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

Khi đổi chỗ $2$ số bất kì, tính chẵn lẻ của số nghịch thế thay đổi. Vậy cần phải có $a\vdots 2$ để có thể về được dãy ban đầu (Trong dãy $a_1,a_2,...,a_n$, cặp $(a_i,a_j)$ được gọi là nghịch thế nếu $i<j$ mà $a_i>a_j$)

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)$

Theo định lí Sperner, phản chuỗi lớn nhất của $A$ chứa $\binom{n}{\left [ \frac{n}{2} \right ]}$ phần tử, dấu bằng xảy ra khi tất cả các tập hợp là tập con có $\left [ \frac{n}{2} \right ]$ phần tử của $A$. Vậy số $k$ nhỏ nhất chính là $\binom{n}{\left [ \frac{n}{2} \right ]}+1$

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$

Quy nạp theo $n$: Giả sử bài toán đúng với $n=k$, xét $k+1$ điểm thoả mãn đề bài. Từ $1$ điểm $A$ nằm trên bao lồi $k+1$ điểm đó, vẽ đường tròn bán kính $1$. Giả sử có ít nhất $4$ điểm trên đường tròn đó thì $4$ điểm đó sẽ nằm cùng về $1$ nửa đường tròn đó. Từ đây áp dụng thêm Dirichlet thì sẽ suy ra có $2$ điểm có khoảng cách <1. Vậy có nhiều nhất $3$ điểm nằm trên đường tròn đó. Xoá $A$ và xét $k$ điểm còn lại, có nhiều nhất $3k-6$ cặp điểm thảo mãn. Vậy có tổng cộng nhiều nhất $3(k+1)-6$ cặp điểm thoả mãn $\Rightarrow Q.E.D$

Gọi $1$ bảng $m\times n$ thoả mãn đề bài là bảng có tính chất $P$. Chứng minh quy nạp theo $m+n$ rằng tất cả bảng $m\times n$ có tính chất $P$ thì $m=n$. Dễ dàng kiểm tra với $m+n=2,3,4$. Giả sử mệnh đề đúng với $m+n=k$. Xét bảng $m\times n$ với $m+n=k+1$, ta thay những số dương trên bảng bằng dấu $+$ và giữ nguyên ô chứa số $0$. Bước đầu tiên xét $1$ cột bất kì và đánh dấu các ô chứa dấu $+$ của cột đó. Ta sẽ đánh dấu $1$ số ô chứa dấu $+$ của bảng theo quy tắc sau trong những bước sau: Xét $1$ ô được đánh dấu, đánh dấu tất cả các ô cùng hàng hoặc cùng cột với nó mà chứa dấu $+$(nếu chưa được đánh dấu). Gọi $1$ hàng hoặc cột là tốt nếu như nó có $1$ ô được đánh dấu, dễ thấy tất cả các ô chứa dấu $+$ của $1$ hàng hoặc cột tốt đều được đánh dấu. Giả sử có $a$ cột, $b$ hàng tốt thì xét $ab$ giao điểm của chúng. Dễ thấy nếu $1$ ô không nằm trong $ab$ giao điểm đó mà thuộc $1$ hàng hoặc cột tốt thì nó sẽ chứa số $0$. Vậy tổng tất cả các số trong các ô thuộc hàng và cột tốt bằng tổng tất cả các số nằm trong $ab$ giao điểm (đặt là $S$). Cũng thấy rằng tổng tất cả các số trong mỗi cột tốt bằng nhau và bằng tổng các số trong mỗi hàng tốt$\Rightarrow \frac{S}{a}=\frac{S}{b}\Rightarrow a=b=t$. Giờ xoá tất cả các hàng tốt và cột tốt ra khỏi bảng, ta còn lại $m-t$ hàng và $n-t$ cột, ghép lại thành $1$ bảng $(m-t)\times(n-t)$ cũng có tính chất $P$ $\Rightarrow m-t=n-t$ (do $m+n-2t<k$).Vậy $m=n$$\Rightarrow Q.E.D$

