tritanngo99

Cho các số a, b, c là các số thực dương thỏa mãn a+b+c=3 .Tìm max của a^4+b^4+c^4-3abc
Các anh giúp em với (

Đề bài có lẻ là phải thêm dữ kiện là $a,b,c\ge 0$ thì mới tồn tại giá trị max.

Vì: Giả sử đối với bài này ta cho $a=b=t( t \rightarrow 0),c=3-2t$ thì biểu thức $P=a^4+b^4+c^4-3abc\rightarrow 81$. 

Cho a, b, c là các số thức $\geq 1$ và $ab+bc+ca=4$. Tìm giá trị lớn nhất của $P=5a+4b+c$. 

Nhờ mọi người giải giúp, em xin cảm ơn!

Ta có: $ab+bc+ca=4\implies c=\frac{4-ab}{a+b}$. Khi đó $P=5a+4b+\frac{4-ab}{a+b}$

Theo đề: $c\ge 1\implies \frac{4-ab}{a+b}\ge 1\iff 4-ab\ge a+b\ge 2\sqrt{ab}$ (Áp dụng bất đẳng thức Cô-si)

$\implies 4-ab\ge 2\sqrt{ab}\iff ab+2\sqrt{ab}-4\le 0\iff (\sqrt{ab}+1)^2\le 5\iff \sqrt{ab}+1\le \sqrt{5}$

$\iff \sqrt{ab}\le \sqrt{5}-1$

$\implies ab\le (\sqrt{5}-1)^2\iff ab\le 6-2\sqrt{5}(1)$

$(1)\implies b\le \frac{6-2\sqrt{5}}{a}\le 6-2\sqrt{5}$ (do $a\ge 1$). 

và cũng $(1)\implies a\le \frac{6-2\sqrt{5}}{b}\le 6-2\sqrt{5}$ (do $b\ge 1$).

Đặt $A=6-2\sqrt{5}>1$

$\blacksquare$ Tìm giá trị nhỏ nhất.

Đặt $f(a)=P=5a+4b+\frac{4-ab}{a+b}$.

$\implies f'(a)=5+\frac{-b(a+b)-(4-ab)}{(a+b)^2}=5+\frac{-b^2-4}{(a+b)^2}=\frac{5(a+b)^2-4-b^2}{(a+b)^2}=\frac{5a^2+10ab+4b^2-4}{(a+b)^2}>0$ (Vì $a\ge 1,b\ge 1$)

$\implies f(a)$ đồng biến trên $(1;+\infty)$

Do $a\ge 1$ nên $f(a)\ge f(1)=5+4b+\frac{4-b}{b+1}$

Đặt $g(b)=f(1)=5+4b+\frac{4-b}{b+1}$

$\implies g'(b)=4+\frac{-(b+1)-(4-b)}{(b+1)^2}=4+\frac{-5}{(b+1)^2}=\frac{4(b+1)^2-5}{(b+1)^2}=\frac{4b^2+8b-1}{(b+1)^2}>0$ (Do $b\ge 1$)

$\implies g(b)$ đồng biến trên $(1;+\infty)$

Do $b\ge 1$ nên $g(b)\ge g(1)=5+4+\frac{4-1}{1+1}=9+\frac{3}{2}=\frac{21}{2}$.

Suy ra $P=f(a)\ge f(1)=g(b)\ge g(1)=\frac{21}{2}$.

Vậy $P_{min}=\frac{21}{2}$

Dấu $=$ xảy ra tại $a=b=1;c=\frac{4-ab}{a+b}=\frac{3}{2}$.

$\blacksquare$ Tìm giá trị lớn nhất. (Continued ..)

Tính:$\frac{\sqrt{2-\sqrt{3}}+\sqrt{4-\sqrt{15}}+\sqrt{10}}{\sqrt{23-3\sqrt{5}}}$

Ta có: $\frac{\sqrt{2-\sqrt{3}}+\sqrt{4-\sqrt{15}}+\sqrt{10}}{\sqrt{23-3\sqrt{5}}}=\frac{\sqrt{2}(\sqrt{2-\sqrt{3}}+\sqrt{4-\sqrt{15}}+\sqrt{10})}{\sqrt{2}(\sqrt{23-3\sqrt{5}})}=\frac{\sqrt{4-2\sqrt{3}}+\sqrt{8-2\sqrt{15}}+\sqrt{20}}{\sqrt{46-6\sqrt{5}}}=\frac{(\sqrt{3}-1)+(\sqrt{5}-\sqrt{3})+2\sqrt{5}}{3\sqrt{5}-1}=\frac{3\sqrt{5}-1}{3\sqrt{5}-1}=1$.

(Do :
+ $\sqrt{4-2\sqrt{3}}=\sqrt{(\sqrt{3}-1)^2}=|\sqrt{3}-1|=\sqrt{3}-1$;

+ $\sqrt{8-2\sqrt{15}}=\sqrt{(\sqrt{5}-\sqrt{3})^2}=|\sqrt{5}-\sqrt{3}|=\sqrt{5}-\sqrt{3}$ ;

+ $\sqrt{46-6\sqrt{5}}=\sqrt{(3\sqrt{5}-1)^2}=|3\sqrt{5}-1|=3\sqrt{5}-1$)

So sánh $\sqrt{6}-1$ và $\sqrt{5}$

Đặt $A=\sqrt{6};B=\sqrt{5}+1$.

Ta có: $A^2 = 6$ và $B^2=6+2\sqrt{5}$.

$\implies A^2<B^2\implies A<B $(do $A,B>0$).

$\implies A-B<0\iff \sqrt{6}-\sqrt{5}-1<0\iff \sqrt{6}-1<\sqrt{5}$.

Vậy $\sqrt{6}-1<\sqrt{5}$

Xin lỗi các bạn vì sự chậm trễ này.

Lời giải bài 17: Đây chính là định lý Kelli trong không gian hai chiều.

Chứng minh: Ta chứng minh bằng quy nạp theo số $n$ các hình lồi.

1. Xét $n=4$

Gọi $F_1,F_2,F_3,F_4$ là bốn hình lồi có tính chất là giao của ba hình bất kì trong chúng là khác rỗng. Vì $F_2\cap F_3\cap F_4 \ne \emptyset $ nên tồn tại $A_1\in F_2\cap F_3\cap F_4$. Tương tự tồn tại $A_2\in F_1\cap F_3\cap F_4;A_3\in F_1\cap F_2\cap F_4; A_4\in F_1\cap F_2\cap F_3$.

Chỉ có hai khả năng xảy ra:

a) Nếu $4$ điểm $A_1,A_2,A_3,A_4$ không hoàn toàn khác nhau. Khi đó không giảm tính tổng quát ta cho là $A_1\equiv A_2$. Từ đó suy ra:

