Đến nội dung


Chú ý

Nếu các bạn đăng kí thành viên mà không nhận được email kích hoạt thì hãy kiểm tra thùng thư rác (spam). Nếu không biết cách truy cập vào thùng thư rác thì các bạn chịu khó Google hoặc đăng câu hỏi vào mục Hướng dẫn - Trợ giúp để thành viên khác có thể hỗ trợ.


tritanngo99

Đăng ký: 06-04-2015
Offline Đăng nhập: Riêng tư
****-

Bài viết của tôi gửi

Trong chủ đề: [TOPIC] Mỗi ngày hai bài toán tổ hợp

Hôm nay, 06:28

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$


Trong chủ đề: [TOPIC] Mỗi ngày hai bài toán tổ hợp

Hôm nay, 06:04

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 đỏ.


Trong chủ đề: [TOPIC] Mỗi ngày hai bài toán tổ hợp

06-07-2020 - 19:31

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.


Trong chủ đề: [TOPIC] Mỗi ngày hai bài toán tổ hợp

06-07-2020 - 19:19

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.


Trong chủ đề: [TOPIC] Mỗi ngày hai bài toán tổ hợp

05-07-2020 - 22:49

Bài 7: (Định lý Mantel) Cho $G$ là một đồ thị (đơn, vô hướng) có $n$ đỉnh. Nếu $G$ không có tam giác thì $G$ không có nhiều hơn $[\frac{n^2}{4}]$ cạnh. Đẳng thức xảy ra khi và chỉ khi $G=K_{{\frac{n}{2}},{\frac{n}{2}}}$ nếu $n$ chẵn và $K_{{\frac{n-1}{2}},{\frac{n-1}{2}}}$ với $n$ lẻ. Trong đó $K_{n}$ là đồ thị đầy đủ với $n$ đỉnh.

Bài 8: (Bổ đề bắt tay) Cho đồ thị $G=(V,E)$. Khi đó $2|E|=\sum\limits_{v\in V}deg(v)$. Trong đó $|V|,|E|$ lần lượt là số đỉnh và số cạnh của $G$