Câu a chính là bất đẳng thức Lubell- Yamamoto- Meshalkin, có thể tìm chứng minh trên mạng. Còn câu b thì ta có thể chứng minh trực tiếp từ KQ câu a: $1\geq \sum_{i=0}^{n}\frac{a_i}{\binom{n}{i}}\geq \left ( \sum_{i=0}^{n}a_i \right )\frac{1}{\binom{n}{\left \lfloor \frac{n}{2} \right \rfloor}}\Rightarrow \left | \Im \right |\leq \begin{pmatrix} n\\ \left \lfloor \frac{n}{2} \right \rfloor \end{pmatrix}$

không, ý mình là đầu bài cho sẵn là tô luân phiên rồi mà...

Nếu cho sẵn cách tô rồi thì còn hỏi cách tô nào cho số giao điểm lớn nhất nữa ?

Mình tưởng tô luân phiên là cứ xanh - đỏ - xanh - đỏ - ... chứ nhỉ...

Giả sử tô $A_1,A_3$ xanh, $A_2,A_4$ đỏ thì $A_1A_2$ không cắt $A_3A_4$,$A_1A_4$ không cắt $A_2A_3$ nên khi chọn $4$ điểm đó thì ta sẽ không thu được giao điểm nào, vì vậy tô theo cách của mình vẫn tốt hơn

Bài 4: Giả sử có $k$ điểm xanh, $2n-k$ điểm đỏ. Chọn ra bộ $4$ điểm $2$ xanh là $A_1,A_2$, $2$ đỏ là $B_1,B_2$. Xét các cặp đoạn thẳng $(A_1B_1;A_2B_2)$ và $(A_1B_2;A_2B_1)$. Dễ thấy rằng nếu $A_1B_1,A_2B_2$ cắt nhau thì $A_2B_1,A_1B_2$ không cắt nhau. Vậy trong $2$ cặp đoạn thẳng đó chỉ chứa nhiều nhất $1$ giao điểm. Vì vậy cứ chọn $4$ điểm thoả mãn $2$ điểm xanh ,$2$ đỏ thì sẽ tạo ra nhiều nhất $1$ giao điểm. Có tất cả $\binom{k}{2}\binom{2n-k}{2}\leq \binom{n}{2}^2$ cách chọn $4$ điểm nên có nhiều nhất $\binom{n}{2}^2$ giao điểm. Xét đa giác $A_1A_2...A_{2n}$ thì ta tô xanh $A_1,A_2,...,A_n$, đỏ $A_{n+1},...,A_{2n}$ thì số giao điểm sẽ lớn nhất (không có $3$ đoạn nào đồng quy)

