Topic tổ hợp.

[thiendienduong]

Mình thấy tổ hợp là mảng kiến thức hay nhất của toán sơ cấp nhưng vẫn chưa có một topic nào về tổ hợp được lâp ra để mọi người cùng trao đổi những bài tổ hợp hay và thú vị. Vì vậy mình lập ra topic này với mong muốn giúp mọi người tiện trao đổi và theo dõi có hệ thống các bài toán tổ hợp.
Mình xin mở đầu với 3 bài tổ hợp sau:
Bài 1:
Trong một giải đấu bóng bàn, mỗi người đều đấu với tất cả các đối thủ còn lại. Chứng minh rằng: ta luôn xếp các vận động viên bóng bàn thành một hàng dọc sao cho người đứng trước thắng người đứng sau.
Bài 2:
Xét 100 số nguyên dương có tổng bằng 101. Chứng minh rằng: ta có thể chọn ra một số các số trong 100 số đó sao cho tổng của chúng bằng 100.
Bài 3:
Cho dãy hữu hạn các số thực: $x_{1} $; $x_{2} $; ...; $x_{n} $ $(n\geq 4) $ có các số đôi một khác nhau. Lấy ra khỏi dãy 4 số hạng bất kì rồi xếp lại vào các vi trí đó, nhưng theo thứ tự ngược lại. Với dãy mới nhận được, ta lại làm như thế, v.v... Hỏi bằng cách đó ta có thể nhận được dãy $x_{n} $;...; $x_{2} $; $x_{1} $ hay không?
Khi gởi bài mới, các bạn nhớ đánh số thứ tự bài và bôi đen như mình để mọi người tiện theo dõi nhé! À quên, lời giải các bạn nhớ đặt trong HINT để mọi người có cái nhìn bao quát về topic, giúp theo dõi dễ dàng hơn.
Mong các bạn ủng hộ topic tổ hợp này nhé!

TOÁN BẤT BIẾN GIỮA DÒNG ĐỜI VẠN BIẾN
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[conami]

Thực ra cũng đã có một topic cho tổ hợp rồi, nhưng lâu lâu không có ai để ý nên nó bị “nguội”:
[Only registered and activated users can see links. ]
Mọi người tham khảo thêm nha
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[thiendienduong]

Nguyên văn bởi thiendienduong

Bài 1:
Trong một giải đấu bóng bàn, mỗi người đều đấu với tất cả các đối thủ còn lại. Chứng minh rằng: ta luôn xếp các vận động viên bóng bàn thành một hàng dọc sao cho người đứng trước thắng người đứng sau.

Mình chém bài 1 trước vậy!
Lời giải:

Xét tất cả các cách xếp một số người thành hàng dọc sao cho người đứng trước thắng người đứng kề sau.
Do số cách xếp như trên là hữu hạn nên ta có thể chọn được một hàng X có nhiều người nhất.
Giả sử vẫn còn một người không được xếp vào hàng X.
*-* Người đó không thể thắng người đứng đầu hàng X vì nếu ngược lại ta sẽ xếp được một hàng khác thỏa đề có nhiều người hơn hàng X.
*_*Người đó cũng không thể thắng người thứ nhì của hàng X vì nếu ngược lại ta cũng sẽ xếp được một hàng khác thỏa đề có nhiều người hơn hàng X.
*_*Lập luận tương tự ta suy ra người đó cũng thua người cuối cùng của hàng X và lúc này ta cũng sẽ xếp được một hàng khác thỏa đề có nhiều người hơn hàng X.
Mâu thuẫn này cho ta điều phải chứng minh.

