JUV

định nghĩa một xích là $1$ dãy các tập hợp $(A_{a_1};A_{a_2};...;A_{a_t})$ thoả mãn $0<a_1<a_2<...<a_t<T+1$ và $A_{a_i}\subset A_{a_{i+1}} \forall 1\leq i\leq t-1$. Với mỗi tập $A_i$, gọi $f(A_i)$ là xích dài nhất nhận $A_i$ là tập đầu tiên trong xích. Giả sử mọi xích đều có độ dài $\leq n-1$ thì lúc đó tồn tại $n$ tập $A_{b_i} \forall i=\overline{1,n}$ thoả mãn $f(A_{b_i})=f(A_{b_j}) \forall i,j=\overline{1,n}$. Nếu tồn tại $i;j$: $1\leq i< j\leq n$ để $A_{b_i}\subset A_{b_j}$ thì $f(A_{b_i})\geq f(A_{b_j})+1$ (vô lí). Vì vậy $n$ tập trên không thoả mãn đề bài, suy ra giả sử sai. Vậy tồn tại $1$ xích độ dài $n$, nhận $A_t$ làm tập cuối cùng trong dãy. Lúc đó $\left | A_t \right |\geq n\Rightarrow A_t=A$.

Đào mộ !

Bài 4:

Nếu $m,n$ cùng chia hết cho $3$ thì đáp số là $mn$

Nếu $m$ chia hết cho $3$ còn $n$ thì không, đáp số là $m(n-1)$(Nếu có $m(n-1)+1$ số $1$ thì trong $m$ hàng sẽ có $1$ hàng chứa $n$ số $1$, tổng $n$ số đó không chia hết cho $3$)

Nếu $m \equiv n\not\equiv 0 \pmod{3}$ thì đáp số là $mn-max\left \{ m;n \right \}$, lập luận tương tự trường hợp trên.

Nếu $m \equiv n+1\equiv 2 \pmod{3}$, ta chứng minh sẽ có ít nhất $\frac{2}{3}(m+n)$ ô không chứa số $1$. Gọi các ô không chứa số $1$ là ô lạ, dễ thấy rằng không có ô lạ nào đứng một mình, tức là không có ô lạ nào khác đứng cùng hàng hoặc cột với nó (Nếu không thì tổng trên cột và hàng chứa ô lạ đó sẽ hơn kém nhau $1$ nên không thể cùng chia hết cho $3$). Ta sẽ tô màu các ô của bảng theo cách sau: Đầu tiên chọn $1$ ô lạ, tô màu tất cả các ô chưa được tô màu nằm cùng hàng và cột với ô đó, sau đó chọn $1$ ô lạ khác chưa được chọn và tiếp tục. Dễ thấy mỗi hàng và cột phải có ít nhất $1$ ô lạ nên rút cuộc tất cả các ô trên bảng đều được tô, hay $m+n$ hàng và cột sẽ được tô(một hàng hoặc cột được tô khi tất cả các ô trên nó được tô). Khi chọn $1$ ô lạ bất kì thì tô được thêm nhiều nhất $2$ đường ($1$ đường tức là $1$ hàng hoặc cột). Nếu sau khi chọn $1$ ô lạ ta tộ được $2$ đường chứa nó thì sẽ có $1$ ô lạ khác nằm cùng hàng hoặc cột với nó chưa được chọn (Nếu được chọn trước rồi thì sau khi chọn ô lạ kia, ta chỉ có thể tô thêm được $1$ đường qua nó). Vậy có cách chọn để cứ chọn $2$ ô lạ liên tiếp, ta tô thêm được nhiều nhất $3$ đường $\Rightarrow$ Số ô lạ ít nhất là $\frac{2}{3}(m+n)$. Vậy số ô có chứa số $1$ ít nhất là $mn-\frac{2}{3}(m+n)$. Lưu ý rằng nếu $max\left \{ m;n \right \}>2min\left \{ m;n \right \}$ thì $max\left \{ m;n \right \}>\frac{2}{3}(m+n)$, lập luận tương tự các tường hợp trên thì số số $1$ nhiều nhất là $mn-max\left \{ m;n;\frac{2}{3}(m+n) \right \}$. Dấu "=" xảy ra khi:

Với $max\left \{ m;n \right \}\leq 2min\left \{ m;n \right \}$(giả sử $n>m$), chọn $\frac{2n-m}{3}$ hàng, mỗi hàng điền $2$ số $0$ sao cho không có $2$ số $0$ nào cùng cột. Trong $\frac{2m-n}{3}$ cột không có số $0$, điền vào mỗi cột $2$ số $1$ sao cho không có $2$ số $1$ hoặc $2$ số $0$ và$1$ cùng hàng.

Nếu $n>2m$, từ $1$ bảng $m\times 2m$ được điền, ta chọn thêm $n-2m$ cột và điền vào mỗi cột đó số $0$ vào ô ở dưới cùng và số $1$ vào các ô còn lại

File kết quả cho mọi người, điểm TST là $23$ nhé :  in_dsdoatgiai_HSGQG_2017-1.pdf   1.05MB   379 Số lần tải

Ta sẽ chứng minh bằng quy nạp rằng $m=2n+1$ là giá trị nhỏ nhất cần tìm. Dễ thấy mệnh đề đúng với $n=2$, giả sử mệnh đề đúng với $n=k$. Xét dãy gồm $m$ số $a_1,a_2,...,a_m$ thoả mãn với mọi lớp có thể có độ dài $k+1$, tồn tại một dãy con của dãy đó có lớp như thế. Giả sử $a_1=a_2$, ta xét các lớp có dạng $(-1;i_1;i_2;...;i_k)$ với $i_t\in \left \{ -1;1 \right \}\forall t=\overline{1,k}$ và $a_{t_1};a_{t_2};...;a_{t_{k+2}}$ là dãy có lớp như thế với $t_1<t_2<...<t_{k+2}$. Có $a_{t_1}\neq a_{t_2}$ nên $t_2>2$. Cũng có dãy $a_{t_2};a_{t_3};...;a_{t_{k+2}}$ là một dãy con có lớp $(i_1;i_2;...;i_k)$ và dãy đó là một dãy con của dãy $a_3,a_4,...,a_m$ nên khi cho các số $i_t$ thay đổi tạo thành tất cả các lớp có thể có độ dài $k$ thì dãy $a_3,a_4,...,a_m$ luôn có một dãy con có lớp như thế. Dãy trên gồm $m-2$ số nên theo giả thiết quy nạp thì $m-2\geq 2k+1$ nên $m\geq 2k+3$. Nếu $a_1\neq a_2$ thì lập luận tương tự với lớp độ dài $k+1$ có dạng $(1;i_1;i_2;...;i_k)$ với $i_t\in \left \{ -1;1 \right \}\forall t=\overline{1,k}$, cũng có $m\geq 2k+3$. Vậy giả thiết quy nạp đúng, hay $m\geq 2n+1$. Có thể xét dãy $2n+1$ số sau: $1,0,1,0,1,0,...,0,1$($n+1$ số $1$ và $n$ số $0$ xếp xen kẽ).