Câu 5: Ta có $a_{i+1}-a_i\leq 1\Rightarrow (a_{i+1}-i-1)-(a_i-i)\leq 0$ $\forall \ i=\overline{1,2015}$. Gọi $i,j$ là $2$ số thoả mãn $a_i=i$,$a_j=j$ với $j>i$, có $0=a_i-i\geq a_{i+1}-i-1 \geq a_j-j=0$ và theo tính duy nhất của $i$ và $j$ thì $j=i+1$. Cũng theo tính duy nhất của $i$, $a_{i-1}>i+1$,$a_{i+2}<i$ và nếu tồn tại $t>i+1$ để $a_t>i$ thì vì$a_{i+2}<i$ nên sẽ tồn tại $p>i+1$ để $a_p<i$,$a_{p+1}>i$ và $a_{p+1}-a_p>1$(vô lí). Vậy các số $(a_{i+2},a_{i+3},...,a_{2016})$ là hoán vị của $(1,2,...,i-1)$$\Rightarrow$ $i-1=2015-i$ hay $i=1008$. Giờ ta sẽ tìm cách hoán vị các số $a_{1010}$ đến $a_{2016}$ thoả mãn đề bài. Gọi $s$ là số lớn nhất thoả mãn $a_{1010},a_{1011},...,a_s$ lập thành cấp số cộng công sai $1$. Nếu $a_s<1007$, lúc đó ta có $a_{s+1}<a_s$ và tồn tại $k>s$ thoả mãn $a_k>a_s$. Khi đó sẽ tồn tại $p>s$ thoả mãn $a_p<a_s$ và $a_{p+1}>a_s$ nên $a_{p+1}-a_p>1$. Vậy $a_s=1007$, tương tự nếu $s_1$ là số lớn nhất thoả mãn $a_{s+1},a_{s+2},...,a_{s_1}$ lập thành cấp số cộng công sai $1$ thì $a_{s_1}=a_{1010}-1$. Tương tự như thế thì dãy số $a_{1010},a_{1011},...,a_{2016}$ sẽ được tạo theo cách sau: Số hạng đầu tiên chọn ngẫu nhiên rồi các số tiếp theo sẽ chọn sao cho các số hạng tiếp theo sẽ lập thành cấp số cộng đến khi có $1$ số là số hạng lớn nhất chưa được chọn trong dãy; số hạng sau đó được chọn ngẫu nhiên trong các số còn lại và cứ tiếp tục như thế.Những cách chọn ngẫu nhiên trong dãy được gọi là cách chọn đặc biệt. Gọi $1$ nhóm $(i_1,i_2,...,i_t)$ được xác định rằng $i_1,i_2,...,i_t$ lần lượt là số đầu tiên, thứ $2$,...,thứ $t-1$,thứ $t$ là tất cả các số được dùng trong cách chọn đặc biệt để gắn cho một số số xác định trong dãy $a_{1010},a_{1011},...,a_{2016}$. Dễ thấy $i_1>i_2>...>i_t$ nên số cách chọn dãy đó là số cách chọn các tập con trong tập $\left \{ 1,2,...,1007 \right \}$ và bằng $2^{1007}$. Dễ thấy nếu chọn $1$ nhóm thì chỉ có $1$ dãy $a_{1010},a_{1011},...,a_{2016}$ được tạo thành nên số dãy thoả mãn là $2^{1007}$. Tương tự số cách chọn dãy $a_1,a_2,...,a_{1007}$ là $2^{1007}$. Vậy tổng số hoán vị thoả mãn là $2^{2014}$

Bài 5 (ngày 2): Xét $1$ cách chọn các bộ số thoả mãn không có $2$ bộ nào trội nhau và $1$ bảng $8\times 8$, đánh dấu các cột từ dưới lên trên $0$ đến $7$, các hàng từ trái sang phải $0$ đến $7$. Đánh dấu vài ô vuông $1\times 1$ trong đó, ô vuông $(y,z)$ được đánh dấu ($y$ là số hàng, $z$ là số cột) nếu có một bộ $(x,y,z)$ được chọn. Ta thấy rằng nếu có $2$ bộ $(x_1;y;z)$ và $(x_2,y,z)$ được chọn thì một bộ phải trội hơn bộ còn lại (với $x_1,x_2,y,z$ là 4 số trong các số từ $0$ đến $7$) nên với một ô $(y,z)$ được đánh dấu thì tồn tại duy nhất một số $x$ trong khoảng từ $0$ đến $7$ được chọn thoả mãn $(x,y,z)$ được chọn, hay số ô đánh dấu bằng số bộ số được chọn. Ta gọi một ô $(y_1,z_1)$ đến được một ô $(y_2,z_2)$ nếu $y_1\geq y_2,z_1\geq z_2$ và $2$ ô đó phân biệt.Dễ thấy $y_1+z_1>y_2+z_2$$(1)$. Ta thấy rằng không thể tồn tại $9$ ô $(y_1,z_1),(y_2,z_2),...,(y_9,z_9)$ sao cho $(y_i,z_i)$ có thể đến được $(y_{i+1},z_{i+1})$ $\forall i=\overline{1,8}$ vì như thế thì sẽ tồn tại $9$ bộ số $(x_i,y_i,z_i)$ và $x_9>x_8>...>x_1$(do không có 2 bộ nào trội nhau)(vô lí do $x_i$ chỉ chọn từ $0$ đến $7$). Gọi $S_1$ là tập tất cả các ô mà không thể đi từ một ô nào khác đến các ô đó và $S_{i+1}$ là tập các ô mà với mỗi ô bất kì từ tập $S_{i+1}$ thì có một ô thuộc $S_i$ đi đến được ô đó. Theo lập luận trên thì $S_9$ là tập rỗng. Xét các tổng tung độ và hoành độ trong các ô thộc $S_i$($(y,z)$ có tổng là $y+z$) và đặt $m_i$ là số lớn nhất trong các số đó. Vì không có $2$ số nào trong tập $S_i$ thuộc cùng $1$ hàng hoặc $1$ cột và vì có một ô trong $S_i$ thoả mãn tổng tung độ và hoành độ của nó là $m_i$ nên dễ chứng minh $\left | S_i \right |\leq t_i$ với $t_i=14+1-m_i$ nếu $m_i>6$,$t_i=m_i+1$ nếu $m_i<7$. Dễ thấy không có ô nào thuộc $S_9$ vì nếu không sẽ tạo ra $1$ đường đi $9$ ô nên và chú ý rằng $m_1>m_2>...>m_8$ do $(1)$ nên tổng số ô trên bảng là $\sum_{i=1}^{8}\left | S_i \right |\leq \sum_{i=1}^{8}t_i\leq 5+6+7+8+7+6+5+4=48$. Vậy có nhiều nhất $48$ ô được đánh dấu nên chỉ chọn được $48$ bộ số. Ta có cách chọn $48$ bộ số sau $(x,y,z)$ với mọi $y,z$ thoả mãn $4\leq y+z\leq 11$ và $x=y+z-4$. Vậy dễ dàng suy ra $n=49$ là giá trị nhỏ nhất