$A_1\in F_1\cap F_2\cap F_3\cap F_4$. Nên $F_1\cap F_2\cap F_3\cap F_4\ne \emptyset$.

b) $A_1,A_2,A_3,A_4$ là $4$ điểm phân biệt, khi đó lại có hai khả năng xảy ra:

b1) Bao lồi của $A_1,A_2,A_3,A_4$ chính là tứ giác lồi $A_1A_3A_2A_4$

Giả sử $O$ là giao của hai đường chéo $A_1A_2$ và $A_3A_4$

Do $A_1\in F_2\cap F_3\cap F_4$ nên $A_1\in F_3$; $A_2\in F_1\cap F_3\cap F_4$ nên $A_1\in F_3$.

Vì $F_3$ lồi mà $A_1\in F_3,A_2\in F_3$ nên $[A_1,A_2]\in F_3$.

nên $O\in F_3$.

Lập luận hoàn toàn tương tự ta suy ra $O\in F_1,O\in F_2,O\in F_4$.

Điều đó có nghĩa là $F_1\cap F_2\cap F_3\cap F_4=\emptyset$

b2) Bao lồi của chúng là tam giác chứa điểm bên trong. Không giảm tổng quát ta có thể cho là $\triangle{A_1A_2A_3}$ chứa $A_4$