Ta sẽ quy nạp theo $n$, dễ thấy $n=2$ đúng. Giả sử bài toán đúng với $n=k$. Xét $S= \left \{ 1;2;...;k+1 \right \}$. Xét các cặp $(A;S\setminus A)$ với $A\in S, \left | A \right |\geq 2$, nếu tồn tại $M,N$ trong $m$ tập thuộc cùng $1$ cặp thì xét $A_i$ $\forall i=\overline{1,m}$, luôn tồn tại $B_i\in M$ để $A_i\cap M=B_i$. $\forall T\subset M,T\neq \varnothing,T\neq M$, gọi $d_T$ là số các tập $A_i$ để $A_i\cap M=T$ và $A_i\neq T$. Nếu $\exists A_i,A_j: A_i\cap N=A_j\cap N\neq \varnothing, A_i\cap M=T,A_j\cap M=M\setminus T$ thì $3$ tập $(A_i,A_j,M)$ không thoả mãn đề bài. Vậy $A_i\cap N\neq A_j\cap N$ $\forall A_i,A_j:A_i\cap M=T=M\setminus (A_j\cap M)$ $(A_i\neq T,A_j\neq M\setminus T)$. $N$ có $2^{\left | N \right |}-1$ tập con khác rỗng nên $d_T+d_{M\setminus T}\leq 2^{\left | N \right |}-1$.Với $T= \varnothing$, $d_{\varnothing}\leq 2^{\left | N \right |-1}-1$ theo giả thuyết quy nạp, mặt khác với $A_i,A_j$ chứa $M$ và khác $M$ thì $(A_i\cap N)\cap (A_j\cap N)\neq \varnothing$, nếu không thì $(A_i,A_j,N)$ là $3$ tập không thoả mãn. Từ đó suy ra $d_M\leq 2^{\left | N \right |-1}$, vậy $d_M+d_{\varnothing}\leq 2^{\left | N \right |}-1$. Vậy $d_T+d_{M\setminus T}\leq 2{^\left | N \right |}-1\forall T\subset M$ .Gọi $p$ là số tập con $S$ trong $m$ tập mà là tập con của $M$, vì $\left | M \right |<k+1$ nên theo giả thiết quy nạp thì $p\leq 2^{\left | M \right |-1}-1$. Vậy $m=\frac{\sum_{T\subset M}(d_T+d_{M\setminus T})}{2}+p\leq (2^{\left | N \right |}-1)2^{\left | M \right |-1}+2^{\left | M \right |-1}-1=2^{\left | M \right |+\left | N \right |-1}-1= 2^k-1$. Nếu không tồn tại $M,N$ thuộc cùng $1$ cặp, lúc đó $m\leq 2^{n-1}$. Nếu $m=2^{n-1}$, mỗi cặp chỉ có $1$ tập con được chọn. Dễ thấy tất cả tập con có số phần tử bằng $k$ và $k+1$ được chọn, có thể dễ dàng chứng minh nếu tất cả tập con có $i+1$ phần tử được chọn thì tất cả tập con có $i$ phần tử cũng được chọn với $i>\frac{k}{2}$. Vậy tất cả các tập con có $>\frac{k}{2}$ phần tử đều được chọn, dễ suy ra điều vô lí. Vây $m\leq 2^{n-1}-1$ 

Tồn tại $1$ màu sao cho màu đó tô ít nhất $40$ điểm. Gọi $a_1,a_2,...,a_{12}$ là số điểm được tô màu đó trên $12$ đường $x=i$ với $i=\overline{1,12}$. Số cặp điểm cùng màu đã chọn là $\binom{a_i}{2}=\frac{(a_i-1)a_i}{2}$ $\forall i=\overline{1,12}$. Tổng trên cả bảng có $\frac{\sum_{i=1}^{12}a_i^2-a_i}{2}\geq \frac{\frac{40^2}{12}-40}{2}> 46$ cặp điểm cùng màu được chọn và cùng cột. Có $\binom{10}{2}= 45$ cách chọn ra $2$ số nguyên khác nhau thuộc đoạn $\left [ 1;10 \right ]$ nên tồn tại $2$ cặp điểm cùng màu được chọn và cùng cột $(A_1,B_1),(A_2,B_2)$ sao cho tung độ $A_1=A_2$, tung độ $B_1=B_2$ . $A_1B_1B_2A_2$ là hình chữ nhật cần tìm. 

Với mỗi viên sỏi ở cột $i$, gán cho mỗi viên $1$ số $\frac{1}{t}$ với $t$ là số viên sỏi trên cột $i$. Tổng các số trên mỗi cột là $1$ nên tổng các số trên cả bảng là $n$. Vì $n\geq m+1$ nên hoặc tồn tại một hàng có tổng các số viết trên đó $\geq 2$ hoặc tồn tại $2$ hàng mà tổng các số trên mỗi hàng $> 1$. Trên một hàng có tổng các số $\geq 1$, chọn ra số lớn nhất $\frac{1}{k}$. Mỗi khác đều $\leq \frac{1}{k}$ và tổng các số trên hàng đó $> 1$ nên có nhiều hơn $k$ viên sỏi trên hàng đó. Vậy viên sỏi mang số lớn nhất đó là $1$ viên sỏi cần tìm. Nếu có $2$ hàng có tổng $> 1$ thì ta tìm được $2$ viên sỏi, nếu có $1$ hàng có tổng $\geq 2$ thì chọn ra số lớn nhất trong các số trên hàng là $a$. Lưu ý $a\leq 1$ nên tổng các số còn lại $\geq 1$ nên chọn được thêm số lớn thứ nhất trong các số còn lại là $\frac{1}{k}$, số viên sỏi trong hàng chứa nó $\geq k+1$(tính cả viên sỏi được chọn lúc đầu.) $\Rightarrow Q.E.D$