Câu 7: Dễ thấy $2017$ là số nguyên tố. Nếu $n=1008$, ta có $1008$ số $1,2,...,1008$ không thoả mãn đề bài. Giả sử tồn tại $1009$ số không thoả mãn đề bài. Nếu trong $1009$ số đó có $1$ số $a_i$ chia hết cho $2007$, $1$ số $a_j$ không chia hết thì đặt $a_i=2017c$, có$\frac{a_i+a_j}{(a_i;a_j)}> \frac{2017c}{(2017c;a_j)}=\frac{2017c}{(c;a_j)}\geq \frac{2017c}{c}=2017$(vô lí). Nếu tất cả các số đều chia hết cho $2017$ thì ta chia các số đó cho $2017$, ta cũng được $1009$ số không thoả mãn đề bài. Cứ chia như vậy cho đến khi có $1$ số không chia hết cho $2017$. Nếu lúc đó còn $1$ số chia hết cho $2017$ thì lập luận tương tự suy ra điều vô lí. Nếu tất cả các số đều không chia hết cho $2017$, giả sử tồn tại $a_i;a_j$ sao cho $a_i-a_j=2017c$ với $c$ là $1$ số nguyên dương thì $\frac{a_i+a_j}{(a_i;a_j)}= \frac{2017c+2a_j}{(a_j;2017c)}> \frac{2017c}{(a_j;c)}\geq \frac{2017c}{c}=2017$(vô lí). Nếu không có $2$ số nào đồng dư với nhau $\pmod{2017}$ thì xét $1008$ cặp $(1;2016),(2;2015);...;(1008;1009)$, lúc đó tồn tại $2$ số $a_i;a_j$ trong $1009$ số sao cho $a_i+a_j=2017d$ với $d$ nguyên. Vì vậy $\frac{a_i+a_j}{(a_j;a_i)}= \frac{2017d}{(a_j;a_i+a_j)}= \frac{2017d}{(2017d;a_j)}=\frac{2017d}{(d;a_j)}\geq \frac{2017d}{d}= 2017$ (vô lí). Vậy giả sử sai, hay luôn tồn tại $2$ trong $1009$ số thoả mãn đề bài. Vậy $n=1009$