... Còn nữa...

Lời giải bài 18: Xét tập $A=\left\{1;3;6;9;13;17\right\}\subset X$

Ta thấy với mọi $a_i,a_j\in A$ thì phương trình $a_i-a_j=k$ có ít hơn $k$ nghiệm. Suy ra $n\ge 7$.

Ta chứng minh $n=7$ thỏa mãn.

Xét $A=\left\{1\le a_1<a_2<...<a_7\le 17\right\}$ là tập con bất kì của tập $X$. Giả sử phương trình $a_i-a_j$ có ít hơn $k$ nghiệm. Suy ra không có cặp $(a_i;a_j)$ để $a_i-a_j=1$, có nhiều nhất một cặp $(a_i;a_j)$ thỏa mãn $a_i-a_j=2$, có nhiều nhất hai cặp $(a_i;a_j)$ thỏa mãn $a_i-a_j=3$ và có nhiều nhất $3$ cặp $(a_i;a_j)$ thỏa mãn $a_i-a_j=4$.

Khi đó: $a_7-a_1=\sum\limits_{i=1}^{6}(a_{i+1}-a_i)\ge 2+2.3+3.4=20$.

Điều này vô lý, do $a_7\le 17$.

Vậy $n_{min}=17$

Bài 17: Trong mặt phẳng cho $n$ hình lồi $n\ge 4$. Biết rằng giao của ba hình lồi bất kì trong chúng khác rỗng. Khi đó giao của $n$ hình lồi cũng khác rỗng.

Bài 18: Tìm số nguyên dương $n$ nhỏ nhất sao cho nếu $a_1,a_2,...,a_n$ là $n$ số phân biệt tùy ý được chọn từ tập $X=\left\{1,2,...,17\right\}$ ta luôn tìm được số nguyên dương $k$ sao cho phương trình $a_i-a_j=k$ có ít nhất $k$ nghiệm.

Bổ đề bài 15: Cho một nhóm gồm $10$ người bất kỳ. Chứng minh rằng luôn có a) và b) biết:

a) Một nhóm con $3$ người không quen biết lẫn nhau hoặc một nhóm con $4$ người quen biết lẫn nhau.

b) Một nhóm con $3$ người quen biết lẫn nhau hoặc một nhóm con $4$ người không quen biết lẫn nhau.

Lời giải bổ đề: Giả sử $A$ là một trong $10$ người đó, còn $9$ người ngồi vào $2$ phòng, phòng $Y$ gồm những người quen $A$, phòng $Z$ gồm những người không quen $A$. Người $A$ không vào một trong hai phòng đó.

a) Ta có phong $Y$ có ít nhất $6$ người hoặc phòng $Z$ có ít nhất $4$ người.

(i) Giả sử phòng $Y$ có ít nhất $6$ người , theo bài toán 10 , trong phòng $Y$ luôn tìm được nhóm $3$ người quen biết lẫn nhau hoặc $3$ người không quen biết lẫn nhau. $A$ cùng với nhóm $3$ người quen biết lẫn nhau tạo thành nhóm $4$ người quen biết lẫn nhau.

(ii) Giả sử phòng $Z$ có ít nhất $4$ người. Khi đó hoặc $4$ người quen biết lẫn nhau hoặc có ít nhất $2$ người không quen biết lẫn nhau. Giả sử là $B,C$. Trong trường hợp đầu ta có nhóm $4$ người quen biết lẫn nhau. Trong trường hợp sau $A,B,C$ là nhóm $3$ người không quen biết lẫn nhau. Yêu cầu bài toán được thỏa mãn.

b) Tương tự phòng $Z$ có ít nhất $6$ người hoặc phòng $Y$ có ít nhất $4$ người. Ta chỉ cần đổi hai khái niệm "quen biết lẫn nhau" và "không quen biết lẫn nhau" thì chỉ ra được những nhóm người thỏa mãn yêu cầu bài toán. 