Với $k=7$, chọn $7$ số trong dãy $Fibonacci$ là $1,2,3,5,8,13,21$, dễ thấy không thoả mãn. Xét $\left | S \right |=8$, giả sử $S$ không thoả mãn đề bài, gọi $K=\left \{ (a,b)|a,b\in S,a>b \right \}$, có $\left | K \right |=\binom{8}{2}=28$. Nếu $(a_1;b_1),(a_2;b_2),(a_3;b_3) \in K$ thoả mãn $a_1-b_1=a_2-b_2=a_3-b_3$ thì dễ chỉ ra $2$ tập con của $S$ thoả mãn.Gọi $C=\left \{ a-b|(a,b)\in K \right \}$, $t$ là số giá trị $d$ nằm trong tập $C$ mà tồn tại đúng $2$ phần tử $(a_1,b_1),(a_2,b_2)\in K$ thoả mãn $d=a_1-b_1=a_2-b_2$(do $S$ không thoả mãn đề bài nên $a_1=b_2$ hoặc $a_2=b_1$) . $C\subset \left \{ 1;2;...;23 \right \}$ nên $\left | K \right |-t\leq 23\Rightarrow t\geq 5$. $s\in S$ là $1$ số đặc biệt nếu tồn tại $(a,b)\in K$ sao cho $(a,s,b)$ là CSC. Nếu có $2$ phần tử $(a_1,b_1),(a_2,b_2)\in K$ để $(a_1,s,b_1),(a_2,s,b_2)$ là CSC thì $2$ tập con thoả mãn đề bài $(a_1,b_2),(a_2,b_1)$ (vô lí). Vì $t\geq 5$ nên số số đặc biệt ít nhất là $5$. Mặt khác số lớn nhất và nhỏ nhất trong $S$ không thể là số đặc biệt nên số số đặc biệt nhiều nhất là $6$. Lưu ý rằng khi $t=5$ thì $\left | C \right |\geq 28-5=23$ nên $C$ chứa tất cả các số từ $1$ đến $23$, $t=6$ thì $C$ không chứa nhiều nhất $1$ số trong tập từ $1$ đến $23$.

Số số đặc biệt là $5$, lúc đó có $23\in C$ nên $24,1\in S$. $22\in C$ nên $2$ hoặc $23$ thuộc $S$. Do tính đối xứng nên có thể giả sử $2\in S$, lúc đó $23$ không thuộc $S$. Nếu $3\notin S$ thì $2$ là số không đặc biệt duy nhất. $21\in C$ nên $22\in S$. $22$ là số đặc biệt nên $20\in S$. Lại có $18,21\notin S$ nên để $22$ là số đặc biệt thì $16\in S$. Dễ thấy $19,20\notin S$ và $16$ là số đặc biệt nên $10$ hoặc $8$ thuộc $S$. Trong cả $2$ trường hợp thì không thể chọn được số cuối cùng thuộc $S$. Nếu $3\in S$, $5\in S$, các phần tử của $S$ là $1<2<3<5<x_1<x_2<x_3<24$, $x_1-5$ khác $1$,$2$, $x_3-x_2,x_4-x_3,24-x_3$ đều lớn hơn $4$ nên $24=24-x_3+x_3-x_2+x_2-x_1+x_1-5+5\geq 5+3+5+5+6=24$. Dấu $"="$ xảy ra khi $x_1=8$; $x_2-8=x_3-x_2=5$,$24-x_3=6$ hoặc $24-x_3=x_3-x_2=5$, $x_2-8=6$. Cả $2$ trường hợp đều không thoả mãn. Vậy $3$ là số không đặc biệt duy nhất, tiếp tục lập luận suy ra điều vô lí