Bài 2: Ta nhận xét rằng để biểu diễn số $n!-1$ thì cần ít nhất $\frac{n(n-1)}{2}$ lá bài. Thật vậy thì ta có thể biểu diễn $n!-1=(n-1)((n-1)!)+(n-2)((n-2)!)+...+2.2!+1.1!$. Xét cách biểu diễn $n!-1=a_1.1!+a_2.2!+...+a_{n-1}.(n-1)!$ trong đó ta dùng lần lượt $a_1,a_2,...,a_{n-1}$ quân bài $1!,2!,...,(n-1)!$ và $a_1+a_2+...a_{n-1}$ nhỏ nhất. Ta thấy rằng $a_i<i+1$$\forall 0<i<n$, nếu không thì ta chỉ cần thay $i+1$ lá bài $i!$ thành $1$ lá bài $(i+1)!$ thì sẽ tạo được $1$ cách chọn bài ít hơn. Cộng số các lá bài $a_i$ lại ta có số lá bài dùng để biểu diễn $n!-1$ ít nhất là $\frac{n(n-1)}{2}$ lá bài. Dễ thấy là để biểu diễn $n!-1$ dưới ít nhất $\frac{n(n-1)}{2}$ lá bài thì các lá bài đó chỉ có thể là $i$ lá bài $i!$ $\forall 0<i<n$, tuy nhiên các lá bài đó không thể biểu diễn được $n!$ nên ta sẽ cần $\frac{n(n-1)}{2}+1$ lá bài để có thể thoả mãn đề bài (có thể thêm $1$ lá bài $1!$ hoặc $n!$). Vậy cần ít nhất $\frac{n(n-1)}{2}+1$ lá bài

Nếu tồn tại $1$ đỉnh nối với ít hơn $5$ đỉnh thì sẽ có ít nhất $4$ đỉnh không nối với đỉnh đó, $4$ đỉnh đó sẽ đôi một nối với nhau.Nếu có $1$ đỉnh $A$ nối với ít nhất $6$ điểm $A_1,A_2,A_3,A_4,A_5,A_6$. Nếu một trong $6$ điểm đó nối với nhiều nhất $2$ trong $6$ điểm thì trong ít nhất $3$ điểm còn lại, các điểm đôi một nối với nhau nên $3$ điểm đó với điểm $A$ tạo $G4$. Nếu tồn tại $1$ điểm $B$ nối với ít nhất $3$ điểm trong $6$ điểm thì trong $3$ điểm đó tồn tại $1$ cạnh, từ đó có $G4$ là $A,B$ và $2$ điểm được nối.Nếu mỗi điểm trong $9$ điểm đó nối với đúng $5$ đỉnh thì tổng số cạnh là $\frac{5\times 9}{2}\notin \mathbb{N}$(vô lí) $\Rightarrow$ $(Q.E.D)$

Câu 4: Xét $11$ số $a+1,...,a+11 (a<2006)$. Chọn ra các số sao cho không có $2$ số nào có hiệu là $4$ hoặc $7$. Chia tập $D_a= \left \{ a+1;...;a+11 \right \}$ thành các nhóm $(a+1,a+8),(a+2,a+6),(a+3,a+7),(a+4,a+11),(a+5,a+9),(a+10)$.Không có $2$ số được chọn nào được thuộc cùng một nhóm và không thể chọn số $a+10$ rồi chọn mỗi nhóm $1$ số nên có nhiều nhất $5$ số được chọn . Chia tập $2016$ số nguyên dương đầu tiên thành các tập $(2016;2015;2014),A_0,A_{11},...,A_{2002}$, tâp đầu chọn nhiều nhất $3$ số, các tập tiếp theo, mỗi tập chọn được nhiều nhất $5$ số, lưu ý là nếu cả $3$ số $2013,2014,2015$ được chọn thì chỉ chọn được nhiều nhất $4$ số ở $A_{2002}$ nên tổng số cách chọn nhiều nhất là $183\times 5+2=917$, chẳng hạn khi ta chọn các số đồng dư $1,2,4,7,10 \pmod{11}$