Lời giải bài 15: Giả sử $A$ là một trong $20$ người đó, phòng $Y$ gồm những người quen $A$, phòng $Z$ gồm những người không quen $A$. Người $A$ không ngồi trong hai phòng đó. Vậy thì hoặc phòng $Y$ có ít nhất $10$ người, hoặc phòng $Z$ có ít nhất $10$ người.

i) Giả sử phòng $Y$ có ít nhất $10$ người theo bổ đề trên, phòng $Y$ có $3$ người quen lẫn nhau hoặc $4$ người không quen biết lẫn nhau. $A$ cùng nhóm với $3$ người quen biết lẫn nhau có thể tạo thành nhóm $4$ người quen biết lẫn nhau. Yêu cầu bài toán được thỏa mãn.

ii) Giả sử phòng $Z$ có ít nhất $10$ người. Tương tự như trường hợp $i$ ta chỉ cần đổi khái niệm "quen biết lẫn nhau" với "không quen biết lẫn nhau" thì chỉ ra được những nhóm người thỏa mãn yêu cầu bài toán.

Lời giải bài 16: Vì $14$ chia cho $4$ còn dư $2$, nên với tư cách người đi đầu em Trung bốc $2$ viên bi, để số bi còn lại là $12$ viên.

Tiếp theo giả sử em Việt bốc $3$ viên, nên trên bàn còn $9$ viên bi

Đến lượt mình em Trung bốc $1$ viên bi, để số bi còn lại là $8$ viên.

Đến lượt mình, giả sử em Việt bốc $2$ viên bi, nên trên bàn còn $6$ viên bi

Đến lượt mình, em Trung phải bốc $2$ viên bi, để số bi còn lại là $4$ viên.

Lần cuối cùng giả sử em Việt bốc $1$ viên, nên số bi còn lại là $3$ viên.

Đến lượt mình đồng thời là người bốc cuối cùng em Trung bốc tất cả $3$ viên bi còn lại và thắng cuộc.

Bài toán gốc: Giả sử $m,n$ là hai số tự nhiên $m<n$ và $n$ không chia hết cho $m+1$.

Trên bàn có một đống gồm $n$ vật. Hai em $A,B$ thực hiện trò chơi bốc các vật theo các nguyên tắc sau:

1) Người đi đầu được xác định bằng gieo đồng tiền

2) Mỗi người đến lượt phải bốc ít nhất một vật và không được bốc quá $m$ vật.

3) Người bốc được vật cuối cùng sẽ thắng cuộc.

Nếu em $A$ được đi đầu, thì em phải có cách bốc các vật như thế nào để đảm bảo thắng cuộc, tức bốc được vật cuối cùng.

Có hai cách đưa ra thuật toán bốc các vật để em $A$ chiến thắng. Đó là phương pháp đồng dư và phương pháp đồ thị.

Nhưng ở đây mình chỉ nêu phương pháp đồng dư, còn phương pháp đồ thị sẽ được giới thiệu ở những bài tiếp theo.

- Phương pháp dồng dư:

+ Thuật toán được hình thành dựa trên cơ sở tính đồng dư theo modul $(m+1)$

1) Vì $n$ không chia hết cho $m+1$, nên khi chia $n$ cho $m+1$ nhận được số dư $r(0<r\le m)$. Bởi vậy tại bước xuất phát em $A$ có thể bốc $r$ vật, để trên bàn còn lại số lượng vật bằng nguyên lần của $m+1$.

2) Tại các bước tiếp theo, nếu đến lượt mình, em $B$ bốc $s(1\le s\le m)$ vật, thì ngay sau đó em $A$ bốc $(m+1-s)$ vật, nên trên bàn số lượng vật vẫn là nguyên lần của $m+1$.

3) Trước khi em $B$ bốc lần cuối cùng, trên bàn còn đúng $m+1$ vật, nhưng em $B$ phải bốc ít nhất $1$ vật và không được bốc quá $m$ vật, nên em $A$ có quyền bốc hết số vật còn lại này và thắng cuộc.

P/s: Bài toán 16 là trường hợp riêng của bài này với $n=14$ và $m=3$