Số số đặc biệt là $6$. $22$ hoặc $23$ thuộc $C$ nên $24$ hoặc $23$ thuộc $S$. Nếu $24\notin S$ thì $23$ là số duy nhất không thuộc $C$. Có $1\in S$ và $21\in C$ nên theo tính đối xứng, giả sử $2\in S$.$2$ là số đặc biệt nên $3\in S$. $3$ cũng là số đặc biệt nên $5\in S$. Lập luận tương tự trường hợp trên suy ra điều vô lí. Vậy $1,24\in S$, nếu $22\in C$ thì theo tính đối xứng, giả sử $2\in S$, lập luận tương tự suy ra điều vô lí. Vậy $22$ là số duy nhất không thuộc $C$. $21\in C$ nên theo tính đối xứng, giả sử $3\in S$. $3$ là số đặc biệt nên $5\in S$. Vì $20\in C$ nên $23$ hoặc $21$ thuộc $S$. Nếu $23,24\in S$, lập luận tương tự trường hợp $1,2\in S$ suy ra điều vô lí. Vậy $21\in S$, dễ thấy $22,23\notin S$ và $21$ là số đặc biệt nên $18\in S$. $4\notin S$ và $5$ là số đặc biệt nên $9\in S$. Lúc này cặp $(9,18),(24,3)$ không thoả mãn.

Tóm lại giả sử sai, vậy $k=8$ là số tốt

Với $3$ số $a,b,c$, ta sẽ thực hiện một số phép toán để giảm thực sự $min(a,b,c)$. Giả sử $a\geq b\geq c$, gọi thương của phép chia $b$ cho $c$ là $p$, số dư là $q<c$. Viết $p$ dưới dạng nhị phân là $\overline{a_1a_2...a_t}_{(2)}$, gọi $1=j_1<j_2<...<j_k$ là tất cả các số thoả mãn $a_{j_i}=1 \forall i=\overline{1,k}$. Ta sẽ thực hiện phép toán $t$ lần : Cho $3$ số $a,b,c$ vào $3$ nhóm $A,B,C$, thực hiện phép toán với $2$ số trong $B$ và $C$ tại lần $t+1-j_i \forall i=\overline{1,k}$ và trong những lần khác chọn số trong nhóm $A,C$ ($2$ số nhận được, số bé nhất vào nhóm $C$, số còn lại vào nhóm còn lại).  Sau $t$ lần ta nhận được $3$ số $a+b+c-q-2^{t}c,q,2^{t}c$ với $min(a+b+c-q-2^{t}c,q,2^{t}c)<c$ (do $q<c$). Tiếp tục làm đến khi giảm được $min(a,b,c)=0$ có $Q.E.D$

a/ Đánh số các ghế từ trái sang phải các số từ $1$ đến $20$. Nếu $n>20$ thì luôn có $1$ người cầm ít nhất $2$ quân bài nên trò chơi không thể kết thúc. Nếu $n=20$, mỗi cô gái sẽ lấy số ghế của mình nhân với số đá mình đang cầm gọi $S$ là tổng tất cả các số của $20$ cô gái. Dễ thấy rằng $S$ không đổi dù các cô gái có chuyển đá thế nào. Giả sử ghế của cô gái cầm tất cả đá lần đầu tiên là $a$, ta có $S=20a \vdots 20$. Nếu sau một số lần chuyển, mỗi cô gái cầm $1$ viên đá thì $S=\sum_{i=1}^{20}i$ không chia hết cho $20$ (vô lí). Vậy trò chơi không thể kết thúc khi $n\geq 20$