Bài 7: Xét số $k$ bất kì với $1\leq k\leq 2017^2-2017$. Gọi $A_k=\left \{ 1,2,...,k \right \}$,$B_k=\left \{ k+1,k+2,...,k+2016 \right \}$,$C_k=\left \{ k+2017,k+2018,...,2017^2 \right \}$. Vì $\left | B_k \right |=2016$ nên tồn tại một hàng không chứa số nào thuộc $B_k$, tương tự với cột. Gọi tập các ô nằm trong hình chữ thập tạo bởi hàng và cột đó là $D_k$, dĩ nhiên $\left | D_k \right |=4033$.Nếu tồn tại $k$ để $D_k$ chứa $2$ số $a\in A_k,c\in C_k$ và ô chứa $2$ số đó nằm cạnh nhau thì dễ thấy $\left | a-c \right |\geq 2017$. Nếu không thì hoặc $D_k$ chỉ chứa toàn các số hoặc thuộc $A_k$, hoặc các số thuộc $C_k$. Có $A_1$ có $1$ phần tử, $C_{2017^2-2017}$ có $1$ phần tử nên $D_1$ chỉ chứa số thuộc $C_1$,$D_{2017^2-2017}$ chỉ chứa các số thuộc $A_{2017^2-2017}$. Vậy tồn tại $c$ sao cho $D_c$ chỉ chứa số thuộc $C_c$,$D_{c+1}$ chỉ chứa số thuộc $A_{c+1}$. Hai hình chữ thập đó cắt nhau tại ít nhất $1$ ô có số $e$ thoả mãn $k+2016<e<k+2$(do $e$ nằm trong cả $C_c$,$A_{c+1}$) vô lí, $Q.E.D$.Còn câu b thì đáp số đơn giản là $2017$, chỉ cần xét bảng mà hàng đầu có các số từ $1$ đến $2017$ từ trái sang phải, hàng $2$ có số $2018$ đến $4034$ từ trái sang phải rồi tương tự với các hàng kế tiếp

Bài 2 ngày 2: Sau mỗi bước sẽ có 1 tập vài quyển sách ở đúng vị trí, có tất cả $2^n$ tập, ta sẽ chứng minh không có 2 bước nào có 2 tập nào giống nhau

Quy ước lấy chiều từ trái sang phải

Ta thấy 1 quyển nếu chưa ở vị trí đúng thì sau khi bị di chuyển bởi quyển khác chỉ có thể sang phải, nếu đã ở vị trí đúng rồi thì sau đó không thế về vị trí nào trước vị trí đúng  

- Giả sử có 2 bước thứ $x$ và $y (x<y)$ có tập $a_1,...a_k$ trùng nhau

+ TH1: Nếu bước thứ $y$ chuyển quyển thứ $a_k$, vị trí đúng của $a_k$ không phải ở cuối

Các quyển ở sau $a_k$ sau bước thứ $x$ không thể có vị trí đúng là trước vị trí đúng của $a_k$ nếu không sẽ có 1 quyển được đưa về vị trí đúng trước bước thứ $y$, tạo ra 1 tập khác 

Vì các quyển sau $a_k$ có vị trí đúng sau $a_k$ nên sẽ di chuyển về vị trí đúng mà không ảnh hưởng tới các quyển khác, sau đó sẽ di chuyển quyển sai vị trí gần nhất trước $a_k$, nhưng lúc này không thể thay đổi vị trí $a_k$ và các quyển sau nữa.

+ TH2: bước thứ $y$ di chuyển quyển $a_i (i \neq k)$

Khi di chuyển $a_i$ nghĩa là tất cả các quyển sau $a_i$ đã đúng vị trí và khi di chuyển $a_i$ các quyển đó không đổi vị trí, suy ra các quyển đó đúng vị trí từ bước $x$, tuy nhiên khi điều đó có nghĩa tất cả các quyển từ $a_i$ trở đi đều không bị di chuyển, nên từ bước $x$ tới bước $y$ ta chỉ có thể di chuyển các quyển trước $a_i$, mâu thuẫn với việc quyển bị di chuyển là $a_i$

Đề bài cần chứng minh sau ít hơn $2^n$ lần chứ không phải nhiều nhất $2^n$ lần