Bài 15: Cho một nhóm $20$ người bất kỳ. Chứng minh rằng luôn có một nhóm con $4$ người quen biết lẫn nhau hoặc không quen biết lẫn nhau.

Bài 16: Trên bàn có một đống bi gồm $14$ viên. Hai em Trung , Việt thực hiện trò chơi bốc bị theo các nguyên tắc sau:

1) Người đi đầu được xác định bằng gieo đồng tiền.

2) Mỗi người đến lượt phải bốc ít nhất một viên bi và không được bốc quá 3 viên bi.

3) Người bốc được viên bi cuối cùng sẽ thằng cuộc.

Hỏi: Nếu em Trung đi đầu, thì em phải có cách bốc bi như thế nào để thắng cuộc, tức bốc được viên bi cuối cùng ?

Lời giải bài 13: Lời giải giống bạn Tan Thuy Hoang. Mình chỉ viết lại , để nhỡ dữ liệu bị mất thì ảnh mất luôn !

Các đường thẳng đã cho không thể cắt các cạnh kề nhau của hình vuông, bởi vì nếu thế chúng chia hình vuông thành một tam giác và ngũ giác. (Chứ không phải chia hình vuông thành hai tứ giác).

Vì lẽ đó, mọi đường thẳng (trong số chín đường thẳng) đều cắt hai cạnh đối của hình vuông và dĩ nhiên không đi qua một đỉnh nào của hình vuông cả.

Giả sử một đường thẳng cắt hai cạnh đối $BC$ và $AD$ tại các điêm $M$ và $N$. Ta có: $\frac{S_{ABMN}}{S_{MCDN}}=\frac{2}{3}\iff \frac{\frac{1}{2}AB(MB+AN)}{\frac{1}{2}CD(MC+DN)}=\frac{2}{3}\iff \frac{EJ}{JF}=\frac{2}{3}$.

(Ở đây $E$ và $F$ là các trung điểm của $AB$ và $CD$ tương ứng).

Gọi $E,F,P,Q$ tương ứng là các điểm sao cho $J_1,J_2$ nằm trên $EF$;$J_3,J_4$ nằm trên $PQ$ và thỏa mãn: $\frac{EJ_1}{J_1F}=\frac{FJ_2}{J_2E}=\frac{PJ_3}{J_3Q}=\frac{QJ_4}{J_4P}=\frac{2}{3}$.

Khi đó từ lập luận trên ta suy ra mỗi đường thẳng có tính chất thỏa mãn yêu cầu đề bài phải đi qua một trong bốn điểm $J_1,J_2,J_3,J_4$ nói trên.

Vì có chín đường thẳng, nên theo nguyên lý Dirichlet phải tồn tại ít nhất một trong bốn điểm $J_1,J_2,J_3,J_4$ sao cho nó có ít nhất ba trong chín đường thẳng đã cho đi qua. Vậy có ít nhất ba đường thẳng trong số chín đường thẳng đã cho đi qua một điểm.

Lời giải bài 14: Đặt $a=x+y+\sqrt{x^2+y^2},b=x+y-\sqrt{x^2+y^2}$. Ta có: $\frac{1}{a}+\frac{1}{b}=\frac{1}{x+y+\sqrt{x^2+y^2}}+\frac{1}{x+y-\sqrt{x^2+y^2}}=\frac{2(x+y)}{(x+y)^2-(x^2+y^2)}=\frac{x+y}{xy}=\frac{1}{x}+\frac{1}{y}$.

Như vậy, qua các phép biến đổi, tổng nghịch đảo các số trên bảng không thay đổi. Vì $\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+\frac{1}{6}=\frac{19}{20}<1$ nên qua các lần biến đổi, tổng nghịch đảo các số trên bảng vẫn nhỏ hơn $1$. Do các số trên bảng qua các phép biến đổi đều dương nên từ đây suy ra không có số nào nhỏ hơn 1.

Bài 13: Cho chín đường cùng có tính chất là mỗi đường thẳng chia hình vuông thành hai tứ giác có tỉ số diện tích bằng $\frac{2}{3}$. Chứng minh rằng, có ít nhất ba đường thẳng trong số đó cùng đi qua một điểm

