Combinatorics 7

Bài 7: (Đề nghị Toán 10 Duyên Hải 2015- Chuyên Hoàng Văn Thụ)

Với n nguyên dương tùy ý, n>3, xét  k= \left [ \dfrac{1}{6} n(n+1) \right ] và tập X_{n} gồm \dfrac{n(n+1)}{2} phần tử, trong đó k phần tử màu đỏ, k phần tử màu xanh và còn lại màu trắng. Chứng minh rằng có thể chia tập X_{n} thành n tập con rời nhau  A_{1},A_{2},...,A_{n} sao cho với số m tùy ý 1 \leq m \leq n  thì tập A_{m}  chứa đúng m phần tử và các phần tử đó cùng màu.

Lời giải:

Ta kiểm tra với  luôn tìm được cách chia thành n tập con rời nhau  sao cho với số m tùy ý  thì tập  chứa đúng m phần tử và các phần tử đó cùng màu.

Ta xét cách chia theo bảng sau:

14593533_1732765550308249_866644947_n

Ta sẽ chứng minh bằng quy nạp với việc xây dựng một cách chia tập X_{n} dựa vào cách chia tập X_{n-6} như sau:

Xét tập  X_{n} gồm \dfrac{n(n+1)}{2} phần tử. Ta xét tập X_{n-6} gồm \dfrac{n-6)(n-5)}{2} phần tử, gồm k_{1}= \left [ \dfrac{1}{6} (n-6)(n-5) \right ] phần tử màu xanh, k_{1} phần tử màu đỏ và còn lại là màu trắng. Theo giả thiết quy nạp, tập X_{n-6} luôn có thể chia được thành n-6 tập rời nhau A_{1},A_{2},...,A_{n-6}  thỏa mãn bài toán

Ta có k-k_{1}= \left [ \dfrac{n(n+1)}{2} \right ] - \left [ \dfrac{(n-6)(n-5)}{2} \right ]

Mặt khác [a]-[b] > a-1 -[b] > a-1-b[a] - [b] \leq a- [b] < a- (b-1)=a-b+1

Nếu  a-b là số nguyên thì [a] - [b]=a-b

\dfrac{1}{6} n(n+1) - \dfrac{1}{6} (n-6)(n-5)= 2n-5 là số nguyên nên k-k_{1}=2n-5

Vậy số phần tử màu xanh ( đỏ) ngoài X_{n-6} đều bằng 2n-5 .

|X_{n}|-|X_{n-6}|=6n-15 nên số phần tử màu trắng ngoài X_{n-6}6n-15-2(2n-5)=2n-5

Khi đó, ta xây dựng các tập A_{n-5},A_{n-4},A_{n-3},A_{n-2},A_{n-1},A_{n}  như sau:

Tập A_{n-5},A_{n} chứa toàn phần tử màu xanh

Tập A_{n-4},A_{n-1} chứa toàn phần tử màu đỏ

Tập A_{n-2},A_{n-3} chứa toàn phần tử màu trắng \blacksquare

 

Advertisements

Combinatorics 6

Bài 6: (Đề nghị Toán 11 Duyên Hải 2016- Chuyên Bắc Ninh)

  Ở các vị trí khác nhau của một đường đua ô tô vòng tròn cùng một thời gian có 25 ô tô xuất phát theo cùng một hướng. Theo thể lệ cuộc đua, các ô tô có thể vượt lẫn nhau, nhưng cấm không được vượt đồng thời hai xe một lúc. Các ô tô đến đích là các điểm mà chúng xuất phát ban đầu cùng một lúc. Chứng minh rằng trong suốt cuộc đua có một số chẵn lần vượt nhau của các ô tô.

Lời giải:

Ta sơn 1 trong 25 ô tô thành màu vàng, còn các oto khác đánh số từ 1 đến 24 theo thứ tự mà chúng ở thời điểm ban đầu sau ô tô màu vàng ( theo chiều chuyển động của các ô tô). Ở tâm của đường đua ta đặt một bảng để ghi số thứ tự của các ô tô sắp xếp sau ô tô vàng sau mỗi lần các ô tô vượt nhau, tức là ta được một hoán vị của {1, 2,..., 24}.

\odot Trường hợp 1:

Mỗi lần 2 ô tô trong các ô tô từ 1 đến 24 vượt nhau thì trên bảng có 2 số liền nhau đổi chỗ cho nhau.

\odot Trường hợp 2:

Nếu trước khi có lần vượt của một ô tô nào với ô tô vàng, các số trên bảng lập thành một hoán vị a_{1},a_{2},...,a_{24} thì sau lần vượt đó sẽ có hoán vị a_{2},a_{3},...,a_{24},a_{1}.

Từ hoán vị trên có thể chuyển xuống hoán vị dưới bằng 23 phép chuyển vị, tức là

phép đổi chỗ 2 số liền nhau.

\odot Trường hợp 3:

Nếu ô tô vàng vượt một ô tô nào đó thì từ hoán vị a_{1},a_{2},...,a_{24} ta có hoán vị  a_{24},a_{1},...,a_{23}. Lần di chuyển này cũng có thể thay bằng 23 phép chuyển vị như trường hợp 2.

Như vậy mỗi lần các ô tô vượt nhau đều dẫn đến việc thực hiện một số lẻ lần phép chuyển vị. Ta sẽ chứng minh nếu số lần vượt nhau là số lẻ thì khi về đích các ô tô không được sắp xếp như cũ. Thật vậy giả sử a_{1},a_{2},...,a_{24} là một cách sắp xếp tùy ý của các số1, 2, ..., 24 . Ta sẽ nói rằng các số a_{i},a_{j} lập thành một nghịch thế nếu i<j mà a_{i} > a_{j}. Khi đổi vị trí 2 số đứng liền nhau, tức là thực hiện một phép chuyển vị thì sẽ tăng hay giảm số nghịch thế đi 1. Do đó nếu các ô tô vượt nhau một số lẻ lần thì từ cách sắp xếp thứ tự của các ô tô ban đầu, đến cuối cùng ta đã thực hiện một số lẻ các phép chuyển vị, tức là số nghich thế của lần sắp xếp cuối cùng là số lẻ, nghĩa là các ô tô không thể sắp xếp như cũ. Mâu thuẫn.

Vậy các ô tô vượt nhau một số chẵn lần \blacksquare

Combinatorics 5

Bài 5:

Cho tập A={1,2,...,2012}. Tìm số tự nhiên n nhỏ nhất sao cho: hễ B \subset A, |B|=n thì chọn được trong B ba số x,y,z phân biệt để x,y,z là độ dài của ba cạnh của một tam giác.

Lời giải:

\odot Xét B \subset A mà các phần tử của B16 số hạng liên tiếp của dãy Fibonaci: B={1,1,2,...,987,1597}. Khi đó |B|=16 và trong B không thể chọn ra x,y,z phân biệt là ba cạnh của một tam giác.

\odot Xét B \subset A, |B|=17. Giả sử các phần tử của Bb_{1},b_{2},...,b_{17} \ (b_{1} < b_{2} <...<b_{17}) Giả sử trong B không chọn được x,y,z là ba cạnh của một tam giác. Khi đó:

b_{3} \geq 1+2, b_{4} \geq 2+3,..., b_{17} \geq 987+1597 > 2012 (Mâu thuẫn)

Vậy min \ n=17 \blacksquare

Combinatorics 4

Bài 4:

Người ta viết các số nguyên 1,2,3,4,5,6,7,8 lên các đỉnh của một bát giác lồi sao cho tổng các số ở ba đỉnh liên tiếp không nhỏ hơn kk nguyên dương. Tìm giá trị lớn nhất của k.

Lời giải:

Gọi A là tổng của tất cả các bộ ba liên tiếp trên các đỉnh. Dễ thấy rằng mỗi số xuất hiện đúng 3 lần trong tổng A nên A=3 \sum_{i=1}^{8} i=108.

Do mỗi tổng có giá trị không nhỏ hơn k nên ta có hệ thức A \geq 8k \Leftrightarrow 108 \geq 8k \Leftrightarrow k \leq 13,5 nhưng k nguyên nên suy ra k \leq 13.

Ta sẽ chứng minh không tồn tại cách đánh số với k=13.

Thật vậy, giả sử ngược lại, tồn tại một cách đánh số thỏa đề.

Giả sử a_{1}=1, khi đó rõ ràng a_{2}, a_{3},a_{7},a_{8} không thể là 2 hoặc 3; tức là 2 và 3 được đánh số cho các đỉnh a_{4},a_{5},a_{6}.

Khi đó số 2 và 3 không được nằm cạnh nhau vì khi đó cần có đến 2 số 8 nằm ở 2 bên 2 đỉnh đo, vô lí. Do đó, ta có 2 trường hợp: a_{4}=2,a_{5}=8,a_{6}=3 hoặc a_{4}=3,a_{5}=8,a_{6}=2. Ta còn lại các số: 4,5,6,7 để điền vào các vị trí: a_{2},a_{3},a_{7},a_{8}.

Ta cần có:a_{1}+a_{2}+a_{3} \geq 13 \Rightarrow a_{2}+a_{3} \geq 12

a_{1}+a_{7}+a_{8} \geq 13 \Rightarrow a_{7}+a_{8} \geq 12. Suy ra:

a_{2}+a_{3}+a_{7}+a_{8} \geq 24, trong khi đó: 4+5+6+7=22 < 24.

Đến đây ta thấy có mâu thuẫn xảy ra, vậy không tồn tại cách đánh số thỏa đề.

Ta có thể đưa ra một cách số như sau:

1 \rightarrow 5 \rightarrow 6 \rightarrow 2 \rightarrow 4 \rightarrow 7 \rightarrow 3 \rightarrow 3 \rightarrow 8

Dễ thấy rằng cách này thỏa mãn đề bài. Vậy giá trị lớn nhất cần tìm của kk=12 \blacksquare