b/Xét bộ các cô gái liên tiếp $A_1,A_2,...,A_m$ $(20\geq m)$. Giả sử trò chơi diễn ra vô hạn bước, ta sẽ chứng minh rằng sau một số bước nào đó, trong $m$ cô gái đó luôn luôn có ít nhất $m-1$ hòn đá. $m=1$ hiển nhiên đúng, giả sử mệnh đề đúng với $m=k$.Xét các bộ cô gái liên tiếp $A_1,A_2,...,A_{k+1}$, gọi $t$ là số thoả mãn sau $t$ bước, các cô gái $A_1,A_2,...,A_k$ có ít nhất $k-1$ hòn đá và $A_2,A_3,...,A_{k+1}$ cũng vậy. Vì trò chơi diễn ra vô hạn nên mỗi cô gái sẽ chuyển đá vô hạn lần, vậy sau $t$ bước đầu, sẽ tồn tại $1$ bước nào đó mà tại bước đó, $A_1$ được cô gái bên trái chuyển đá cho, lúc này $k+1$ người có ít nhất $k$ viên. Thấy rằng $A_1,A_2,...,A_{k+1}$ chỉ mất đá khi $A_1$ hoặc $A_{k+1}$ chuyển đá. Nếu $A_1$ chuyển đá, lúc đó cô có ít nhất $2$ viên đá, $k$ người còn lại có ít nhất  $k-1$ viên đá, tổng $k+1$ viên. Sau khi chuyển thì mất $1$ viên, vậy còn ít nhất $k$ viên đá, tương tự khi $A_{k+1}$ chuyển đá. Vậy tồn tại một bước nào đó mà sau bước đó, $k+1$ người luôn có ít nhất $k$ viên đá. Vậy mệnh đề quy nạp đúng. Vậy sau $1$ bước nào đó, $m$ cô gái liên tiếp bất kì sẽ có ít nhất $m-1$ viên đá ($m$ bất kì nhỏ hơn hoặc bằng 20). Xét các cô gái không cầm viên đá nào lúc đó, các cô gái sẽ đứng lên và di chuyển theo chiều kim đồng hồ đến chỗ của cô gái gần nhất cầm ít nhất $2$ viên đá. Không có cô gái nào đi qua ghế của cô gái không cầm đá nào bởi nếu cô gái $A_1$ đi qua ghế của cô gái $A_m$ không cầm đá thì các cô gái $A_2,A_3,...,A_{m-1}$ mỗi người cầm nhiều nhất $1$ viên đá, $A_1$ và $A_m$ không cầm đá nên $m$ người đó có nhiều nhất $m-2$ viên đá (vô lí). Nếu cô gái đi qua tất cả các ghế mà không có cô gái nào cầm $2$ viên đá thì trò chơi kết thúc, nếu mỗi cô gái không cầm đá tìm được $1$ cô gái cầm $2$ viên đá thì không có $2$ cô gái không cầm đá nào gặp cùng $1$ cô cầm $2$ viên do sẽ có $1$ người đi qua ghế của người khác trong $2$ cô. Mỗi cô gái không cầm đá tìm được đúng $1$ cô gái cầm $2$ viên đá nên số đá ít nhất là $20$ (vô lí)

Nếu ô có dấu $+$ là $1$ trong $4$ góc của bảng thì chỉ cần đổi dấu tất cả các đường chéo không song song với đường chéo chứa ô đó là được $1$ bảng thoả mãn. Nếu như ô đó không phải là $1$ góc của bảng thì lúc đó tồn tại $1$ bảng con $4\times 4$ để cho ô vuông được đánh dấu cộng nằm có đúng $1$ cạnh nằm trên $1$ cạnh bảng con đã cho và nằm trong bảng con đó. Trong bảng con đó, có đúng $8$ ô vuông có đúng $1$ cạnh vuông với bảng và có đúng $1$ ô chứa dấu $+$. Dễ thấy rằng số ô trong $8$ ô đó chứa dấu $+$ luôn là $1$ số lẻ, nên không thể đạt được trạng thái đề ra.

P/s: Nếu đánh $+$ và $-$ một vài ô bất kì của bảng và để cho bảng có về trạng thái như trên, điều kiện cần và đủ là không có bảng $4\times 4$ nào có $8$ ô nằm bên trong nó và có đúng $1$ cạnh nằm trên $1$ cạnh bảng đó, chứa $1$ số lẻ các ô vuông đánh dấu $+$

Bài 1:

Với $n=2,3$, hiển nhiên bài toán đúng. Giả sử bài toán đúng với $n=k\geq 3$, xét $n=k+1$ điểm trên mặt phẳng. Giả sử $A$ là điểm có ít nhất các điểm cách $A$ khoảng cách là $1$ (giả sử là $x$ điểm). Nếu $x> \frac{1}{4}+\sqrt{\frac{k+1}{2}}+\frac{k}{\sqrt{2k+2}+\sqrt{2k}}$, trong $k$ điểm còn lại, mỗi điểm có ít nhất $x$ điểm cách nó $1$ đơn vị. Trừ đi $x$ điểm cách $A$ $1$ đơn vị, $k$ điểm kia cách có số cặp điểm cách nhau $1$ ít nhất là $(k-1)x> (k-1)\left ( \frac{1}{4}+\sqrt{\frac{k+1}{2}}+\frac{k}{\sqrt{2k+2}+\sqrt{2k}} \right )>\frac{k}{4}+\frac{\sqrt{2k^3}}{2}$ (trái với giả thiết quy nạp). Nếu $x\leq \frac{1}{4}+\sqrt{\frac{k+1}{2}}+\frac{k}{\sqrt{2k+2}+\sqrt{2k}}$, $k$ điểm kia có không quá $\frac{k}{4}+\frac{\sqrt{2k^3}}{2}$ cặp điểm có khoảng cách $1$ nên tổng cộng có không quá $\frac{k+1}{4}+\frac{\sqrt{2\left ( k+1 \right )^3}}{2}$ cặp điểm khoảng cách bằng $1$. Bài toán đúng với $n=k+1$$\Rightarrow Q.E.D$

Bài 2:

Đầu tiên xét các bộ $n-2$ người, có tất cả $\binom{n}{2}=\frac{n(n-1)}{2}$ bộ như vậy. Tong mỗi bộ có $3^k$ cặp người quen nhau nên đếm được $\frac{3^kn(n-1)}{2}$ cặp. Tuy nhiên mỗi cặp được đếm $\binom{n-2}{n-4}=\frac{(n-2)(n-3)}{2}$ lần nên có tổng cộng $\frac{3^kn(n-1)}{(n-2)(n-3)}$ cặp $\Rightarrow 3^kn(n-1)\vdots (n-2)(n-3)\Rightarrow n=4;n=5$

Bài 3:

Chỉ cần giải bài toán với trường hợp $n$ chẵn, tức $n=2k$. Xét $1$ bảng $2k\times 2k$, viết các số từ $1$ đến $2k$ từ trái sang phải trên các cột, từ dưới lên trên trên các hàng biểu thị cho các người $1,2,...,2k$. Ở ô $(i;j)$, ta đánh số $1$ nếu người $i$ quen $j$,$0$ nếu ngược lại, để trống nếu $i=j$. Trên mỗi hàng $i$, gọi $t_i$ là số số $1$, $p_i$ là số số $0$ trên hàng đó. Có $t_i+p_i=2k-1$, số cặp ô có viết cùng số trên hàng đó là $\frac{t_i^2+p_i^2-t_i-p_i}{2}\geq \frac{k^2+(k-1)^2-2k+1}{2}$. Trên cả $2k$ hàng có ít nhất $k(k^2+(k-1)^2-2k+1)$ cặp ô cùng hàng và cùng số. Số cặp cột là $\binom{2k}{2}=k(2k-1)$ nên có $1$ cặp cột $(m,n)$ chứa ít nhất $\frac{k(k^2+(k-1)^2-2k+1)}{k(2k-1)}>k-2$ cặp ô cùng hàng và cùng số$\Rightarrow$ Cặp cột $(m,n)$ có ít nhất $k-1$ cặp ô cùng hàng và cùng số, hay có ít nhất $k-1$ người cùng quen hoặc không quen $2$ người $m,n$ $(Q.E.D)$