[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[nhox12764]

Nguyên văn bởi thiendienduong

Bài 2:
Xét 100 số nguyên dương có tổng bằng 101. Chứng minh rằng: ta có thể chọn ra một số các số trong 100 số đó sao cho tổng của chúng bằng 100. [/SIZE]

Bài này hình như có vấn đề thì phải. "100 số nguyên dương có tổng bằng 101" thì dễ thấy chúng là 99 số 1 và 1 số 2 thế chẳng phải chỉ cần bỏ ra một số 1 là đủ sao?
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[ptk_1411]

Chắc bài đó viết nhầm đề. Phải sửa lại là tổng 100 số nguyên dương bằng 200
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[NTH03]

Bài 4:
Trên bảng ô vuông vô hạn tại ô (1,1) có đăỵ một viên bi.Cho phép bỏ bi theo quy tắc : mỗi lần chọn ô (i. j) mà các ô (i+1,j) và ô (i,j+1) chưa đặt bi và lấy bi ở ô (i,j) ra khỏi bảng và đặt vào cấc ô (i+1,j) ,(i,j+1) mỗi ô một viên.Hỏi bằng cách đó ta có thể làm cho các ô (1,1), (1,2),(2,1),(1,3),(2,2),(3,1) đều có bi.
Mình xin đưa ra một bài chung vui
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[nhox12764]

Nguyên văn bởi NTH03

Bài 4:
Trên bảng ô vuông vô hạn tại ô (1,1) có đăỵ một viên bi.Cho phép bỏ bi theo quy tắc : mỗi lần chọn ô (i. j) mà các ô (i+1,j) và ô (i,j+1) chưa đặt bi và lấy bi ở ô (i,j) ra khỏi bảng và đặt vào cấc ô (i+1,j) ,(i,j+1) mỗi ô một viên.Hỏi bằng cách đó ta có thể làm cho các ô (1,1), (1,2),(2,1),(1,3),(2,2),(3,1) đều có bi.
Mình xin đưa ra một bài chung vui

Có phải "bảng ô vuông vô hạn" thì có cả những ô (-1,-1) hay (0,0), (-3,2) đúng không bạn?
Mình hỏi thêm 1 câu nữa: "mỗi lần chọn ô (i. j) mà các ô (i+1,j) và ô (i,j+1) chưa đặt bi và lấy bi ở ô (i,j) ra khỏi bảng" thì có bắt buộc phải chọn ô (i;j) có bi hay không? Bởi vì nếu có thì ô (1;1) không thể có bi bất kì lần nào nữa nếu ban đầu được chọn?
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[thiendienduong]

Nguyên văn bởi thiendienduong

Bài 3:
Cho dãy hữu hạn các số thực: $x_{1} $; $x_{2} $; ...; $x_{n} $ $(n\geq 4) $ có các số đôi một khác nhau. Lấy ra khỏi dãy 4 số hạng bất kì rồi xếp lại vào các vi trí đó, nhưng theo thứ tự ngược lại. Với dãy mới nhận được, ta lại làm như thế, v.v... Hỏi bằng cách đó ta có thể nhận được dãy $x_{n} $;...; $x_{2} $; $x_{1} $ hay không?

Lời giải:

Gọi 2 số hạng $x_{i},x_{j} $ là 2 số hạng đẹp nếu $i<j $ và $x_{i} $ xếp trước $x_{j} $.
Gọi $A $ là dãy đề cho và $\overline{A} $ là dãy ngược lại.
Rõ ràng khi đổi chỗ 2 số hạng cạnh nhau của $A $, ta được dãy $A^{'} $ hơn kém dãy $A $ một cặp số đẹp. Suy ra, sau khi đổi chỗ 2 số hạng đứng kề nhau một số chẵn lần liên tiếp, ta sẽ được dãy $A^{*} $ có số cặp số đẹp cung tính chẵn lẻ với số cặp số đẹp của $A $. (1)
Ta thấy rằng việc đổi chỗ 4 số hạng trong dãy như đề bài có thể thay bằng một số chẵn lần đổi chỗ liên tiếp 2 số hạng đứng cạnh nhau (với qui ước $x_{i},x_{j} $ đứng cạnh nhau nếu $\left | x_{i} -x_{j}\right | $ nhỏ nhất). (2)
Từ (1) và (2) suy ra sau một số lần bất kì đổi chỗ các số hạng của
dãy $A $ như đề bài, ta luôn nhận được một dãy có số cặp số đẹp cùng tính chẵn lẻ với số cặp số đẹp của $A $. (3)
Kí hiệu $s(A),s(\overline{A}) $ là số cặp số đẹp của $A $ và $\overline{A} $. Ta có:
$s(A)=(n-1)+(n-2)+ ... +1=\frac{n(n-1)}{2} $
$s(\overline{A})=0 $
mà từ (3) suy ra $s(A) $ và $s(\overline{A}) $ cùng tính chẵn lẻ nên $n(n-1)\vdots 4\Leftrightarrow n=4k\vee n=4k+1 $.
*-*Với $ n=4k $:
Để có $\overline{A} $, ta thực hiện đổi chỗ các bộ 4 số như sau:
$(x_{1};x_{2};x_{4k-1};x_{4k}) $, $(x_{3};x_{4};x_{4k-3};x_{4k-2}) $, ..., $(x_{2k-1};x_{2k};x_{2k+1};x_{2k+2}) $.
*-*Với $ n=4k+1 $:
Để có $\overline{A} $, ta thực hiện đổi chỗ các bộ 4 số như sau:
$(x_{1};x_{2};x_{4k};x_{4k+1}) $, $(x_{3};x_{4};x_{4k-2};x_{4k-1}) $, ..., $(x_{2k-1};x_{2k};x_{2k+2};x_{2k+3}) $.
Kết luận:Ta có thể nhận được dãy $\overline{A} $ từ dãy $A $ như cách của đề khi và chỉ khi $n $ chia hết cho 4 hoặc chia 4 dư 1.

mỏi tay quá!

[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[winwave]

Nguyên văn bởi NTH03

Bài 4:
Trên bảng ô vuông vô hạn tại ô (1,1) có đăỵ một viên bi.Cho phép bỏ bi theo quy tắc : mỗi lần chọn ô (i. j) mà các ô (i+1,j) và ô (i,j+1) chưa đặt bi và lấy bi ở ô (i,j) ra khỏi bảng và đặt vào cấc ô (i+1,j) ,(i,j+1) mỗi ô một viên.Hỏi bằng cách đó ta có thể làm cho các ô (1,1), (1,2),(2,1),(1,3),(2,2),(3,1) đều có bi.
Mình xin đưa ra một bài chung vui

bài 7.2.3 trang 74

[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[kien10a1]

Bài 5 Cho 100 số dương tổng là 300, không có số nào lớn hơn 100, tổng các bình phương của 100 số lớn hơn 10000. CMR luôn tồn tại 3 số có tổng lớn hơn 100.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[daylight]

Bài 5: Cho $11 $ tập hợp $M_1,M_2,...,M_{11}, $ mỗi tập có $5 $ phần tử và thỏa mãn $M_i \cap M_j \not=\O \ ,\forall 1 \le i < j \le 11. $
Gọi $m $ là số lớn nhất sao cho tồn tại các tập $M_{i_1},M_{i_2},...,M_{i_m} $
Trong số các tập đã cho sao cho $\cap_{k=1}^m M_{i_k} \not= \O $.
Hỏi giá trị nhỏ nhất của $m $ là bao nhiêu ?
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[thiendienduong]

Đã gần $2$ năm rồi!

Mình thật sự muốn duy trì và phát triển topic này nhưng biết khả năng có hạn nên hi vọng các bạn nhiệt tình ủng hộ!

Để hâm nóng lại topic, mình xin làm Bài 5

Nguyên văn bởi daylight

Bài 5: Cho $11 $ tập hợp $M_1,M_2,...,M_{11}, $ mỗi tập có $5 $ phần tử và thỏa mãn $M_i \cap M_j \not=\O \ ,\forall 1 \le i < j \le 11. $
Gọi $m $ là số lớn nhất sao cho tồn tại các tập $M_{i_1},M_{i_2},...,M_{i_m} $ trong số các tập đã cho sao cho $\cap_{k=1}^m M_{i_k} \not= \O $.
Hỏi giá trị nhỏ nhất của $m $ là bao nhiêu ?

Mình diễn giải một chút như sau: Ý của đề là tìm giá trị $m$ nhỏ nhất sao cho trong $11$ tập hợp đã cho tồn tại $m$ tập hợp $M_{i_1},M_{i_2},...,M_{i_m}$ sao cho $\cap_{k=1}^m M_{i_k} \not= \varnothing $ và không tồn tại một số $n>m$ nào mà tồn tại $n$ tập hợp $M_{i_1},M_{i_2},...,M_{i_n}$ sao cho $\cap_{k=1}^n M_{i_k} \not= \varnothing $, tức là với mọi $n>m$ thì với mọi $n$ tập hợp $M_{i_1},M_{i_2},...,M_{i_n}$ bất kì trong $11$ tập đã cho, giao của chúng bằng rỗng.
Lời giải:

Để dễ nêu ví dụ, mình giả sử tập hợp đề cho là tập các số.
$m=4$ là giá trị thỏa đề, ví dụ như sau:
$M_1=\left \{ 1;2;3;4;{\color{Red} 5} \right \}$
$M_2=\left \{ 1;{\color{Red} 6};{\color{Red} 7};{\color{Red} 8};{\color{Blue} 9} \right \}$
$M_3=\left \{ 2;{\color{Red} 6};{\color{Red} {10}};{\color{Blue} {11}};{\color{Red} {12}} \right \}$
$M_4=\left \{ 3;{\color{Red} 7};{\color{Red} {10}};{\color{Blue} {13}};14 \right \}$
$M_5=\left \{ 4;{\color{Red} 8};{\color{Blue} {11}};{\color{Blue} {13}};15 \right \}$
$M_6=\left \{ {\color{Red} 5};{\color{Blue} 9};{\color{Red} {12}};14;15 \right \}$
$M_7=\left \{ 1;{\color{Red} {10}};15;16;{\color{Red} {17}} \right \}$
$M_8=\left \{ 4;{\color{Red} 6};14;16;{\color{Red} {17}} \right \}$
$M_9=\left \{ 2;{\color{Red} 7};15;16;{\color{Red} {17}} \right \}$
$M_{10}=\left \{ 3;{\color{Red} 8};{\color{Red} {12}};14;16 \right \}$
$M_{11}=\left \{ 1;2;3;4;{\color{Red} 5} \right \}$
Sự lặp lại các số như sau:
Số lặp lại ${\color{Blue} {2}}$ lần: ${\color{Blue} {9;11;13}}$,
Số lặp lại ${\color{Red} {3}}$ lần: ${\color{Red} {5;6;7;8;10;12;17}}$,
Số lặp lại $4$ lần: $1;2;3;4;14;15;16$.
Do đó không có trá trị lớn hơn $4$ nào thỏa đề.
Bây giờ ta đi chỉ ra mâu thuẫn khi $m$ nhận giá trị nhỏ hơn $4$.
Vì $m<4$ nên ta giả sử sự lặp lại của các số trong $11$ tập hợp như sau:
1/. Có $x_1$ số lặp lại $1$ lần,
2/. Có $x_2$ số lặp lại $2$ lần,
3/. Có $x_3$ số lặp lại $3$ lần.
suy ra $x_1+2x_2+3x_3=55$
Theo đề, giao của $2$ tập bất kì khác rỗng nên khi lấy giao giữa $2$ tập hợp kì, ta nhận được ít nhất $1$ phần tử giao.
Do có $11$ tập hợp nên ta nhận được ít nhất $C_{11}^{2}=55$ phần tử giao (các phần tử giao có thể trùng nhau).
Tuy nhiên mỗi số lặp lại $2$ lần cho ta $C_{2}^{2}=1$ phần tử giao và mỗi số lặp lại $3$ lần cho ta $C_{3}^{2}=3$ phần tử giao, còn các số chỉ lặp lại $1$ lần tất nhiên không cho ta phần tử giao nào. Do vậy, ta nhận được $1.x_2+3.x_2=55-(x_1+x_2)$ phần tử giao.
Rõ ràng $55\geq 55-(x_1+x_2)\Leftrightarrow x_1+x_2\geq 0\Rightarrow x_1=x_2=0\Rightarrow x_3=\frac{55}{3}$: vô lí!
Vậy $m=4$ là giá trị thỏa đề.

[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[quocbaoct10]

Em xin ùng hộ anh bài này:
Bài 6: cho một hình phẳng F có diện tích bằng 1 được phủ bởi 1 hữu hạn hình tròn. Chứng minh rằng có thể chọn ra một hình tròn có diện tích không nhỏ hơn $\frac{1}{9}$ hoặc một số hình tròn rời nhau có sao cho tổng diện tích của chúng có tổng không nhỏ hơn $\frac{1}{9}$.
Bài 7:Chứng minh rằng tồn tại 1 cách tô màu các nút của mạng lưới nguyên bởi 2 màu thỏa mãn: Không tồn tại hình chữ nhật có 4 đỉnh cùng màu mà có cạnh song song với hai trục tọa độ và cũng không tồn tại diện tích của 1 hình chữ nhật có 4 đỉnh cùng màu bằng lũy thừa của 2.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[thiendienduong]

Nguyên văn bởi quocbaoct10

Em xin ùng hộ anh bài này:
Bài 6: cho một hình phẳng F có diện tích bằng 1 được phủ bởi 1 hữu hạn hình tròn. Chứng minh rằng có thể chọn ra một hình tròn có diện tích không nhỏ hơn $\frac{1}{9}$ hoặc một số hình tròn rời nhau có sao cho tổng diện tích của chúng có tổng không nhỏ hơn $\frac{1}{9}$.
Bài 7:Chứng minh rằng tồn tại 1 cách tô màu các nút của mạng lưới nguyên bởi 2 màu thỏa mãn: Không tồn tại hình chữ nhật có 4 đỉnh cùng màu mà có cạnh song song với hai trục tọa độ và cũng không tồn tại diện tích của 1 hình chữ nhật có 4 đỉnh cùng màu bằng lũy thừa của 2.

Bài 6 Em xem lại đề vì điều đó là hiển nhiên mà.
Bài 7 Em cũng xem lại đề vì anh chứng minh được rằng với mọi cách tô màu thì luôn tồn tại hình chữ nhật có 4 đỉnh cùng màu mà có cạnh song song với hai trục tọa độ.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[quocbaoct10]

Nguyên văn bởi thiendienduong

Bài 6 Em xem lại đề vì điều đó là hiển nhiên mà.
Bài 7 Em cũng xem lại đề vì anh chứng minh được rằng với mọi cách tô màu thì luôn tồn tại hình chữ nhật có 4 đỉnh cùng màu mà có cạnh song song với hai trục tọa độ.

cả hai bài này em đều lấy từ cuốn kỷ yếu GGTH ra, không biết có sai sót. Bài 6 là bài chọn đội tuyển trường em, còn bài 7 thì em có nghi ngờ bị sai đề nên mang lên nhưng không ngờ sai thật . Anh chỉ giúp em sao bài 6 hiển nhiên được không, do hồi thi chọn đt em không nghĩ ra được.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]