Combinatorics 3

Bài 3:

Hai đội tuyển A và B tham gia giải cầu lông. Mỗi đội có 7 người đấu với nhau theo 1 thứ tự nhất định. Đầu tiên người thứ nhất của đội A đấu với người thứ nhất của đội B và người thua sẽ bị loại. Sau đó người chiến thắng chơi nữa với người thứ hai của đội kia. Các bước tiếp theo chơi tương tự. Cuộc thi đấu không kết thúc cho đến khi tất cả người chơi của 1 đội đều bị loại và đội còn lại là chiến thắng. Hỏi số cách diễn ra cuộc thi đấu.

Lời giải:

Trước hết ta tìm số quá trình khác nhau cuẩ cuộc chơi khi A thắng.

Gỉa sử người thứ i của A thắng x_{i} lần (i=1,2,...,7) thế thì: x_{1}+x_{2}+...+x_{7}=7

Thế thì số quá trình phân biệt của cuộc chơi nếu A thắng bằng số nghiệm không âm của phương trình trên và bằng \textrm{C}_{7+7-1}^{7-1}= \textrm{C}_{13}^{6}

Tương tự số quá trình phân biệt của cuộc chơi nếu B thắng bằng \textrm{C}_{13}^{6}

Như vậy số cách diễn ra cuộc thi đấu là:

2. \textrm{C}_{13}^{6}= 3432 \blacksquare

 

Combinatorics 2

Bài 1:

Cho 2016 cái kẹo vào 1008 cái hộp sao cho không có hộp nào có nhiều hơn 1008 cái kẹo và mỗi hộp có ít nhất 1 cái kẹo. Chứng minh rằng có thể tìm thấy một số hộp mà tổng số kẹo trong các hộp đó đúng bằng 1008m cái kẹo.

Lời giải:

\cdot Nếu tất cả các hộp đều có 2 cái kẹo thì ta chọn 504 hộp sẽ được tổng 1008 cái kẹo.

 \cdot Nếu có ít nhất 2 hộp có số kêọ khác nhau, ta xếp 1008 cá hộp thành hàng ngang sao cho 2 hộp đầu tiên có số kẹo khác nhau, kí hiệu a_{i} chỉ hộp thứ i (i=1,2,...,1008)

Xét các số:

S_{1}=a_{1}, S_{2}=a_{1}+a_{2}, …, S_{1008}=a_{1}+a_{2}+...+a_{1008}

\odot Nếu 2 trong số chúng có cùng sô dư khi chia cho 1008. Giả sử là S_{i}, S_{j} (j>i) \Rightarrow S_{j}-S_{i} \ \vdots \ 1008

\Leftrightarrow a_{i+1}+...+a_{j} \ \vdots \ 1008

1 \leq S_{j}-S_{i}< 2016 \Rightarrow a_{i+1}+...+a_{j}=1008 (đpcm)

\odot Nếu không có 2 số nào trong chúng cùng số dư khi chia cho 1008. Ta xét 1008 số S_{1},S_{2},...,S_{1008},S_{2} khi chia cho 1008 có ít nhất 2 số cùng số dư.

Do S_{1}=a_{1} \neq a_{2} Suy ra tồn tại k sao cho S_{k},a_{2} cùng số dư khi chia cho 1008.

Khi đó S_{k}-a_{2}=a_{1}+a_{3}+...+a_{k} \vdots 1008 Lại có 1 \leq a_{1}+a_{3}+...+a_{k} <2016

Suy ra a_{1}+a_{3}+...+a_{k}=1008. Bài toán được chứng minh \blacksquare

Combinatorics 1

Bài 1:

Có 2015  vận động viên thi đấu bóng bàn theo thể thức vòng tròn, mỗi đấu thủ đấu với tất cả các đấu thủ còn lại. Kết quả mỗi trận đấu chỉ có thắng hoặc thua, không có hòa. CMR có thể xếp 2015 vận động viên theo hang dọc sao cho người đứng trước thắng người đứng kề sau.

Lời giải:

Ta xét tất cả các cách xếp một sô vận động viên sao cho người đứng trước thắng người đứng kề sau. Do số cách xếp là hữu hạn nên ta chọn cách xếp có nhiều vận động viên nhất. Ta sẽ chứng minh cách xếp này thỏa mãn yêu cầu bài toán. Giả sử cách xếp Tn vận động viên A_{1},A_{2},…,A_{n}  (A_{i} thắng A_{i+1}) là cách xếp có nhiều vận động viên nhất và A là một vận động viên không thuộc A. Nếu A thắng A_1 thì ta có cách xếp A,A_{1},A_{2},…,A_{n} có nhiều vận động viên hơn T, suy ra A thua A_1. Lập luận tương tự ta có A thua A_{1},A_{2},…,A_{n} , khi đó ta có nhóm A_{1},A_{2},…,A_{n},A có nhiều vận động viên hơn nhóm T(mâu thuẫn). Từ đây ta có điều phải chứng minh \blacksquare