Bài 14: Trên bảng có $4$ số $3,4,5,6$. Mỗi lần thực hiện, cho phép xóa đi hai số $x,y$ có trên bảng và thay bằng $x+y+\sqrt{x^2+y^2}$ và $x+y-\sqrt{x^2+y^2}$. Hỏi sau một số hữu hạn bước thực hiện, trên bảng có thể xuất hiện một số nhỏ hơn $1$ được không ?

Lời giải bài 11: Gọi $x_i$ là số số $1$ ở hàng thứ $i$. Ta cần tìm max $S$ với $S=\sum\limits_{i=1}^{n^2+n+1}x_i$.

Gọi tập $M$ gồm các cặp $(k;l)$ mà $1\le k<l\le n^2+n+1$, ta có $|M|=C_{n^2+n+1}^{2}$. (Trong đó $C_{b}^{a}=\frac{b!}{a!(b-a)!}$)

Với mỗi $i=1,2,...,n^2+n+1$, ta xét tập $M_i$ gồm các cặp $(k;l)$ mà hai ô giao ở cột $k$ và cột $l$ với hàng thứ $i$ đều chứa số $1$. Ta có $|M_i|=C_{x_i}^{2}=\frac{x_i(x_i-1)}{2}$.

Vì không có $4$ ô ghi số $1$ là đỉnh của hình chữ nhật nên $M_i\cap M_j=\varnothing \forall i\ne j$.

Do đó $\sum\limits_{i=1}^{n^2+n+1}|M_i|\le |M|$.

Hay $\frac{1}{2}\sum\limits_{i=1}^{n}(x_i^2-x_i)\le \frac{(n^2+n)(n^2+n+1)}{2}\iff \sum\limits_{i=1}^{n^2+n+1}x_i^2-\sum\limits_{i=1}^{n^2+n+1}x_i\le (n^2+n)(n^2+n+1)$

Mặt khác $\sum\limits_{i=1}^{n^2+n+1}x_i^2\ge \frac{1}{n^2+n+1}(\sum\limits_{i=1}^{n^2+n+1}x_i)^2$

nên ta có: $\frac{1}{n^2+n+1}S^2-S\le (n^2+n)(n^2+n+1)\iff S^2-(n^2+n+1)S-(n^2+n)(n^2+n+1)^2\le 0$

$\implies S\le (n+1)(n^2+n+1)$. (Với $S=\sum\limits_{i=1}^{n^2+n+1}x_i$)

Đẳng thức xảy ra khi $x_1=x_2=...=x_{n^2+n+1}=n+1$.

Vậy có nhiều nhất $(n+1)(n^2+n+1)$ số $1$ được ghi lên bảng.

Lời giải bài 12: Bài toán này chính là Định lý EGZ (Erdos-Ginzburg-Ziv), 

Ta gọi mệnh đề ở đề bài là $A(n)$. Trước hết ta chứng minh rằng nếu $A(m),A(n)$ đúng thì $A(mn)$ cũng đúng. (Dành cho bạn đọc). Từ đây, bài toán quy về chứng minh $A(p)$ với $p$ là số nguyên tố.

Xét $E=\left\{a_1,a_2,...,a_{2p-1}\right\}$. Giả sử ngược lại rằng với mọi bộ $a_{i1},...,a_{ip}$ lấy từ $E$ ta có $a_{i1}+...+a_{ip}$ không chia hết cho $p$. Khi đó, theo định lý nhỏ Fermat ,ta có: $(a_{i1}+...+a_{ip})^{p-1}\equiv 1(\text{ mod }p)$.

Từ đó suy ra $\sum(a_{i1}+...+a_{ip})^{p-1}\equiv C_{2p-1}^{p}(\text{ mod }p)$, trong đó tổng tính theo tất cả các tập con $p$ phần tử của $E$.

Mặt khác, ta đếm số lần xuất hiện của các đơn thức $a_{j1}^{\alpha_1}...a_{jk}^{\alpha_k}$ với $\alpha_1+...+\alpha_k=p-1$ trong tổng ở vế trái.