Trường hợp tổng quát cho $n>8$: Nếu $n$ lẻ, đặt $n=2k+1$. Chiến thuật giúp $A$ thắng: đầu tiên $A$ sẽ loại $n$ ra khỏi bảng và chia $n-1$ số còn lại thành $k$ cặp $(1,2),(3,4),...,(2k-1,2k)$.Mỗi lượt $B$ sẽ chọn $1$ số trong $1$ cặp bất kì, $A$ chỉ việc loại số còn lại trong cặp đó và trên bảng luôn còn những cặp số liên tiếp nên cuối cùng trên bảng sẽ còn $2$ số liên tiếp và $A$ sẽ thắng. Còn nếu $n$ chẵn thì $B$ sẽ thắng: Đặt $n=2k$ gọi $S_i$ là hiệu giữa số số chẵn với số số lẻ trên bảng sau bước thứ $i$ của $B$. Có $S_0=0$, chiến thuật thắng của $B$ như sau: Rõ ràng trò chơi sẽ kết thúc sau $k-1$ bước, trong $k-2$ bước đầu của $B$, anh ta sẽ chọn ra $2$ số lẻ $u,v$ với $(u,v)>1$ (luôn chọn được vì $n>8$) và sẽ chỉ loại những số lẻ trên bảng khác $u,v$ nếu có thể. Nếu trong $k-2$ bước đầu của $A$, $A$ chọn loại $1$ số lẻ tại bước thứ $i$ và $B$ chọn loại $1$ số lẻ khác thì $S_i\geq 2$. Lúc đó $B$ sẽ chọn loại tất cả các số lẻ khác trên bảng và $S_i$ sẽ không giảm. Cuối cùng trên bảng còn ít nhất $2$ số chẵn, $A$ và $B$ cứ loại dần đến khi chỉ còn $2$ số chẵn và $B$ thắng. Còn nếu $A$ luôn chọn loại số chẵn trong $k-2$ bước đầu thì sau $k-2$ bước của cả $2$, trên bảng còn $2$ số chẵn $a,b$ và $2$ số lẻ $u,v$. Nếu sau đó $A$ chọn loại $1$ số trong cặp $(a,b)$ thì $B$ sẽ loại số còn lại trong nhóm đó và trên bảng còn $2$ số $u,v$ với $(u,v)>1$. Còn nếu $A$ chọn loại $1$ số trong $(u,v)$ thì $B$ loại số còn lại, trên bảng còn $2$ số $a,b$ chẵn có $(a,b)>1$. Tóm lại $A$ thắng nếu $n$ lẻ, $B$ thắng nếu $n$ chẵn

Nếu có $1$ thí sinh giải được $4$ bài (giả sử là $1,2,3,4$) thì không ai giải được cả $2$ bài $5$ và $6$. Mà trong mỗi bài $5$ và $6$ đều có $100$ người giải được nên số thí sinh ít nhất là $100+100+1=201$. Nếu mỗi người giải được không quá $3$ bài, vì có $600$ bài làm nên sẽ có ít nhất $\frac{600}{3}=200$ thí sinh. Vậy cần ít nhất $200$ thí sinh, có thể chia bài làm cho mỗi thí sinh như sau: Chia $200$ người làm $4$ nhóm $50$ người: 

Nhóm $1$ làm các bài $1,2,3$

Nhóm $2$ làm các bài $1,4,5$

Nhóm $3$ làm các bài $2,5,6$

Nhóm $4$ làm các bài $3,4,6$

($50$ người trong cùng $1$ nhóm làm $3$ bài giống nhau và giống như cách sắp xếp trên)

Câu 1 chỉ cần chứng minh tam giác có $3$ cạnh độ dài $<1$ thì bán kính đường tròn ngoại tiếp $< \frac{1}{\sqrt{3}}$. Vẽ các đường tròn bán kính $=\frac{1}{\sqrt{3}}$ tâm là các điểm đang xét thì theo Helly, các đường tròn đó có $1$ điểm chung $A$ nên $(A; \frac{1}{\sqrt{3}})$ là đường tròn cần tìm. Còn câu 2 thì gọi độ dài lớn nhất là $a$ thì tồn tại $1$ đường tròn $(A;\frac{1}{\sqrt{3}})$ chứa tất cả các điểm đó. Dễ CM có $2$ điểm $B,C$ để $\widehat{BAC}\leq 60^\circ$ nên $BC\leq \frac{a}{\sqrt{3}}$$\Rightarrow Q.E.D$