$\boxed{\text{Bài toán 1}}$Cho số nguyên dương $k$ . Tìm số các số tự nhiên $n$ không vượt quá $10^{k}$ thỏa mãn : $i)$ $n$ là bội của $3$ $ii)$ Các chữ số trong biểu diễn thập phân của $n$ là $2,0,1,5$. Spoiler: Lời giải Xét đa thức $P(x)=(x^5+x^2+x+1)^k$ Dễ thấy tổng các hệ số của đa thức cũng bằng số các bộ $\left ( a_1,a_2,..,a_k \right )\in \begin{Bmatrix} 2;0;1;5\end{Bmatrix}^k$ bằng $4^k.$ hơn nữa số bộ số này chia hết cho 3 cũng bằng tổng hệ số $x^{3k}$ trong đa thức. Theo định lí Ruf: $S=S=\frac{1}{3}[P(1)+P(\epsilon )+P(\epsilon^2 )]$, gọi $\epsilon$ là nghiệm của phương trình $x^2+x+1=0$ thì phương trình có nghiệm phức $\epsilon_t=cos\frac{2t\pi }{3}+isin\frac{2t\pi }{3}$. Từ đây ta có $\epsilon^3=1$ do đó $1+\epsilon+\epsilon^{2k}=0$ với $k$ không chia hết cho 3 và bằng 3 với $k$ chia hết cho 3. Dễ dàng tính được $P(1)=4^k,P(\epsilon )=\epsilon^{2k},P(\epsilon^2)=\epsilon^{4k}$. Từ đây suy ra $\left\{\begin{matrix} S=\frac{4^K-1}{3},K\neq 3m\\ S=\frac{4^K+2}{3},K=3m \end{matrix}\right.,m \in \mathbb{Z}$. $\boxed{\text{Bài toán 2}}$Trong một cuộc họp có $12k$ người tham gia, mỗi người bắt tay với đúng $3k+6$ người khác. Biết rằng với bất kỳ một cách chọn cặp $2$ người ta có số người bắt tay với cả hai là như nhau. Hỏi có bao nhiêu người tham gia cuộc họp đó? Spoiler: Lời giải Ta giải bài toán này bằng đếm bằng hai cách. Ta đếm bộ ba $(A,B,C)$ các người, trong đó $A$ bắt tay với $B,C$ nhưng $B,C$ lại không bắt tay với nhau. Cách $1$: Có $12k$ cách chọn $A$ , sau đó có $3k+6$ người bắt tay với $B$ nên có $3k+6$ cách , riêng với $C$ có $3k+5-t$ người bắt tay với $A$ nhưng không bắt tay với $B$ .Vậy có $12k(3k+6)(3k+5-t)$ ( $t$ là số người bắt tay chung với cả hai người). Cách $2$: Có $12k$ cách chọn $B$ , và $12k-1-(3k+6)=9k-7$ cách chọn $C$ , riêng $A$ có thể chọn $t$ cách. Vậy có $(3k+6)(3k+5-t)=t(9k-7)$ ,để $t$ nguyên thì $k=3$ dẫn đến có $36$ người. $\boxed{\text{Bài toán 3}}$Giả sử các tập $A_{1},...A_{k}$ là tập con của $[10]$ với $[n]$ là tập $[n]$ số tự nhiên đầu tiên (khác $0$) thỏa mãn các điều kiẹn $i)$ Với mọi $i$ thì $|A_{i}|=5$. $ii)$ Giao hai tập bất kì không quá $2$. Tìm max của $k$? Spoiler: Lời giải Dưới đây là bảng cho trường hợp $k=6$. Do đó $k\ge 6.$ Xét với $k\ge 7$. Gọi $d(i)$ là số tập chưa phần tử $i$. Khi đó $\sum_{i=1}^{10}d_i=\sum_{i=1}^{k}\left | A_i \right |=5k\geq 35$ $\Rightarrow \exists i_0:d_{i_0}\ge 4$ WLOG đó là các tập $A_1,A_2,A_3,A_4$ $\Rightarrow \left | A_1\cap A_2\cap A_3\cap A_4 \right |=1\Rightarrow \left | A_i\cap A_j\cap A_k \right |\geq \left | A_1\cap A_2\cap A_3\cap A_4 \right |=1,\forall 1\le i,j,k\le 4$. Do đó $$10=\left | A_1\cup ...A_k \right |\geq \left | A_1\cup A_2\cup A_3\cup A_4 \right |=\sum \left | A_i \right |-\sum \left | A_i\cap A_j \right |+\sum \left | A_i\cap A_j\cap A_k \right |-\left | A_1\cap A_2\cap A_3\cap A_4 \right |\ge 4.5-C_4^2.2+(C_4^3-1).1=11$$ Điều trên vô lí nên $k=6$ là giá trị cần tìm. $\boxed{\text{Bài toán 4}}$ Xét dãy số như sau:$x_1=1$ với $i\ge 2$ thì $x_i$ nhận được từ $x_{i-1}$ bằng cách đổi (trong cách viết số $x_{i-1}$) $1\rightarrow 01,0\rightarrow 1$.Làm như vậy ta nhận được dãy $1,01,101,01101,..$.Trong dãy trên gọi $a_n$ là vị trí của chữ số $1$ thứ $n$,$b_n$ là vị trí của chữ số $0$ thứ $n$ $\left ( a_1=1,b_1=2,a_2=3,a_3=4,b_2=5,a_4=6,b_3=7,... \right )$. Tìm công thức xác định $a_n,b_n$. Spoiler: Lời giải Gọi $k_{n}$ là số số $0$ đứng trước số $1$ thứ $n$ , hiển nhiên $a_{n}=n+k_{n}$ Chữ số $0$ thứ $n$ được chuyển từ chữ số $1$ thứ $n$ , chứ số $1 \to 01 \to 101$ . Trước chữ số $1$ thứ $n$ có $k_{n}$ chữ số $0$ . Từ đó $b_{n}=k_{n}+2n$ nên $b_{n}-a_{n}=n$ Định lý $Beatty$ , hai số $\alpha , \beta$ thỏa $\frac{1}{\alpha}+\frac{1}{\beta}=1$ , thế thì đặt $S(a)=([na]|n \in Z)$ ta có $S(\alpha)$ hợp với $S(\beta)$ vét hết tập các số nguyên dương $N^{*}$ Đinh lý này có liên quan đến rất nhiều bài toán dạng dạng này , các bạn nên tìm hiểu chứng minh Để ý rằng hai dãy $(a_{n})$ và $(b_{n})$ đều tăng , mỗi số nguyên dương xuất hiện một lần trong dãy , ta viết lại như sau $i$ ta có $a_{1}=1$ $ii b_{n}-a_{n}=n$ $iii a_{n}$ là số nhỏ nhất không thuộc tập $(a_{1},...a_{n-1},b_{1},...b_{n-1})$ Từ đó suy ra mỗi số nguyên dương xuất hiện đúng $1$ lần ở $1$ trong hai dãy $(a_{n})$ hoặc $(b_{n})$ và hai dãy này xác định duy nhất Theo cái định lý Beatty kia thì ta sẽ tìm $a_{n},b_{n}$ dưới dạng $a_{n}=[nu],b_{n}=[nv]$ , ta cứ tìm như thế này nếu nó thỏa mãn thì nó đúng vì nó xác định duy nhất mà . Trong đó $\frac{1}{u}+\frac{1}{v}=1$ Lại có $n=n+[nu]-[nu]=[n(u+1)]-[nu]$ cần có $u+1=v$ Vậy tức là $u$ thỏa mãn $\frac{1}{u}+\frac{1}{u+1}=1$ Từ đó tìm được $(a_{n},b_{n})=([\frac{1+\sqrt{5}}{2}n],[\frac{1+3\sqrt{5}}{2}n])$ $\boxed{\text{Bài toán 5}}$ Cho $n$ hòn sỏi được đặt vào $n$ điểm trên 1 hình tròn. Mỗi lần ta dịch chuyển 2 hòn sỏi , mỗi hòn sỏi được dịch chuyển vào 1 trong 2 điểm mà nằm kề với hòn sỏi đó nhưng chiều dịch chuyển của 2 hòn sỏi đó ngược nhau (có 2 hướng dịch chuyển là cùng và ngược chiều kim đồng hồ). Ta muốn dịch chuyển tất cả các hòn sỏi vào 1 điểm. CMR: a/ Ta có thể đạt được mục đích nếu $n$ lẻ b/ Ta không thể đạt được mục đích nếu $n$ chẵn Spoiler: Lời giải Đánh số các điểm là $1,2,...,n$ , ta gọi giá trị hình tròn này là tổng các số dạng $a.b$ trong đó $a$ là vị trí số viên sỏi nằm ở vị trí thứ $b$ Dễ thấy đây là bất biến và bằng $\frac{n(n+1)}{2}$ khi mà đưa được hết vào một ô thì tức là có số $t$ mà $tn=\frac{n(n+1)}{2}\Leftrightarrow 2t-1=n$ hay $n$ lẻ Khi $n$ lẻ thì số các ô chứ sỏi không tăng ,nên một lúc nào đó sẽ về một .
$\boxed{\text{Bài toán 6}}$ Với số nguyên $m>3$ gọi $T_{m}$ là số dãy $(a_{1},a_{2},...a_{m})$ thỏa mãn $1)$ Với mọi $i=1,2,...,m$ thì $a_{i} \in (1,2,3,4)$ $2)$ $a_{1}=a_{m}=1<a_{2}$ $3)$ Với mọi $i=3,4...,m$ thì $(a_{i-1}-a_{i})(a_{i-2}-a_{i})$ khác $0$ Tìm công thức tổng quát của dãy $(T_{n})$ và chứng minh tồn tại dãy $(g_{n})>0$ nguyên thỏa mãn $|T_{n}-g_{n}|<2\sqrt{g_{n}}$ với mọi $n$ Spoiler: Lời giải Ta có $T_{4}=T_{5}=T_{6}=6$ Xét với $n>6$ ta có số bộ $(1,a_{2},...,a_{n},1)$ thỏa mãn đk $1,2,3$ bằng số bộ $(1,a_{2},....,a_{n-2},a_{n-1},1)$ với $a_{n-2}$ khác 1 thỏa 1,2,3 cộng với số bộ $(1,a_{2},....,1,a_{n-1},a{n},1)$ thỏa đk $1,2,3$ nên $T_{n+1}=T{n}+4T_{n-2}$ với $n\geq 6$. $\boxed{\text{Bài toán 7}}$ Cho lưới vuông kích thước $2n\times 2n$, chứa các ô vuông đơn vị trắng. Trong một nước đi một người có thể đổi màu của ba ô liên tiếp trong cùng một hàng hoặc một cột, với quy ước trắng thành đen và đen thành trắng. Xác định tất cả số nguyên dương $n\geq 2$, sao cho với hữu hạn nước đi, ta có thể thu được một bàn cờ vua. Spoiler: Lời giải Xét $n$ chia hết cho 3, khi đó chia bảng $2n\times 2n$ thành các bảng $3\times 3$. Từ mỗi bảng $3\times 3$ đó có thể tạo được 1 bàn cờ vua $3\times 3$ để ghép lại thành 1 bàn cờ vua $2n\times 2n$ Xét $n$ không chia hết cho 3, giả sử bảng $2n\times 2n$ ban đầu có thể biến đổi thành 1 bàn cờ vua. Nếu thế thì khi biến đổi được bảng về 1 bảng cờ vua thì luôn có 2 trong 4 góc bảng màu trắng (Vì $2n$ là số chẵn). Giả sử góc trên cùng bên trái màu trắng sau khi ta lập được 1 bàn cờ vua. Ta sẽ đánh số 1,2,3 vào các ô của bảng thoả mãn điều kiện: -Ô bên trái trên cùng đánh số 1 -Ô kề trái những ô đánh số 1,2,3 thì được đánh số lần lượt là 2,3,1. Nếu như ô cuối của hàng được đánh số 1,2,3 thì ô đầu tiên của hàng bên dưới hàng đó được đánh số lần lượt là 2,3,1. Vì $n$ không chia hết cho 3 nên 3 ô liên tiếp nằm trên cùng 1 hàng hoặc cột được đánh cả 3 số 1,2,3. Vì vậy mỗi lần đổi màu thì số ô đen được đánh dấu số 1 hoặc là tăng lên 1, hoặc là giảm 1. Tương tự với các ô đánh số 2,3. Vì vậy số các ô được đánh số 1,2,3 sau lần đổi màu thứ $n+1$ lần lượt khác tính chẵn lẻ với số các ô được đánh số 1,2,3 sau lần đổi màu thứ $n$.Vì vậy tại mọi thời điểm, số các ô dược đánh số 1,2,3 luôn cùng tính chẵn lẻ với nhau. Nhưng nếu xét bàn cờ vua đã cho,vì ô trên cùng bên trái màu trắng nên số các ô được đánh số 1 là $\frac{2n^2-2}{3}$, số các ô được đánh số 2 và 3 là $\frac{2n^2-2}{3}+1$. 3 số này không cùng tính chẵn lẻ nên suy ra giả sử sai $\boxed{\text{Bài toán 8}}$ Anne và Alice ở 2 phòng khác nhau. Alice đặt 13 quân bài từ Át đến K vào 14 ô trống nằm trên một đường tròn và có 1 ô không đặt lá bài nào, Anne không thể thấy được Alice sắp xếp thế nào. Mỗi lượt Anne sẽ gọi tên 1 lá bài. Nếu lá bài đó nằm cạnh ô trống thì Alice sẽ dịch chuyển lá bài đó về phía ô trống, còn nếu không thì không làm gì cả.Sau 1 số bước thì Anne sẽ dùng hỏi bài. a/ Anne có một cách nào đó để chắc chắn sau khi dừng hỏi bài thì tất cả các quân bài không còn nằm ở vị trí ban đầu của nó nữa không? b/ Anne có một cách nào đó để sau chắc chắn sau khi dừng hỏi bài thì quân Át không nằm cạnh ô trống không? Spoiler: Lời giải a/ Anne có thể gọi tên bài để đạt được mục đích: cô sẽ gọi $13$ lần, mỗi lần sẽ gọi lần lượt tên các lá bài từ Át đến K.Xét 1 lần gọi bất kì, không mất tính tổng quát, giả sử quân bài đầu tiên được di chuyển di chuyển theo chiều kim đồng hồ thì lúc đó quân bài thứ 2 được di chuyển là quân bài nằm cạnh ô trống và khác quân bài thứ nhất. Vì vậy quân bài đó sẽ di chuyển theo chiều kim đồng hồ, tương tự với lá bài thứ 3,4,.... Vì vậy mỗi quân bài được di chuyển sau mỗi lần đọc bài thì sẽ di chuyển theo 1 chiều nhất định. Xét sau lần đọc 1, xét 2 quân bài $a$,$b$ nằm cạnh ô trống. Nếu quân $b$ nằm bên phải, $a$ nằm bên trái ô trống thì nghĩa là trong lần đọc đầu, quân $a$ được di chuyển và quân $b$ không được di chuyển. Tất nhiên là quân $b$ được đọc trước $a$ vài nếu không thì nó sẽ nằm bên phải ô trống. Vì quân $b$ đọc trước $a$ nên trong lần đọc thứ 2 thì nó sẽ di chuyển về phía ô trống. Vì vậy sau mỗi lần đọc, có ít nhất $1$ quân không được di chuyển từ những lần trước được phép di chuyển theo chiều kim đồng hồ. Vì có $13$ lần đọc nên cả $13$ lá bài đều được di chuyển theo chiều kim đồng hồ ít nhất $1$ lần và vì trong mỗi lần, mỗi quân bài chỉ di chuyển tối đa 1 lần nên trong cả $13$ lần, $13$ quân bài di chuyển theo chiều kim đồng hồ nhiều nhất $13$ lần và ít nhất $1$ lần nên sau $13$ lần đọc thì các quân bài sẽ không còn ở vị trí cũ. b/ Anne không thể đạt được mục đích nếu không có may mắn. Thât vậy nếu Alice sắp xếp bộ bài sao cho quân Át nằm cạnh ô trống, gọi đó là trạng thái 0 và Anne đưa Alice 1 tờ giấy ghi những lá bài mình sẽ gọi theo thứ tự nhất định từ trái sang phải cho đến khi dừng gọi. Alice sẽ ghi lại các quân bài đó trên bảng theo thứ tự ngược lại ( ví dụ như nếu Anne ghi $A,5,Q,K$ thì Alice sẽ ghi $K,Q,5,A$) và thực hiện các bước: Gọi $n$ là số các lá bài được ghi trên giấy. Anne sẽ nhìn lên bảng và trong bước thứ $i$, xét quân bài thứ $i$ từ trái sang phải. Nếu lúc này quân bài đó nằm cạnh ô trống thì dịch chuyển quân bài đó về ô trống, còn nếu không thì không làm gì cả và chuyển qua bước $i+1$. Gọi trạng thái $i$ là cách sắp xếp bộ bài sau bước thứ $i$ thì cuối cùng sau $n$ bước thì bộ bài sẽ đạt trạng thái $n$. Ta chứng minh rằng nếu bộ bài được sắp xếp thế này và Anne đọc đúng hững quân bài được viết trên giấy theo đúng thứ tự thì cuối cùng, quân Át sẽ nằm cạnh ô trống. Ta sẽ chứng minh rằng sau lần đọc thứ $i$ thì bộ bài của $Anne$ sẽ trở về trạng thái $n-i$. Ta thấy trong lần đọc thứ $i$ thì Anne sẽ đọc quân bài thứ $n-i+1$. Ta thấy mệnh đề hiển nhiên đúng với $i=0$ vì Anne chưa đọc lá bài nào. Giả sử mệnh đề đúng với $i=k$, xét lần đọc thứ $k+1$. Trong lần này Anne sẽ đọc quân bài thứ $n-k$ trên bảng và bộ bài của Alice đang ở trạng thái $k$. Nếu quân bài Anne đang đọc không nằm cạnh ô trống trong trạng thái $n-k$ thì trong trạng thái $n-k-1$ nó cũng vậy, vì vậy nên Alice sẽ không làm gì và bộ bài sẽ trở về trạng thái $n-k-1$. Nếu quân bài đó nằm cạnh ô trống thì trong trạng thái $n-k-1$ nó cũng nằm cạnh ô trống nhưng ngược hướng so với trạng thái $n-k$, lúc đó Alice sẽ dịch chuyển quân bài đó về ô trống và bộ bài trở về trạng thái $n-k-1$. Chứng minh quy nạp hoàn tất. Vì vậy sau $n$ lần đọc thì bộ bài trở về trạng thái 0. Nhưng trong trạng thái này quân Át nằm cạnh ô trống nên Anne không thể đạt được mục đích. Vậy cho dù Anne có đọc thế nào thì cũng có 1 cách sắp xếp bộ bài sao cho cuối cùng quân Át cũng ở cạnh ô trống $\boxed{\text{Bài toán 9}}$ Một tập hợp các số nguyên dương gọi là tốt nếu mỗi phần tử của nó đều không nhỏ hơn số phần tử của chính tập số .Gọi $a_{n}$ là số tập tốt của tập $n$ số nguyên dương đầu tiên và $b_{n}$ là số tập con của tập đó mà cứ hai phần tử bất kì hơn kém nhau ít nhất $2$ đơn vị . Tính $a_{n}-b_{n}$. Spoiler: Lời giải Xét $a_n$. Số các tập thuộc $a_n$ có $i$ phần tử là $\binom{n-i+1}{i}$ vì ta chỉ chọn các phần tử $i, i+1, ...,n$ Do đó $a_n=\sum_{i<n-i+1}\binom{n-i+1}{i}$ Xét $b_n$. Ta đếm số các tập thuộc $b_n$ có $i$ phần tử. Gọi các phần tử đó là $x_1 < x_2 < ... <x_i$ thì theo đề bài $1 \leq x_1 < x_2 - 1 < x_3 -2 ... <x_i-(i-1)\leq n -i +1$. Đặt $y_i=x_i-(i-1)$ thì số tập thuộc $b_n$ có $i$ phần tử bằng số các dãy $y_1,y_2,..,y_i$ mà $1\leq y_1 < y_2 <...<y_i \leq n-i+1$ hay bằng $\binom{n-i+1}{i}$. Do đó $b_n=\sum_{i<n-i+1}\binom{n-i+1}{i}$ hay ta có $a_n=b_n$. $\boxed{\text{Bài toán 10}}$ Xét một số tự nhiên được biểu diễn trong hệ nhị phân. Ta gọi một khoảng cách nhị phân là một khoảng gồm các số $0$ liền nhau và ở hai đầu của nó là hai số $1$. Ví dụ số $548=1000100100_{2}$ có hai khoảng cách nhị phân là $000$ và $00$. Hỏi từ $1$ tới $4095$ có bao nhiêu số mà độ dài các khoảng cách nhị phân của nó nhỏ hơn hoặc bằng $3$? Spoiler: Lời giải Trước tiên ta để ý rằng $4095=111111111111_{2}$ là số lớn nhất có $12$ chữ số trong hệ nhị phân Nên ta đặt một số từ $1$ đến $4095$ là $\overline{a_{1}a_{2}....a_{12}}_{(2)}$ Gọi số số $1$ là $i$ thì có $12-i$ số $0$ , khoảng cách giữ hai số một là một trong $4$ số $0,1,2,3$ Xét dạng sau $1....1.....1....1....1....$ Trong đó có $i>1$ số $1$ , tổng các khoảng cách bằng tổng số các số $0$ là $12-i$ Vậy ta tìm số nghiệm nguyên của phương trình $x_{1}+x_{2}+....x_{i}=12-i$ ( vì lưu ý là nó không bắt đầu từ $0$) Trong đó $0 \leq x_{i} \leq 3$ Quanh đi quẩn lại vẫn phải đệ quy sorry nãy làm sai , gọi số nghiệm của $\sum_{i=1}^{m}x_{i}=n$ là $S(m,n)$ với $0\leq x_{i} \leq 3$ Xét số $x_{1}=0$ thì số nghiệm là $S(i-1,12-i)$ Tương tự suy ra $S(i,12-i)=S(i-1,12-i)+S(i-1,11-i)+S(i-1,10-i)+S(i-1,9-i)$ Quy ước nếu $n>m$ thì $C_{m}^{n}=0$ Vậy đáp số là $\sum_{i=1}^{12}S(i,12-i)$ .
$\boxed{\text{Bài toán 11}}$ Trên $1$ đoạn thẳng từ trái sang phải có đặt $21$ hộp gỗ, trong mỗi hộp gỗ có đặt $1$ vài hòn bi. Biết rằng số hòn bi trong mỗi hộp gỗ nhận $1$ trong các giá trị từ $1$ đến $21$ và không có $2$ hộp nào chứa cùng số bi. Mỗi bước ta sẽ chọn $2$ hộp gỗ bất kì và nếu $1$ hộp chứa nhiều bi hơn hộp kia thì ta sẽ chuyển từ hộp nhiều bi hơn sang hộp ít bi hơn $1$ số bi đúng bằng số bi mà hộp ít bi hơn có trước khi chuyển bi. Hỏi có thể luôn chuyển được bi sao cho sau các bước chuyển đó,$ 21$ hộp có số bi nhận $1$ trong các giá trị từ $1$ đến $21$, không có $2$ hộp nào có cùng số bi và số bi của các hộp từ trái sang phải sắp xếp theo thứ tự tăng dần? Spoiler: Lời giải Với mỗi số $2\leq a\leq 21$ thì ta sẽ gọi $b$ là 1 số đối của $a$ nếu -)$b<a$ -)Xét hộp $A$ chứa $a$ viên bi và hộp $B$ chứa $b$ viên bi. Sau một số bước chuyển bi giữa 2 hộp này thì hộp $A$ chứa $b$ viên bi và hộp $B$ có $a$ viên bi. Nếu $a$ là số chẵn thì $a$ có 1 số đối là $\frac{a}{2}$ Nếu $a$ là số lẻ thì ta sẽ xây dừng cặp $(a;b)$ bới $b$ là số đối của $a$ như sau: $(3;2),(5;4),(7;4),(9;8),(11;4);(13;4);(15;4);(17;16);(19;8);(21;4)$ Ta sẽ chứng minh bài toán tổng quát hơn: Với $(a_{1};a_{2};...;a_{n})$ là 1 hoán vị của $(1;2;...;n)$ với $n\leq 21$ thì ta có thể thực hiện chuyển đổi giữa các hộp sao cho hộp thứ $i$ từ trái sang phải chứa $a_i$ viên bi. Mệnh đề đúng với $n=1,2$, giả sử mệnh đề đúng với $n=k<21$, xét $n=k+1$. Giả sử lúc đầu hộp $x$ chứa $k+1$ viên bi và 1 hộp thứ $y$ với $y\leq 21$ bất kì. Khi đó với $k$ hộp còn lại, theo mệnh đề quy nạp thì ta có thể chuyển bi sao cho với $b$ là số đối của $k+1$ thì hộp $y$ chứa $b$ viên bi. Ta thực hiện chuyển đổi liên tiếp giữa 2 hộp này thì cuối cùng hộp $y$ chứa $k+1$ viên bi, hộp $x$ chứa $b$ viên bi. Cho $y$ chạy từ $1$ đến $k+1$ thì lúc đó ta có thể di chuyển bi sao cho tất cả mọi hộp đều có thể chứa $k+1$ viên bi, hoán vị $k$ hộp còn lại ta sẽ tạo ra được tất cả các hoán vị của $(1;2;...;k+1)$. Vậy mệnh đề đúng với $n=k+1$, vì vậy mệnh đề đúng với $n=21$. Vì $(1;2;...;21)$ là 1 hoán vị của $(1;2;...;21)$ nên ta có thể chuyển bi sao cho các hộp chứa số bi thoả mãn. $\boxed{\text{Bài toán 12}}$ (USAMO 2016) Cho $n,k$ là hai số nguyên, $n\geq k\geq 2$. Bạn tham gia vào một trò chơi với một phù thuỷ Phù thuỷ có $2n$ lá bài, với mỗi $i=1,2,...,n$ thì có đúng hai lá bài cùng được đánh số là $i$. Lúc đầu, phù thuỷ sắp úp tất cả lá bài trên một hàng, thứ tự bất kỳ. Về phần bạn, bạn sẽ lặp lại các thao tác sau: chỉ vào $k$ lá bài bạn muốn chọn, phù thuỷ sẽ lật ngửa lên hộ bạn. Nếu lật lên, có hai tấm thẻ cùng được đánh 1 số, bạn thắng, game sẽ kết thúc. Nếu ngược lại, phù thuỷ sẽ hoán vị $k$ lá bài đó và lật úp chúng lại. Mỗi lần bạn làm vậy là một bước đi. Và bạn sẽ lặp lại thao tác trên. Ta gọi game này là thành công nếu tồn tại $m$ nguyên dương nào đó và một chiến thuật nào đó ở tối đa $m$ bước đi, không quan trọng việc phù thuỷ xáo trộn bài của bạn. Hỏi với $n$ và $k$ nào thì bạn có thể chiến thắng? Spoiler: Lời giải Trước tiên, ta chứng minh với $k=n$ thì sẽ không có chiến thuật đảm bảo thắng. Khi $k=n$ thì trường hợp xấu nhất ở lần chọn bài đầu tiên là ta chọn đúng $n$ lá bài mà các số trên đó là một hoán vị của $(1,2,...,n)$. Giả sử ở lần tiếp theo, ta chọn $l$ lá bài cũ và $n-l$ lá bài mới, khi đó tồn tại ít nhất 1 cách phù thuỷ xáo bài sao cho $n$ lá bài ở lần chọn này vẫn là một hoán vị của $(1,2,...,n)$. Dẫn tới, ở mọi lần chọn bài, ta đều có thể chọn phải $n$ lá bài mà các số trên đó là một hoán vị của $(1,2,...,n)$, hay nói cách khác là ta không thể đảm bảo có thể thắng trong hữu hạn lần chọn. Ta sẽ chứng minh tiếp, với $2\le k<n$ thì ta sẽ có chiến thuật thắng bất chấp mọi cách xáo trộn bài của phù thuỷ. Đánh số các quân bài từ $1$ đến $2n$. Giả sử mỗi lần bốc bài dưới đây đều rất "đen đủi" tức là không có 2 lá bài nào trong $k$ lá bài được chọn ghi cùng 1 số. Đầu tiên ta sẽ bốc $k$ lá bài $(1,2,...,k)$ thì ta sẽ biết được tập hợp các số ghi trên các quân bài này. Sau đó, ta sẽ bốc $k$ lá bài $(2,3,...,k+1)$ thì ta sẽ biết được giá trị ghi trên lá bài thứ $k+1$ và từ đó ta sẽ biết được $k+1$ lá bài đầu tiên chứa các số như thế nào (cho dù xáo trộn các lá bài thì tập các số này vẫn không đổi). Cứ tiếp tục bốc $k$ lá bài $(i,i+1,...,i+k-1)$ với $i$ nhận giá trị lần lượt từ $3$ đến $2n-k$, khi đó ta sẽ biết được $2n-1$ lá bài đầu tiên chứa các số như thế nào. Từ đó ta sẽ suy ra được giá trị ghi trên lá bài thứ $2n$. Bắt đầu lại quá trình trên một lần nữa theo cách tương tự, ta sẽ xác định được số ghi trên lá bài thứ $2n-1$. Cứ như vậy, ta sẽ xác định được giá trị ghi trên $2n-k$ lá bài từ $k+1$ đến $2n$. Theo nguyên lý Dirichlet thì ta sẽ chọn được 2 lá bài ghi cùng 1 số, như vậy lần chọn cuối cùng này ta hoàn toàn có thể chọn được $k$ lá bài mà có 2 lá bài ghi cùng 1 số. $\boxed{\text{Bài toán 13}}$ Cho $n$ là số nguyên dương, $n\ge 2$. Xét tập $X_n$ gồm các điểm nguyên $(x;y)$ trên mặt phẳng tọa độ $Oxy$ với $1\le x,y\le n$. Gọi $S_k$ là số cặp điểm là cặp đỉnh chung của $k$ hình vuông có các đỉnh thuộc $X_n$ với $k=\overline{0;3}$. Chứng minh rằng: $S_0=S_2+2S_3$. Spoiler: Lời giải Gọi ${{P}_{n}}$ là số hình vuông có các đỉnh thuộc ${{X}_{n}}$. Nhận xét: từ một hình vuông cạnh $s$ có cạnh song song với trục tọa độ, ta có thể dựng được thêm $s-1$ hình vuông nội tiếp. Mà có ${{(n-s)}^{2}}$ hình vuông cạnh $s$ có cạnh song song với trục tọa độ. $\displaystyle \Rightarrow {{P}_{n}}=\sum_{s=1}^{n-1}{{{(n-s)}^{2}}}s=\frac{{{n}^{2}}({{n}^{2}}-1)}{12}=\frac{C_{{{n}^{2}}}^{2}}{6}$ Mỗi hình vuông có 6 đoạn nối các cặp đỉnh nên có $6{{P}_{n}}$ đoạn nối các cặp đỉnh. Số cặp điểm là:${{S}_{0}}+{{S}_{1}}+{{S}_{2}}+{{S}_{3}}=C_{{{n}^{2}}}^{2}=6{{P}_{n}}$. Số cạnh và số đường chéo của ${{P}_{n}}$ hình vuông là: ${{S}_{1}}+2{{S}_{2}}+3{{S}_{3}}=6{{P}_{n}}$. Từ đó suy ra: ${{S}_{0}}={{S}_{2}}+2{{S}_{3}}$. $\boxed{\text{Bài toán 14}}$ Có 2 con châu chấu nằm tại 2 điểm nguyên trên mặt phẳng toạ độ. Mỗi lần thổi còi, có đúng 1 con châu chấu nhảy tới một điểm nguyên khác sao cho khoảng cách giữa 2 con châu chấu luôn không đổi. Hỏi sau hữu hạn lần thổi còi, 2 con châu chấu có thể đổi chỗ cho nhau được không? (mỗi con sẽ nhảy tới vị trí ban đầu của con kia) Spoiler: Lời giải Đánh dấu màu xanh tất cả vị trí mà con châu chấu đầu tiên nhảy được tới, màu đỏ các vị trí mà con thứ 2 có thể nhảy được tới. Gọi $d$ là khoảng cách của 2 con châu chấu, đặt $d^2=2^tq$ ($q$ là số lẻ). Xét 1 thời điểm bất kì con châu chấu đầu tiên ở vị trí $A(x_1;y_1)$, con thứ 2 ở vị trí $B(x_2;y_2)$. Giả sử con châu chấu đầu tiên nhảy từ $A$ đến $C(x_3;y_3)$, ta có $(x_1-x_2)^2+(y_1-y_2)^2=(x_3-x_2)^2+(y_3-y_2)^2=d^2=2^tq$. Đặt $x_1-x_2=a_1; y_1-y_2=b_1; x_3-x_2=a_2; y_3-y_2=b_2$ Nếu $t$ là số chẵn, đặt $t=2n$, lúc đó cả $a_1;a_2;b_1;b_2$ đều chia hết cho $2^n$, vì vậy $(a_1-a_2)^2+(b_1-b_2)^2$ chia hết cho $2^{2n+1}$ hay $(x_1-x_3)^2+(y_1-y_3)^2$ chia hết cho $2^{t+1}$ Nếu $t$ là số lẻ, đặt $t=2n+1$, lúc đó cả $a_1;a_2;b_1;b_2$ đều chia hết cho $2^n$ nhưng không chia hết cho $2^{n+1}$. Đặt $a_1=2^na; a_2=2^nb; b_1=2^nc; b_2=2^nd$, có $a,b,c,d$ đều không chia hết cho 2 nên $(a_1-a_2)^2+(b_1-b_2)^2=2^{2n}((a-b)^2+(c-d)^2)$ chia hết cho $2^{2n+2}$ hay chia hết cho $2^{t+1}$ ( Vì $(a-b)^2+(c-d)^2$ chia hết cho $4$) Trong cả 2 trường hợp thì $(x_1-x_3)^2+(y_1-y_3)^2$ đều chia hết cho $2^{t+1}$. Từ đó có thể chứng minh rằng bình phương khoảng cách của 2 điểm xanh bất kì trên toạ độ đều chia hết cho $2^{t+1}$. Vì vậy khoảng cách giữa 2 điểm xanh bất kì đều khác $d$. Vì vậy không có điểm nào trên toạ độ tô cả 2 màu xanh và đỏ. Cho nên con châu chấu thứ 2 không thể nào nhảy đến bất kì điểm nào mà con thứ nhất có thể nhảy đến, tương tự với con thứ nhất. Vì vậy 2 con châu chấu không thể đổi chỗ cho nhau $\boxed{\text{Bài toán 15}}$ Một ảo thuật gia với $1$ bộ bài có $52$ quân bài, có $4$ loại bài là cơ, chuồn, rô, tép, mỗi loại bài có $13$ quân bài. Đầu tiên nhà ảo thuật sẽ đưa bộ bài cho khán giả xào bài, tất cả các quân bài sau khi được xào lại được đặt úp, chồng lên nhau. Trợ thủ của nhà ảo thuật được quyền xem thứ tự các quân bài sau đó viết $1$ trong $2$ số $0$ hoặc $1$ vào mặt sau mỗi quân bài nhưng không được sắp xếp lại bộ bài và cũng không được nói cho nhà ảo thuật biết thứ tự của bộ bài. Mỗi lượt nhà ảo thuật sẽ đoán loại bài của lá bài trên cùng của xấp bài, sau đó loại nó ra khỏi bộ bài. Nhà ảo thuật cứ tiếp tục như thế trong $52$ lượt. Hỏi có chiến lược nào giúp anh ta đoán được đúng loại bài của ít nhất $30$ quân bài không?
$\boxed{\text{Bài toán 16}}$ Trên mặt phẳng cho 2016 điểm, khoảng cách giữa các điểm này đôi một khác nhau. Nối mỗi điểm trong số 2016 điểm này với điểm gần nhất. Với cách nối đó có thể nhận được gấp khúc khép kín hay không Spoiler: Lời giải Giả sử dựng được đường gấp khúc thỏa đề. Do khoảng cách giữa các điểm đã cho là đôi một khác nhau nên theo nguyên lí cực hạn, trong các đoạn thẳng cấu thành đường gấp khúc ta luôn chọn được đoạn dài nhất, giả sử là đoạn $AB.$ Giả sử $A$ được nối với $C$ khác $B,$ còn $B$ được nối với $D$ khác $A.$ Do tính dài nhất của đoạn $AB,$ ta suy ra $AB>AC$ và $AB>BD.$ Như vậy $A$ không phải là điểm gần $B$ nhất và $B$ không phải là điểm gần $A$ nhất, suy ra $A$ và $B$ không được nối với nhau, mâu thuẫn. Vậy không nhận được gấp khúc khép kín với cách dựng thỏa đề. $\boxed{\text{Bài toán 17}}$ Có n người ngồi quanh một bàn tròn. Họ cùng chơi một trò chơi như sau: tại mỗi lượt, hai người nào đó ngồi cạnh nhau trên bàn sẽ đổi chỗ cho nhau. Hỏi phải sau bao nhiêu bước thì ta đạt được trạng thái mà tại đó, 2 người bất kì ngồi cạnh nhau ban đầu vẫn ngồi cạnh nhau nhưng theo chiều ngược lại ? Spoiler: Lời giải Đánh số n người đó theo các số từ 1 đến n theo 1 chiều xác định, khi đó chiều ngược lại: $\Rightarrow 2\rightarrow n,3\rightarrow n-1,...$ Chia n người đó làm 2 phần sao cho độ dài cung từ vị trí ban đầu đến vị trí cần tới(ngược lại) là nhỏ nhất thì ta cần sắp dãy $q,q+1,...,k-1,k\rightarrow k,k-1,...q+1,q$ Với k=2 thì hiển nhiên cần ít nhất 1 lần đổi chỗ Giả sử với k=m ta cần ít nhất a lần đỗi chỗ thì với k=m+1 ta cần ít nhất a+m-1 lần vì khi đó $k \rightarrow q$ cần m-1 lượt và khi đó ta phải sắp dãy k-1 số còn lại giống với TH k=m và vì khi $k \rightarrow q$ vị trí tương đối của k-1 số còn lại không đổi nên dù thay đổi thứ tự di chuyển k thì ta vẫn cần ít nhất a lần để thực hiên sắp xếp dãy còn lại Vậy Với k=m thì ta cần ít nhất số lượt là : $\sum_{1}^{m-1}= \frac{m(m-1)}{2}$ Với n lẻ ta được 2 phần là $\frac{n+1}{2},\frac{n-1}{2}\rightarrow a= \frac{(n-1)^2}{4}$ Với n chẵn ta được 2 phần là $\frac{n-2}{2},\frac{n+2}{2}\rightarrow a= \frac{(n-1)^2+3}{4}$ $\boxed{\text{Bài toán 18}}$ Trong $n$ giác lồi kẻ tất cả các đường chéo. Biết rằng không có ba đường chéo nào đồng quy tại một điểm. Hỏi đa giác lồi được chia ra thành bao nhiêu phần? Các đường chéo cắt nhau tại bao nhiêu điểm? Spoiler: Lời giải Số giao điểm: Xét một tứ giác bất kỳ lập thành từ $4$ đỉnh của đa giác, do đa giác lồi nên giao điểm 2 đường chéo của tứ giác này nằm trong đa giác và cũng là giao điểm 2 đường chéo của đa giác. Ngược lại với $1$ giao điểm của $2$ đường chéo bất kỳ trong đa giác thì $2$ cặp đầu mút của $2$ đường chéo này lập thành $1$ tứ giác có $4$ đỉnh là $4$ đỉnh phân biệt của đa giác. Tóm lại ta lập được song ánh giữa số giao điểm và số tứ giác tạo bởi $4$ đỉnh phân biệt của đa giác. $\Rightarrow$ Số giao điểm là $C^4_n$. Số miền: Ta xuất phát từ đầu với $1$ miền (chính là $n$-giác) và lần lượt nối các đường chéo. Mỗi đường chéo chia đa giác thêm $1$ phần, và mỗi khi nó giao với đường chéo khác nó lại chia đa gíc thêm $1$ phần nữa. Dễ tính được số đường chéo là: $C^2_n-n$. $\Rightarrow$ Số miền là: $1+C^2_n-n+C^4_n$. $\boxed{\text{Bài toán 19}}$ Gọi an là số các xâu nhị phân độ dài n không chứa chuỗi con $010$, $b_n$là số các xâu nhị phân độ dài n không chứa chuỗi con $0011$ hoặc 1100. Chứng minh rằng $b_{n+1}=2a_n$ với mọi $n$ nguyên dương. Spoiler: Lời giải Xét một xâu nhị phân bất kì $\left \{ x_1, x_2,...,x_n \right \}$. Ta xây dựng một xâu nhị phân $\left \{ y_1, y_2,...,y_{n+1} \right \}$ sao cho $y_1 =0$ và $y_k = x_1 + x_2 +...+ x_k(mod2)$ Rõ ràng, xâu $\left \{ x_1, x_2,...,x_n \right \}$ có dạng $a_n$ khi và chỉ khi $\left \{ y_1, y_2,...,y_{n+1} \right \}$ có dạng $b_n$. Nói cách khác đó là một song ánh biến các xâu có dạng $a_n$ thành các xâu có dạng $b_{n+1}$ bắt đầu bằng $0$. Với mỗi xâu $\left \{ y_1, y_2,...,y_{n+1} \right \}$, ta thay các kí tự 1 bởi 0 và 0 bởi 1, ta được một xâu khác cũng có dạng $b_{n+1}$ nhưng bắt đầu bởi $1$. Từ đó cho ta: $b_{n+1} = 2a_n$. $\boxed{\text{Bài toán 20}}$ Trên bảng ô vuông $20$x$20$ mỗi ô có $1$ quân cờ. $A$ chọn một số thực $d$ và $B$ phải đưa mỗi quân cờ đi tới ô cách ô ban đầu nó đứng một khoảng cách ít nhất là $d$ (khoảng cách giữa $2$ ô được tính theo khoảng cách tâm của $2$ ô đó) và mỗi ô chỉ có thể có $1$ quân cờ. Hỏi với điều kiện gì của $d$ thì $B$ có thể thao tác thoả mãn điều kiện trên? Hỏi tương tự với bảng $21$x$21$ Spoiler: Lời giải $*$ TH bảng $20 \times 20$: Xét toạ độ các ô (được tính ở tâm ô) là $(i, j) \forall 1 \le i, j \le 20$. Xét ô $(10, 10)$, giả sử sau bước chuyển quân cờ ở ô này chuyển đến ô $(a,b) (1 \le a,b \le 20, a, b$ không đồng thời bằng $10)$, khi đó khoảng cách giữa $2$ ô là: $\sqrt{(a-10)^2+(b-10)^2} \ge d$. Do $1 \le a,b \le 20$ nên $|a-10| \le 10, |b-10| \le 10 \Rightarrow d \le 10\sqrt{2}$. Cách chuyển quân: Các quân ở các ô $(i, j)$ đến ô $(i', j')$ với $\begin{cases} i'=i+10 & \text{ if } i \le 10\\ i'=i-10 & \text{ if } i > 10 \end{cases}$. $*$ TH bảng $21 \times 21$: Lập luận tương tự với ô $(11,11)$,
$\boxed{\text{Bài toán 21}}$ Cho một bảng ô vuông kích thước $m \times n$. Người ta muốn tô màu các ô vuông con của bảng, mỗi ô vuông con chỉ được tô bởi 1 trong 2 màu Xanh hoặc Đỏ theo quy tắc sau: i) Tất cả các ô vuông con ở cạnh của bảng đều được tô màu Đỏ. ii) Không có hình vuông kích thước $2 \times 2$ nào của bảng mà $4$ ô vuông con được tô cùng màu. iii) Không có hình vuông kích thước $2 \times 2$ nào của bảng mà hai ô ở mỗi đường chéo đều được tô cùng màu. Hỏi người ta có thể thực hiện cách tô màu như trên trong các trường hợp với bảng ô vuông kích thước: $a) 2012 \times 2013?$ $b) 2012 \times 2014?$ $\boxed{\text{Bài toán 22}}$ Trong 1 dãy nhà vô hạn ,được đánh số :$1,2,3,…$ mỗi phòng có thể có người hoặc không có người ,nhưng số người là hữu hạn .Mỗi buổi sáng 2 người ở 2 phòng liên tiếp $k,k+1$ nào đó sẽ thực hiện việc chuyển phòng như sau : i)Người ở phòng $k$ chuyển sang phòng $k-1$ $(k>1)$ ii)Người ở phòng $k+1$ chuyển sang phòng $k+2$ CMR:Việc chuyển phòng chỉ ra hữu hạn lần. Spoiler: Lời giải Gọi $S(n)$ là tích số thứ tự phòng của tất cả mọi người ngày thứ $n$ Như vậy ta có $\frac{S(n+1)}{S(n)}=\frac{n(n+1)}{(n-1)(n+2)}=\frac{n^{2}+n}{n^{2}+n-2}< 1$ $\Rightarrow S(n+1)<S(n)$ Như vậy $S(n)$ là một đơn biến. Do $S(n)$ giảm và $S(n)>0$ nên việc chuyển phòng sẽ dừng sau một số ngày $\boxed{\text{Bài toán 23}}$ Cho số nguyên dương n. Có bao nhiêu số chia hết cho 3, có n chữ số và các chữ số đều thuộc {3, 4, 5, 6}? Spoiler: Lời giải Gọi $a_n$ là số các số có $n$ chữ số lập từ ${3, 4, 5, 6}$ và chia hết cho 3, còn $b_n$ là số các số có $n$ chữ số lập từ ${3, 4, 5, 6}$ và không chia hết cho 3. Khi đó ta có $a_n = 2a_{n-1} + b_{n-1}(1)$ $b_n = 2a_{n-1} + 3b_{n-1}(2)$ Từ (1) suy ra $b_{n-1} = a_n – 2a_{n-1}$, thay n à n+1 thì được $b_n = a_{n+1} – 2a_n$. Thay vào (2), ta được $a_{n+1} – 2a_n = 2a_{n-1} + 3(a_n – 2a_{n-1})$ $a_{n+1} – 5a_n + 4a_{n-1} = 0$. Giải phương trình sai phân này, với chú ý rằng a1 = 2, a2 = 6, ta tìm được \[{a_n} = \frac{{{4^n} + 2}}{3}.\] $\boxed{\text{Bài toán 24}}$ Gọi $X=\left \{ 1,2,...,2003 \right \}$. Lấy số tự nhiên $n\geq 1$ và $n\leq 2003$ sao cho nếu lấy tập hợp con gồm $n$ phần tử của $X$, thì ta có thể tìm được một phần tử là lũy thừa của $2$ hoặc $2$ phần tử có tổng là lũy thừa của $2$. Chứng minh rằng: $n\geq 999$ Spoiler: Lời giải Xét tập $A=\left \{ 5, 6, 7, 12, 13, 14, 15, 21, 22, 23, 24, 28, 29, 30, 31, 37, 38, 39, 44\right \}$ và $B=\left \{n|n \in \mathbb{N}, 1025 \le n \le 2003\right \}$. Xét tập $C=A \cup B$. Dễ thấy $|C|=998$. Các phần tử trong $B$ nằm giữa $2^{10}$ và $2^{11}$ nên không thể là luỹ thừa của $2$ và $\forall x \neq y; x, y \in B$ thì $2^{11} < x+y < 2^{12}$ nên tổng $x+y$ cũng không thể là luỹ thừa của $2$. Với $x \in A$ và $y \in B$ thì $1030 \le x+y \le 2047$ nên tổng $x+y$ cũng không là luỹ thừa của $2$. Dễ kiểm tra các phần tử của $A$ không là luỹ thừa của $2$ và tổng của $2$ số bất kỳ trong số chúng cũng vậy. $\Rightarrow \forall n \le 998$ ta chỉ cần lấy một tập con $n$ phần tử của $C$ thì tập này sẽ không có phần tử nào và cũng không có tổng của $2$ phần tử nào là luỹ thừa của $2$. $\Rightarrow n \geq 999$. $\boxed{\text{Bài toán 25}}$ Trên một sân chơi có 10 em bé đứng. Biết rằng khoảng cách giữa các em bé đôi một khác nhau và mỗi em bé cầm trong tay một quả bóng (quả bóng là một trong bốn màu đỏ, vàng, lam, lục). Sau hiệu lệnh của chị phụ trách, mỗi em đưa quả bóng của mình cho bạn đứng gần nhất. Hỏi rằng có ít nhất bao nhiêu em bé còn có bóng trong tay? Spoiler: Lời giải Ta CM còn ít nhất 2 em bé có bóng. Gọi vị trí 10 em bé đứng lần lượt là $A_1 \rightarrow A_{10}$ Giả sử tồn tại cách đứng sao cho sau khi chuyển bóng thì còn đúng 1 em bé có bóng. Giả sử chỉ có em $A_1$ còn bóng. Xét các góc $\angle A_jA_1A_i (\forall 2 \le i, j \le 10, i \neq j)$, theo nguyên lý Dirichlet tồn tại 1 góc nhỏ hơn $60^o$, WLOG giả sử là $\angle A_2A_1A_3 < 60^o$. Khi đó tồn tại một trong 2 góc $\angle A_1A_2A_3$ hoặc $\angle A_2A_3A_1$ lớn hơn $60^o$ và lớn hơn $\angle A_2A_1A_3$. Giả sử $\angle A_2A_1A_3< \angle A_1A_2A_3$, khi đó $A_2A_3<A_1A_3$ do vậy $A_3$ sẽ đưa bóng cho $A_2$ chứ không phải $A_1$ (mâu thuẫn). Vậy có ít nhất 2 em còn cầm bóng. Cấu hình sau đảm bảo có đúng 2 em cầm bóng là $A_1$ và $A_6$.
$\boxed{\text{Bài toán 26}}$ (Germany 1970) Cho tập $M$ có $22222$ phần tử .Hỏi $M$ có hay không 50 tập con thoả mãn : 1/Mỗi phần tử của $M$ là phần tử của ít nhất 1 trong các tập con. 2/Mỗi tập con đều có $1111$ phần tử. 3/Với 2 tập $M_i;M_j (i\neq j)$ có ${M_i} \cap {M_j}$ 22 phần tử. Spoiler: Lời giải Gọi các phần tử của $M$ là $a_1 \rightarrow a_{22222}$. Giả sử tồn tại $50$ tập con $M_i (1 \le i \le 50)$ thoả mãn $3$ yêu cầu trên. Ta đếm số cách chọn $2$ tập $M_i, M_j (i \neq j)$ kèm theo $1$ phần tử $a_k$ thuộc $M_i \cap M_j$. Gọi số cách chọn này là $S$. Có $C^2_{50}$ cách chọn $2$ tập $M_i, M_j (i \neq j)$ và $22$ cách chọn phần tử $a_k$ thuộc $M_i \cap M_j$. $\Rightarrow S=22.C^2_{50}=26950$. Mặt khác, giả sử $a_i$ thuộc $r_i ( \forall 1 \le i \le 22222)$ tập $M_j$. Khi đó dễ CM được $$\sum_{i=1}^{22222}r_i= \sum_{i=1}^{50} |M_i|=50.1111=55550$$. Có $22222$ cách chọn phần tử $a_i$ bất kỳ, và có $C^2_{r_i}$ cách chọn 2 tập $M_j, M_k$ sao cho $a_i \in M_j \cap M_k$ (coi $C^2_1=0$). $\Rightarrow S=\sum_{i=1}^{22222} C^2_{r_i}$ $=\sum_{i=1}^{22222} \frac{r_i(r_i-1)}{2}$ $=\frac{1}{2}(\sum_{i=1}^{22222}r_i^2 - \sum_{i=1}^{22222}r_i)$ $\geq \frac{1}{2} (\frac{(\sum_{i=1}^{22222} r_i)^2}{22222}-\sum_{i=1}^{22222} r_i)$ (BĐT C-S) $=\frac{55550^2-22222.55550}{2.22222}>26950=S$ (mâu thuẫn). Vậy không tồn tại $50$ tập con của $M$ thoả mãn đề bài. $\boxed{\text{Bài toán 27}}$ Có $2n$ người xếp thành 2 hàng dọc. Hỏi có bao nhiêu cách chọn ra một số người (ít nhất 1) từ 2n người này, sao cho không có hai người nào đứng kề nhau được chọn. Hai người đứng kề nhau là hai người có số thứ tự liên tiếp trong một hàng dọc hoặc có cùng số thứ tự ở hai hàng. Spoiler: Lời giải Gọi $S_n$ là số cách chọn ra một số người từ $2n$ người xếp thành 2 hàng dọc và Tn là số cách chọn ra một số người từ $2n-1$ người xếp thành 2 hàng dọc, trong đó khuyết một chỗ ở đầu của một hàng. Ta có S1 = 2, T1 = 1. Xét 2n người xếp thành 2 hàng dọc. Ta xét các cách chọn thoả mãn điều kiện đầu bài. Xảy ra các khả năng sau : 1) Người ở vị trí số 1 được chọn : Khi đó người ở vị trí số 2 và số 3 không được chọn à Có $T_{n-1}+1$ cách chọn (+1 là do bổ sung cách chọn " không chọn gì cả" ) 2) Người ở vị trí số 2 được chọn : Tương tự, có $T_{n-1}+1$ cách chọn. 3) Cả hai người ở vị trí số 1 và số 2 đều không được chọn: Có $S_{n-1}$ cách chọn. Vậy ta có $S_n=S_{n-1}+2T_{n-1}+2$ (1). Xét $2n-1$ người xếp thành 2 hàng dọc. Ta xét các cách chọn thoả mãn điều kiện đầu bài. Xảy ra các khả năng sau : 1) Người ở vị trí số 1 được chọn : Khi đó người ở vị trí số 2 không được chọn à có $T_{n-1}+1$ cách chọn 2) Người ở vị trí số 1 không được chọn : có $S_{n-1}$cách chọn. Vậy ta có $T_n=S_{n-1}+T_{n-1}+1$ (2) Từ (1) ta suy ra $2T_{n-1} = S_n – S_{n-1} – 2, 2T_n = S_{n+1} – S_n – 2$. Thay vào (2), ta được $S_{n+1} – S_n – 2 = 2S_{n-1}+ S_n – S_{n-1} – 2 + 2$ $S_{n+1} = 2S_n + S_{n-1} +2$ Từ đây dễ dàng tìm được \[{S_n} = \frac{{{{(1 + \sqrt 2 )}^{n + 1}} + {{(1 - \sqrt 2 )}^{n + 1}} - 2}}{2}\] $\boxed{\text{Bài toán 28}}$ (APMO 1989) Chứng minh rằng một đồ thị n đỉnh, k cạnh thì sẽ có ít nhất \[\frac{{k\left( {4k - {n^2}} \right)}}{{3n}}\] tam giác. Spoiler: Lời giải Gọi $D_i$ là bậc của đỉnh $i$ nào đó. Nếu 2 đỉnh $i$ và $j$ liên thông thì tồn tại ít nhất $D_i + D_j - 2$ cạnh khác nổi đến $n-2$ đỉnh khác của đồ thị. Nên có $D_i + D_j - n$ tam giác có đỉnh là $j$ và $j$. Vậy số tam giác có chứa cạnh $ij$ được tạo thành phải tối thiểu là: $\sum_{i,j} {\frac{D_i + D_j -n}{3}}=\sum_{i,j} {\frac{D_i + D_j}{3} - \frac{nk}{3}} = \sum_{i} {\frac{D_i^2}{3} - \frac{nk}{3}}$ Vậy số tam giác tối thiểu được tạo thành là: $\sum_{i}{\frac{D_i^2}{3}} -\frac{nk}{3} \geq \frac{1}{3n}\left ( \sum_{i}{D_i} \right )^2 - \frac{nk}{3} = \frac{4k^2}{3n} -\frac{nk}{3}$ $\boxed{\text{Bài toán 29}}$ Trong một ngày chủ nhật mỗi học sinh trong bảy học sinh có ba lần đi đến hiệu sách. Biết rằng hai học sinh bất kì trong số đó có gặp nhau tại hiệu sách. Chứng minh rằng có mội thời điểm mà trong hiệu sách có mặt cùng lúc 3 học sinh. (trong 7 học sinh nói trên) Spoiler: Lời giải Gọi $7$ bạn học sinh này là $X_1 \rightarrow X_7$, xét $3$ thời điểm $A_1, A_2, A_3$ mà học sinh $X_1$ đi đến hiệu sách. Do cả $6$ học sinh khác đều có gặp $X_1$ nên mỗi người trong số họ phải đến hiệu sách vào ít nhất $1$ trong $3$ thời điểm kể trên, theo nguyên lý Dirichlet thì tồn tại $2$ học sinh $X_i$ và $X_j (2 \le i,j \le 7, i \neq j)$ đến vào cùng $1$ thời điểm $A_i$. Do đó $3$ học sinh $X_i, X_j, X_1$ cùng có mặt tại hiệu sách cùng $1$ thời điểm nên ta có đpcm. $\boxed{\text{Bài toán 30}}$ Cho $n$ điểm xanh và $n$ điểm đỏ trên mặt phẳng, trong đó không có $3$ điểm nào thẳng hàng. Chứng minh rằng ta có thể nối $2n$ điểm này bằng $n$ đoạn thẳng có đầu mút khác màu sao cho chúng đôi một không giao nhau. Spoiler: Lời giải Ta giải bài này theo nguyên lý cực hạn (lần sau nhớ post bài kèm theo nguồn và phương pháp nhé bạn) Giả sử không tồn tại cách nối thoả mãn đk trên Tồn tại cách nối sao cho tổng độ dài các cạnh được nối nhỏ nhất Trong cách nối trên: Theo giả thiết tồn tại 2 cạnh $AB$ và $CD$ cắt nhau tại $O$ ($A,C$ màu đỏ, $B,D$ màu xanh) Theo bất đẳng thức tam giác, ta có: $OA+OD>AD$ $OB+OC>BC$ Suy ra $AD+BC<AB+CD$ Vậy khi ta thay cạnh AB và CD bằng cạnh AD và BC thì sẽ có một cách nối nhỏ hơn, vô lí (vì cách nối trên là nhỏ nhất) Suy ra đpcm.
$\boxed{\text{Bài toán 31}}$ (China TST 2012) Trong một hình vuông được tạo bởi \[2012 \times 2012\] ô vuông có chứa những con bọ, trong một ô vuông có nhiều nhất 1 con bọ. Vào một thời điểm nào đó, những con bọ này bay lên rồi lại đậu xuống lại vào các ô vuông, mỗi ô vuông cũng có nhiều nhất một con bọ. Đối với mỗi con bọ, có thể xem đoạn thẳng có hướng nối tâm của ô vuông lúc đầu và tâm của lúc sau mà nó đậu lên tạo thành một vector. Với một số lượng bọ ban đầu, xét tất cả những trường hợp có thể xảy ra với các vị trí đầu tiên và cuối cùng của những con bọ, hãy tìm độ dài lớn nhất của tổng các vector. $\boxed{\text{Bài toán 32}}$ (APMO 1998) Cho F là tập tất cả các bộ (A1, . . . ,An) sao cho mỗi Ai là một tập con của {1, 2, . . . , 1998}. Ký hiệu |A| là số các phần tử của tập hợp A. Hãy tính $\sum\limits_{({A_1},{A_2},...,{A_n}) \in F} {|{A_1} \cup {A_2} \cup ... \cup {A_n}|} $ Spoiler: Lời giải Bài này đếm bằng truy hồi. Tập $(1, 2, . . . , 1998)$ có tất cả $2^{1998}$ tập con $A_i$ nên tổng cần tính có tất cả $2^{1998n}$ bộ $n$ số. Bước 1: Với các tập con $(A_1, A_2 ... , A_n)$ của $(1, 2, . . . , 1997)$, ta có thể thêm hoặc không thêm vào mỗi tập $A_i$ phần tử $1998$ để tạo thành tập con của tập $(1, 2, . . . , 1998)$. Vậy từ bộ $(A_1, A_2 ... , A_n)$ ta có $2^n$ bộ gồm các tập con của $\left \{1, 2, . . . , 1998 \right \}$. Bước 2: Bây h chỉ còn xét các tập con $(A_1, A_2 ... , A_n)$ của các bộ còn lại. Làm tương tự như trên thì ta có được $(2^n -1).2^{n(m-1)}$. Tình tổng lại, ta có: $\sum\limits_{({A_1},{A_2},...,{A_n}) \in (1,...,1998)} {|{A_1} \cup {A_2} \cup ... \cup {A_n}|} = (2^n.\sum\limits_{({A_1},{A_2},...,{A_n}) \in (1,...,1998)} {|{A_1} \cup {A_2} \cup ... \cup {A_n}|}) + (2^n -1) 2^{n(m-1)}$ Từ đó, ta có: $\sum\limits_{({A_1},{A_2},...,{A_n}) \in F} {|{A_1} \cup {A_2} \cup ... \cup {A_n}|} = 1998(2^{1998n} - 2^{1997n})$. Mở rộng bài 15: Tính: $P= \sum_{(A_{1},A_{2},...,A_{k})\in F_{k}}\sum_{b\in (A_{1}\cup A_{2}\cup ...\cup A_{k})}b$ $S= \sum_{(A_{1},A_{2},...,A_{k})\in F_{k}}\sum_{i=1}^{k}\sum_{b\in A_{i}}b$ $\boxed{\text{Bài toán 33}}$ (Bulgaria 1996) HÌnh chữ nhật $m \times n ( m,n \in N, m,n>1)$ được chia thành $mn$ hình vuông đơn vị. Có bao nhiêu cách xoá 2 hình vuông sao cho phần còn lại có thể lát kín bởi các domino? Spoiler: Lời giải đặt $S(m,n)$ là số cách tô thỏa yêu cầu. Nếu $m,n$ lẻ thì $S(n)=0$. Tô xen kẽ các ô vuông bằng 2 màu đen trắng. Ta sẽ chứng minh bằng cách bỏ đi 2 ô khác màu nhau thì phân còn lại sẽ được phủ kín bới các ô vuông $1 \times 2$. dễ thấy nó đúng với cách bảng $2 \times 2$, $2 \times 3$, $2 \times 4$, .... Giả sử nó đúng với $m.n$ ta chứng minh nó đúng với $m.(n+1)$.(m chẵn ) chia bảng $m.(n+1)$ thành 2 bảng $A$ và $B$ sao cho $A$ là bảng gồm 2 hàng đầu tiên, và $B$ là bảng còn lại thỏa $m$ là độ dài chiều ngang. nếu 2 ô vuông khác màu nhau bị bỏ ở trong cùng 1 bảng $A$ hoặc $B$ thì dễ thấy theo giả thiết quy nạp, ta có đpcm. nếu 1 ô nằm trong $A$ và 1 ô nằm trong $B$. Khi đấy, ta phủ 1 hcn $1 \times 2$ lên 2 ô vuông nằm cạnh nhau sao cho 1 ô thuộc $A$ và 1 ô thuộc $B$ sao cho ô nằm trong $A$ phải khác màu ô đã bị bỏ trong $A$ trước đó và tương bị với ô trong $B$. Theo giả thiết quy nạp thì phần còn lại của mỗi bảng đều được phủ kín. Vậy ta có đpcm. Từ đó dễ thấy số cách chọn là $S(m,n)=\frac{m^{2}.n^{2}}{4}$. $\boxed{\text{Bài toán 34}}$ Một tập hữu hạn các số nguyên dương được gọi là “béo” nếu mỗi phần tử của nó lớn hơn hoặc bằng số phần tử của nó (Tập rỗng “béo”) . Gọi $a_n$ là số tập con “béo” của $X= \left\{1,2,3,4,…..,n\right\}$ mà không chứa 2 số nguyên liên tiếp nào, $b_n$ là số tập con của X mà 2 phần tử bất kì hơn kém nhau ít nhất 3 đơn vị. Chứng minh rằng $a_n=b_n$ Spoiler: Lời giải Gọi $A$ là các tập béo có k phần tử mà không chứa 2 số nguyên liên tiếp nào, B là các tập con của $X$ có tính chất 2 phần tử bát kì hơn kém nhau ít nhất 3 đơn vị. Từ giả thiết ta thấy : với $A' = {a_1, a_2, ..., a_k} \in A$ thì $k \le a_1 <a_2<...<a_k \le n$. Giờ ta thiết lập 1 ánh xạ đi từ $f: A \rightarrow B$. Đặt $a_i=b_{i}+k-i$ $\forall i=\overline{1,k}$, . ta có: $a_{i+1}-a{i} \ge 2$ $\forall i=\overline{1,k-1}$ $\Rightarrow$ $b_{i+1}-b_{i} \ge 3, b_1 \ge 1, b_{k} \le n $. Từ đấy, ta thấy $B'=\left \{b_1,b_2,...,b_{k} \right. \left. \right \}$ $\in B$. Đặt $f(A)=B'=\left\{b_1,b_2,...\right. \left. \right \}=\left\{a_{1}+1-k,a_{2}+2-k,...a_{k}\right. \left. \right \}$. Vậy $f$ là ánh xạ từ $A$ vào $B$. Dễ chứng minh $f$ song ánh nên $|A|=|B|$ hay $a_{n}=b_{n}$. $\boxed{\text{Bài toán 35}}$ Cho tập hợp $X=\left \{ 1,2,...,50 \right \}$. Tìm số nguyên dương nhỏ nhất $k$ sao cho mọi tập con gồm $k$ phần tử của $X$ đều chứa hai phần tử phân biệt $a$ và $b$ sao cho $ab$ chia hết cho $a+b$ Spoiler: Lời giải Ta chứng minh $k \ge 39$ Các cặp số thoả mãn $ab$ chia hết $a+b$: $(3;6);(4;12);(5;20);(6;12);(6;30);(7;42);(8;2);(9;18);(10;15);(10;40);(12;24);(12;36);(14;35);(15;30);(16;48);(18;36);(20;30);(21;28);(21;42);(24;40);(24;48);(30;45);(36;45)$ Xét tập $M=(6,12,15,18,20,21,24,35,40,42,45,48)$. Vì 23 cặp trên đều có phần tử thuộc $M$ nên tập $X\M$ không thỏa mãn bài toán. Mà $|X\M|=38 \rightarrow k \ge 39$ Ta chứng minh mọi tập có 39 phần tử đều thỏa mãn bài toán: Xét tập $A$ bất kì gồm 39 phần tử của $X$. Chọn 12 cặp số trong 23 cặp trên sao cho các phần tử không trùng nhau: $(3;6);(4;12);(5;20);(7;42);(8;2);(9;18);(10;15);(14;35);(18;36);(21;28);(24;40);(30;45)$ 12 cặp trên chứa 24 phần tử của $X$. Nên $X$ chỉ còn lại 26 phần tử. Vậy ít nhất 13 phần tử của $A$ của phải thuộc 12 cặp trên. Theo nguyên lí drichlet thì $A$ chứa ít nhất 1 trong 12 cặp trên. Từ đó tập $A$ thỏa mãn đề bài.
$\boxed{\text{Bài toán 36}}$ Cho $n$ điểm phân biệt trên đoạn thẳng có độ dài 1 đơn vị. Với mỗi điểm, ta tính tích khoảng cách từ điểm đó đến $n-1$ điểm còn lại. Gọi $S(n)$ là tổng nghịch đảo của các tích ấy. Chứng minh rằng: $S(n) \ge 2^{n-3}$. $\boxed{\text{Bài toán 37}}$ Cho một bảng 4.4, trong mỗi ô vuông có 2 con ngựa và cỏ. Biết 2 con ngựa trong mỗi ô vuông không ăn cỏ trong ô vuông đó mà ở các ô vuông chung cạnh và chúng không ăn cỏ trong cùng một ô vuông. Tìm số lớn nhất các ô vuông không có cỏ bị ăn. Spoiler: Lời giải Em sẽ sử dụng bảng của anh Nxb ở bài trên Xét các con ngựa ở ô vuông $1,4,5^{'},8^{'}$ Dễ dàng nhận ra rằng cỏ ở các ô vuông $2,3,5,8,1^{'},4^{'},6^{'},7^{'}$ đều bị ăn Dễ dàng CM các con ngựa ở ô $6,7,2^{'},3^{'}$ đều có thể ăn cỏ ở các ô trên Xét các con ngựa ở ô $2,3,5,8,1^{'},4^{'},6^{'},7^{'}$ Mỗi ô sẽ có 1 con ngựa ăn cỏ ở 1 trong các ô trên Xét các con ngựa còn lại: Nhận xét: con ngựa ở ô $2,5$ ăn cỏ chung một ô (tương tự với các ô $3$ và $8$, $4^{'}$ và $7^{'}$, $1^{'}$ và $6^{'}$) Dễ dàng thấy rằng cỏ của 4 trong 8 ô còn lại phải bị ăn Vậy số ô không bị ngựa ăn cỏ lớn nhất là 4 $\boxed{\text{Bài toán 38}}$ Cho một nhóm 9 người. Hai người có thể thích nhau, ghét nhau hoặc không quen biết. Hai người được gọi là "có quan hệ với nhau" nếu hoặc thích nhau hoặc quen nhau. Gọi số cặp 2 người có quan hệ với nhau là $n$. Tìm số $n$ nhỏ nhất sao cho trong bất kì trường hợp nào cũng tồn tại 3 người đôi một thích nhau hoặc ghét nhau. $\boxed{\text{Bài toán 39}}$ (Thái Lan 2007) 229 học sinh nam và 271 học sinh nữ được chia thành 10 nhóm, mỗi nhóm 50 học sinh được đánh số từ 1 đến 50. Người ta muốn chọn ra một nhóm 4 học sinh, trong đó số học sinh nữ được chọn là lẻ và thoả mãn điều kiện sau đây: 4 người này được chọn từ 2 nhóm và có 2 cặp học sinh có cùng số thứ tự. Chứng minh rằng số cách chọn các nhóm như vậy là một số lẻ. $\boxed{\text{Bài toán 40}}$ (Moldova 2007) Chứng minh rằng hình vuông cạnh 14 có thể phủ được bởi 21 hình vuông: 6 hình vuông cạnh 1, 5 hình vuông cạnh 2, …, 1 hình vuông cạnh 6.
$\boxed{\text{Bài toán 41}}$ (UK 2007) Ở nước Hexagonia, 6 thành phố được kết nối bởi hệ thống đường sắt sao cho giữa hai thành phố bất kỳ có đường sắt nối trực tiếp. Vào ngày chủ nhật, một số đoạn đường đóng cửa để sửa chữa. Luật đường sắt quy định là mọi thành phố phải có thể đến được từ một thành phố khác (không nhất thiết trực tiếp) trong mọi thời điểm. Có bao nhiêu cách đóng một vài đoạn đường để yêu cầu này được thoả mãn? Spoiler: Lời giải Ta đưa về việc đếm số đồ thị liên thông được tạo từ $6$ đỉnh Đặt mỗi thành phố là một điểm và đoạn đường nối hai thành phố là một cạnh. Xin phát biểu một bổ đề quen thuộc: Nếu $G$ là một đồ thị không liên thông thì $\overline{G}$ (đồ thị bù của $G$) là một đồ thị liên thông Gọi $X,Y$ lần lượt là tập hợp các đồ thị liên thông và không liên thông được tạo từ $6$ đỉnh Xét ánh xạ $f:Y\rightarrow X$, $f\left ( G \right )=\overline{G}$ Dễ dàng nhận thấy đây là một song ánh Suy ra $\left | X \right |=\left | Y \right |$ Mặt khác $\left | X\cup Y \right |=2^6$, $\left | X\cap Y \right |=0$ Vậy $\left | X\right |=2^5$ Có $2^5$ cách chọn thoả mãn ycdb $\boxed{\text{Bài toán 42}}$ (Iran 2007) Cho I1, I2, …, In là n đoạn thẳng đóng trên R sao cho từ bất kỳ k đoạn thẳng trong số chúng, luôn tìm được 2 đoạn có điểm chung. Chứng minh rằng có thể tìm được k – 1 điểm trên R sao cho mỗi đoạn thẳng đã cho chứa ít nhất một điểm trong các điểm được chọn. Spoiler: Lời giải Nhận xét 1: $k>[\frac{n}{2}]+1$ với $n$ lẻ và $k>\frac{n}{2}$ với $n$ chẵn. chứng minh: giả sử $k \le [\frac{n}{2}]+1$. Ta sẽ chỉ ra 1 TH $k \le [\frac{n}{2}]+1$ thì tồn tại 1 bộ $k$ đoạn không có bất kì 2 đoạn nào giao nhau. Xét TH $k=[\frac{n}{2}]+1$ ($n$ lẻ, với $n$ chẵn thì lấy $k=\frac{n}{2}$) có $k$ đoạn thẳng sao cho giao của chúng khác rỗng (tồn tại 1 điểm nằm trên $k$ đường thẳng đó) và $k-1$ còn lại không giao nhau đôi một và không giao với bất kì 1 đường nào của bộ k đoạn kia thì ta chọn 1 đường trong bộ $k$ đường kia và kết hợp với $k-1$ đường không giao nhau, ta sẽ được 1 bộ k đoạn mà không có đoạn nào có điểm chung.(vô lí) Nhận xét 2: tồn tại 1 bộ k đoạn thẳng mà giao của $k$ đoạn thẳng đó khác rỗng giả sử không tồn tại bộ nào thỏa điều này. Xét $k = [\frac{n}{2}]+2$, khi đó sẽ có 1 TH có bộ $k=[\frac{n}{2}]+1$ và chứng minh giống nx 1. Từ 2 nhận xét trên, dễ thấy nếu trên mỗi đoạn thẳng chỉ có 1 điểm thì có nhiều nhất $k-1$ điểm thỏa ycđb khi $k=[\frac{n}{2}]+2$ với $n$ lẻ và $k=\frac{n}{2}+1$ với $n$ chẵn. Nếu với các số $k$ lớn hơn thì ta sẽ thêm vào các điểm nằm trên các đoạn đó để có đủ $k-1$ điểm. $\boxed{\text{Bài toán 43}}$ Tô màu các đỉnh của đa giác đều 12 cạnh bằng hai màu khác nhau. Hãy tìm tất cả các cách tô màu sao cho không có đa giác đều nào có các đỉnh cùng màu. $\boxed{\text{Bài toán 44}}$ Cho bảng hình vuông gồm 13x13 ô vuông.người tatoo màu đỏ ở S ô vuông của bảng sao cho không có 4 ô đỏ nào nằm ở bốn góc của một hình chữ nhật.Hỏi giá trị lớn nhất của S có thể là bao nhiêu ? Spoiler: Lời giải Gọi $x_{i}$ là số ô đỏ ở dòng thứ i. Ta có S=$\sum_{i=1}^{13}x_{i}$ .Ở hàng thứ i số các cặp ô đỏ là$C_{x_{i}}^{2}=\frac{x_{i}\left ( x_{i}-1 \right )}{2}$. Vậy, tổng số các cặp ô đỏ là $A=\sum_{i=3}^{13}\frac{x_{i}\left ( x_{i}-1 \right )}{2}$ Chiếu các cặp ô đỏ xuống một hàng ngang nào đó . Do giả thiết thì không có cặp ô đỏ nào có hình chiếu trùng nhau.Vậy $C_{13}^{2}=78\geq A=\sum_{i=3}^{13}\frac{x_{i}\left ( x_{i}-1 \right )}{2}$ $\Leftrightarrow\sum_{i=1}^{13}x_{i}^{2}-\sum_{i=1}^{13}x_{i}\leq 156$ Theo BĐT Bunhiacopxki: $\left ( \sum_{i=1}^{13} x_{i}\right )^{2}\leq 13\left ( \sum_{i=1}^{13}x_{i}^{2} \right )$. Ta suy ra $\frac{S^{2}}{13}-S\leq \sum_{i=1}^{13}x_{i}^{2}-\sum_{i=1}^{13}x_{i}\leq 156$. $\Leftrightarrow S^{2}-13S-2028\leq 0$ $\Leftrightarrow S\leq 52$ Đẳng thức xảy ra khi $x_{1}=x_{2}=...=x_{13}=4$ Mỗi dòng có 4 ô tô đỏ .Ta có thể đễ dàng thực hiện được cách tô màu như vậy.Vậy $S_{Max}=52$. $\boxed{\text{Bài toán 45}}$ Trong một phòng thi gồn có 9 thí sinh được xếp ngồi xung quanh một bàn tròn.TRong ngân hàng đề có 9 loại đề khác nhau mỗi loại có nhiều bản.Một cách phát đề được coi là hợp lệ nếu mỗi thí sinh được nhận chỉ một đề và hai thí sinh ngồi cạnh nhau thì nhận được hai loại đề khác nhau.Hỏi có tất cả bao nhiêu cách phát đề hợp lý? Spoiler: Lời giải Gọi 9 thí sinh ngồi trên bàn tròn theo thứ tự là $a_1,a_2,...,a_9$ Có 9 cách chọn đề cho $a_1$ Có 8 cách chọn đề cho $a_2$ Có 8 cách chọn đề cho $a_3$ ... Có 8 cách chọn đề cho $a_8$ Có 7 cách chọn đề cho $a_9$ Số cách phát đề hợp lệ là: $9.8^7.7=132120576$
$\boxed{\text{Bài toán 46}}$ Chứng minh rằng với $n\geq k\geq r\geq s$, ta có: $C_{n}^{k}C_{k}^{r}C_{r}^{s}=C_{n}^{s}C_{n-s}^{r-s}C_{n-r}^{k-r}$ Spoiler: Lời giải Ta sử dụng đếm bằng hai cách. Cho $n$ điểm. Tìm số cách tô $n$ điểm đó sao cho có $k-r$ điểm đỏ, $r-s$ điểm xanh, $s$ điểm đen Cách 1: Đầu tiên ta tô $k$ điểm màu đỏ. Có $C_{n}^{k}$ cách tô. Lấy $k$ điểm này ta tô $r$ điểm màu xanh. Có $C_{k}^{r}$ cách tô. Lấy $r$ điểm trên và tô màu đen. Có $C_{r}^{s}$ cách tô. Vậy có tổng công $C_{n}^{k}C_{k}^{r}C_{r}^{s}$ cách tô Cách 2: Ta dễ thấy số cách tô màu các điểm của bài toán trên là $C_{n}^{s}C_{n-s}^{r-s}C_{n-r}^{k-r}$ $\boxed{\text{Bài toán 47}}$ Cho $m,n$ là 2 số nguyên dương, $m \geq n$. CMR: $\sum_{k=0}^{n}\left ( -1 \right )^kC_{n}^{m-k}C_{n}^{k}=1$ $\boxed{\text{Bài toán 48}}$ Cho $A_1,A_2,...,A_{2n}$ là tập con đôi một khác nhau của tập $\left \{ 1,2,...,n \right \}$. Tìm giá trị lớn nhất của $\sum_{i=1}^{2n}\frac{\left | A_i \cap A_{i+1} \right |}{\left | A_i \right |.\left | A_{i+1} \right |}$ (với $A_{2n+1}=A_1$) $\boxed{\text{Bài toán 49}}$ (Russia 2011) Cho một bảng gồm $10$ cột và $n$ hàng. Ở mỗi ô một chữ số được viết vào. Với một hàng $A$ và $2$ cột bất kì, ta có thể tìm một hàng chỉ khác $A$ tại $2$ ô giao với 2 cột đó. CMR: $n \geq 512$ $\boxed{\text{Bài toán 50}}$ Cho bàn cờ vua $n x n$ ô.Dán mếp trái và mép phải của bàn cờ với nhau,sao cho mặt bàn cờ quay ra ngoài,ta thu được một bàn cờ hình trụ.Tiếp tục dán mép trên và mép dưới của bàn cờ hình trụ ta sẽ thu được một bàn cờ hình xuyến.Hỏi trên bàn cờ hình xuyến ấy có thể xếp được tối đa bao nhiêu quân vua sao cho quân nọ không ăn được quân kia?