Có $C_{2p-1}^{k}C_{2p-k-1}^{p-k}$ tổng dạng $a_{i1}+...+a_{ip}$ có chứa $a_{j1},...,a_{jk}$. Trong mỗi tổng này, đơn thức $a_{j1}^{\alpha_1}...a_{jk}^{\alpha_k}$ xuất hiện với hệ số $\frac{(p-1)!}{\alpha_1!...\alpha_k!}$. Như vậy, đơn thức $a_{j1}^{\alpha_1}...a_{jk}^{\alpha_k}$ sẽ xuất hiện trong tổng vế trái với hệ số $C_{2p-1}^{k}C_{2p-k-1}^{p-k}.\frac{(p-1)!}{\alpha_1!...\alpha_k!}=\frac{(2p-1)!}{k!(p-k)!(p-1)!}.\frac{(p-1)!}{\alpha_1!...\alpha_k!}$

Do $1\le k\le p-1$ nên hệ số này luôn chia hết cho $p$, suy ra tổng vế trái chia hết cho $p$. Mặt khác $C_{2p-1}^{p}=\frac{(2p-1)!}{p!(p-1)!}=\frac{(p+1)...(2p-1)}{(p-1)!}$ không chia hết cho $p$. Mâu thuẩn.

Bài 11: Cho bảng $(n^2+n+1)\text{ x }(n^2+n+1)$. Ta điền vào mỗi số của bảng số $0$ hoặc số $1$, sao cho không có bốn ô ghi số $1$ nào là đỉnh của hình chữ nhật. Hỏi có nhiều nhất bao nhiêu chữ số $1$ được ghi lên bảng.

Bài 12: Chứng minh rằng từ $2n-1$ số nguyên bất kỳ luôn tìm được $n$ số có tổng chia hết cho $n$

Lời giải bài 9: Giả sử tại một thời điểm nào đó, ta có $a$ hiệp sĩ tóc đỏ, $b$ hiệp sĩ tóc vàng và $c$ hiệp sĩ tóc xanh , ta đặt $N=a-b(\text{ mod }3)$. Ta chứng minh $N$ không thay đổi khi có sự đổi màu tóc.

Thật vậy:

+ Nếu hiệp sõ tóc đỏ gặp hiệp sĩ tóc vàng thì ta có $a\rightarrow a-1,b\rightarrow b-1,c\rightarrow c+2$, do đó $N\rightarrow (a-1)-(b-1)(\text{ mod }3)$ không thay đổi.

+ Nếu hiệp sĩ tóc đỏ gặp hiệp sĩ tóc xanh thì ta có $a\rightarrow a-1,b\rightarrow b+2,c\rightarrow c-1$, do đó $N\rightarrow (a-1)-(b+2)(\text{ mod }3)\equiv a-b(\text{ mod }3)$ không thay đổi.

+ Nếu hiệp sĩ tóc vàng gặp hiệp sĩ tóc xanh thì ta có $a\rightarrow a+2,b\rightarrow b-1,c\rightarrow c-1$, do đó $N\rightarrow (a+2)-(b-1)(\text{ mod }3)\equiv a-b(\text{ mod }3)$ không thay đổi.

Vì ban đầu ta có $N=13-15(\text{ mod }3)\equiv 1(\text{ mod }3)$ nên trong quá trình biến đổi màu tóc, ta luôn có $N\equiv 1(\text{ mod }3)$. Như thế không xảy ra trường hợp tất cả các hiệp sĩ có cùng màu tóc vì trong trường hợp này, $N$ tương ứng sẽ bằng $0(\text{ mod }3)$ (do $(a,b,c)=(45,0,0)$ hoặc các hoán vị.)

Lời giải bài 10:

Cách 1: Giả sử $\left\{A,B,C,D,E,F\right\}$ là một nhóm $6$ người. Giả thiết rằng những người quen $A$ thì ngồi phòng $Y$ và những người không quen người $A$ thì ngồi ở phòng $Z$. Người $A$ không ngồi trong hai phòng đó. Khi đó có ít nhất $3$ người ngồi trong phòng $Y$ hoặc ngồi trong phòng $Z$.

(a) Không mất tổng quát giả sử $3$ người cùng ngồi trong phòng $Y$ là $B,C,D$. Nếu $3$ người này không quen biết lẫn nhau thì yêu cầu bài toán được thỏa mãn. Nếu $3$ người này có $2$ người quen biết nhau, giả sử $B,C$ thì ta có $3$ người là $A,B,C$ quen biết lẫn nhau. Yêu cầu bài toán được thỏa mãn.

(b) Giả sử $3$ người cùng ngồi trong phòng $Z$ là $B,C,D$ tương tự ta chỉ cần thay đổi khái niệm "quen biết lẫn nhau' với "không quen biết lẫn nhau" thì ta cũng chỉ ra được nhóm $3$ người thỏa mãn yêu cầu bài toán.

Cách 2: Nếu ta coi $6$ người như là $6$ điểm trong mặt phẳng thì ta có thể gặp bài toán trên dưới một dạng khác như sau:

Trong mặt phẳng cho sáu điểm được nối với nhau từng đôi một bởi các cung màu xanh hoặc màu đỏ. Chứng minh rằng luôn tìm được $3$ điểm sao cho các cung nối chúng có cùng một màu (ta nói là chúng tạo thành tam giác xanh hoặc đỏ).

Giải : Cho điểm $P$ nào đó trong $6$ điểm. Từ nó có $5$ cung nối với $5$ điểm còn lại. Theo nguyên lý Dirichlet, có $3$ trong $5$ số cung đó phải có cùng một màu, chẳng hạn là màu xanh. Giả sử đó là các cung $PA,PB,PC$. Nếu như một trong số $3$ cung $AB,AC,BC$ có màu xanh thì nó cùng với hai trong số ba cung $PA,PB,PC$ tạo thành một tam giác xanh. Nếu ngược lại thì tam giác $ABC$ là một tam giác đỏ.

Bài 9: Ở Vương quốc "Sắc màu kì ảo" có $45$ hiệp sĩ: $13$ hiệp sĩ tóc đỏ, $15$ hiệp sĩ tóc vàng, $17$ hiệp sĩ tóc xanh. Khi hai hiệp sĩ có màu tóc khác nhau gặp nhau, tóc của họ sẽ lập tức đổi sang màu thứ ba. Hỏi có thể có một lúc nào đó, tất cả các hiệp sĩ đều có màu tóc giống nhau ?

Bài 10: Cho trước một nhóm $6$ người bất kỳ. Chứng minh rằng luôn có một nhóm con gồm $3$ người trong đó họ quen nhau từng đôi một hoặc họ không quen nhau từng đôi một.

Lời giải bài 7: Gọi $I$ là một tập hợp các đỉnh độc lập (đôi một không có cạnh nối) cực đại và $|I|=x$. J là tập các đỉnh còn lại của G, vậy $|J|=n-x$. 

Ta có các nhận xét sau: 

+ Mỗi cạnh của G có một đầu mút trong I, vì một cạnh nếu có cả 2 đầu mút sẽ khiến $I$ không độc lập.

+ $deg(A)\le x\forall A$. Thật vậy, vì $G$ không có tam giác nên với mỗi đỉnh $A$, $2$ đỉnh kề của $A$ không kề nhau. Nói cách khác tập các đỉnh kề $A$ là độc lập. Do ta giả sử $|I|$ là cực đại nên $deg(A)\le x$.

Như vậy, nếu $e$ là số cạnh của $G$ thì $e\le \sum\limits_{A\in J}deg(A)\le \sum\limits_{A\in J}x=x(n-x)\le [\frac{n^2}{4}]$.

Ta có điều phải chứng minh.

Lời giải bài 8: Mỗi cạnh $e=(u,v)$ được tính một lần trong $deg(u)$ và một lần trong $deg(v)$. Vậy tổng tất cả các bậc của các đỉnh bằng hai lần số cạnh. 

Hệ quả: Số đỉnh bậc lẻ của một đồ thị là một số chẵn.