PHƯƠNG PHÁP ĐẾM BẰNG HAI CÁCH
(Dành cho học sinh lớp 10 chuyên toán)
Lời nói đầu
Đếm bằng hai cách là một phương pháp hay gặp trong đời sống, ví dụ bài toán sau: Một công ty nhập vào 3 xe hàng $ A, B, C $ gồm hai loại hàng $ I $ và $ II $. Trong đó xe $ A $ có 3 loại $ I $ và 2 loại $ II $, xe $ B $ có 4 loại $ I $ và 6 loại $ II $, xe $ C $ có 4 loại $ I $ và 6 loại $ II $. Tính số lượng hàng mà công ty nhâp vào. Đây là bài toán khá đơn giản, để giải bài toán ta có thể lập bảng và khi đó ta có thể tính bằng 2 cách như sau: Tính tổng số hàng trên mỗi xe rồi cộng lại; hoặc ta có thể tính tổng số hàng loại $ I $ trên 3 xe,tổng số hàng loại 2 trên 3 xe, rồi sau đó cộng lại.
Trên đây là một ví dụ của tính bằng hai cách, ta có thể tính tổng theo dòng hoặc có thể tính tổng theo cột. Tổng quát hơn ta có công thức đại số sau: $\sum_{i \in I,j \in J}a_{ij}=\sum_{j \in J}(\sum_{j \in J}a_{ij})=\sum_{j \in J}(\sum_{i \in J}a_{ij})$
Trong một số tình huống đề bài yêu cầu đếm số phần tử của một tập hợp mà không quan tâm ta đếm bằng cách nào, khi đó đếm bằng hai cách cho ta cùng một đáp số giống nhau, khi đó ta sẽ thiết lập được một đẳng thức tổ hợp. Một ví dụ đơn giản như đếm số tập con của tập có $ n $ phần tử, ta có thể đếm số tập có $ k $ phần tử với $ k = 0,1,…,n $, lấy tổng ta được $ C^0_n +C^1_n +….+C^n_n $. Nhưng nếu ta đếm bằng cách khác như sau: xét một tập hợp $ A $ bất kì, khi đó phần tử $ i $ có thể thuộc $ A $ hoặc $ i $ không thuộc $ A $, mỗi phần tử có 2 trường hợp, mà có $ n $ phần tử nên số tập $ A $ là $ 2^n $. Từ đó ta có đẳng thức $ C^0_n + C^1_n + …. + C^n_n = 2^n $. Đếm bằng hai cách cho ta một phương pháp để chứng minh đẳng thức liên quan tới hệ số khai triển nhị phân hay các đẳng thức tổ hợp.
Ngoài ra đếm bằng hai cách có thể áp dụng trong các bài toán bất đẳng thức, cực trị tổ hợp hay một số bài toán chứng minh sự tồn tại.
Để sử dụng phương pháp đếm bằng hai cách, đòi hỏi học sinh phải biết và vận dụng tốt các phép đếm cơ bản. Bài viết này được sử dụng để giảng dạy cho học sinh lớp 10 chuyên Toán, các em mới bước đầu làm quen với các bài toán tổ hợp nói chung và các bài toán đếm nói riêng nên ví dụ được nêu ra có độ khó không cao giúp các em làm quen với phương pháp này. Vì thời gian quá gấp rút nên không tránh khỏi sai sót, bạn đọc có thắc mắc xin liên hệ địa chỉ nguyentangvu@gmail.com,cảm ơn.
1. Chứng minh các đẳng thức tổ hợp
Ví dụ 1. Cho các số nguyên dương $ n $ và $ k $ với $ 0 < k \leq n $. Chứng minh các đẳng thức tổ hợp sau:
a) $ C_n^k=C^k_{n-1}+C^{k-1}_{n-1} $
b) $ \sum_{k \geq 0}C^{2k}_n=2^{n-1} $
Giải
a) Dễ thấy vế trái của đẳng thức là số cách chọn $ k $ phần tử từ $ n $ phần
tử. Để chọn $ k $ phần tử từ $ n $ phần tử ta có thể làm như sau: Xét phần tử
$ a $, nếu $ a $ được chọn thì ta cần chọn thêm $ k−1 $ phần tử từ $ n−1 $
phần tử còn lại ta có $ C^{k−1}_{ n−1} $ cách. Nếu $ a $ không được chọn,
ta chọn $ k $ phần tử từ $ n−1 $ phần tử còn lại, ta có $ C^k_ {n−1} $. Do
đó số cách chọn trong hai trường hợp là $C^k_{n-1}+C^{k-1}_{n-1} $. Từ
đó ta có điều cần chứng minh.
b) Ta xét bài toán “đếm số cách chọn một số chẵn phần tử từ $ n $ phần tử”.Ta có thể đếm theo cách sau:
Cách 1: Ta có số cách chọn $ 2k $ phần tử từ $ n $ phần tử là $ C^{2k}_n $ . Khi
đó $ \sum_{k \geq 0}C^{2k}_n $ lần tổng số cách chọn một số chẵn phần tử từ
$ n $ phần tử.
Cách 2: Xét một phần tử $ a $, thì có hai khả năng $ a $ được chọn hoặc $ a $
không được chọn, ta có 2 trường hợp. Khi đó với $ n−1 $ phần tử đầu tiên, thì
số trường hợp là $ 2^{n−1} $. Tới phần tử thứ $ n $, nếu ta đã chọn được một
số chẵn phần tử thì ta không chọn, còn nếu ta đã chọn được một số lẻ phần
tử thì phần tử này sẽ được chọn, do đó số cách chọn là $ 2^{n−1} $.
Ví dụ 2. Cho các số nguyên dương $ n $ và $ k $ với $ 0 \leq k \leq n $. Chứng minh rằng:
a) $ kC^k_n=nC^{k-1}_{n-1} $
b) $ \sum_{k=0}^{n}kC^k_n=n2^{n-1} $
Giải
a) Xét bài toán “Một đội văn nghệ có n thành viên, có bao nhiêu cách chọn
$k$ người thể hiện một tiết mục hát tốp ca trong đó có một bạn hát sô lô”.
Cách 1: Chọn đội văn nghệ gồm $ k $ người từ $ n $ ta có số cách là $ C^k_n $,
từ $ k $ người này ta chọn một người hát sô lô có $ k $ cách. Khi đó số cách
chọn là $ kC^k_n $.(1)
Cách 2: Chọn người hát sô lô trước, có $ n $ cách, sau đó chọn $ k−1 $ người từ
$ n−1 $ người còn lại có $ C^{k−1}_{n−1} $ cách.
Vậy số cách chọn là $ nC^{k−1}_{n−1} $. (2)
Từ (1) và (2) ta có đẳng thức $ kC^k_n = nC^{k−1}_{n−1}. $
b) Xét bài toán “Từ $ n $ thành viên của đội văn nghệ, có bao nhiêu cách lập một nhóm hát trong đó có một nhóm trưởng?”. Làm tương tự như câu trên ta sẽ có đẳng thức cần chứng minh.
Ví dụ 3. Cho các số nguyên dương $ n $ và $ k $ với $ 0 \leq k \leq n $. Chứng minh rằng:
a) $ \sum_{m=k}^{n}C^k_m=C^{k+1}_{n+1} $
b) $ \sum_{m=k}^{n-k}C^k_mC^k_{n-m}=C^{2k+1}_{n+1} $
với $ 0 \leq k \leq\dfrac{n}{2} $.
Giải
a) Xét tập $ X = {1,2,…,n + 1} $. Khi đó ta đếm số tập con có $ k + 1 $ phần tử của $ X $.
Cách 1: Rõ ràng số tập con là $ C^{k+1}_{ n+1} $.
Cách 2: Ta chọn tập con sao cho phần tử lớn nhất là $ m $. Khi đó số tập con
có phần tử lớn nhất $ m $ là $ C^k_m $. Vì $ k \leq m \leq n $ nên ta có số tập
con là $ C^k_k + C^k_{k+1} + … + C^k_n $. Từ đó suy ra đẳng thức cần chứng
minh.
b) Xét bài toán “Đếm số tập con có $ 2k+1 $ phần tử của $ X $”.
Cách 1: Số tập con là $ C^{2k+1}_n $.
Cách 2: Ta xét phần tử thứ $ k + 1 $, giả sử đó là $ m $, khi đó ta chọn $ k $
phần tử nhỏ hơn $ m $ và $ k $ phần tử lớn hơn $ m $, số cách chọn là
$ C^k_mC^k_{n−m} $, vì $ k \leq m \leq n−k $ nên ta có số cách chọn là
$ \sum_{m=k}^{n-k} C^k_mC^k_{n-m}$.
Từ đó ta có đẳng thức cần chứng minh.
Bài tập
Bài 1 Cho $ 0 \leq k \leq m \leq n. $ Chứng minh các đẳng thức sau:
a) $ C^k_mC^m_n=C^k_nC^{m-k}_{n-k} $
b) $ \sum_{k \geq 0}k(C^k_n)^2=nC^{n-1}_{2n-1} $
c) $ \sum_{k \geq 0}C^k_nC^{m-k}_{n-k}=2^mC^m_n $
Bài 2. Chứng minh các đẳng thức sau:
a) $\sum_{i=0}^{k} C^i_n C^{k-i}_{n-i} = 2^kC^k_n$
b) $ kC^k_m C^0_p+(k-1)C^{k-1}_m C^1_p+…+C^1_mC^{k-1}_p$
$=\dfrac{m}{m+p}.k.C^k_{m+p} $
Ví dụ 4. Trong một hội nghị, mỗi thành viên tham gia đúng 3 cuộc họp và mỗi cuộc họp thì có đúng 6 thành viên tham gia. Chứng minh rằng số cuộc họp thì bằng nửa số thành viên tham gia hội nghị.
Giải
Gọi số thành viên là $ n $, số cuộc hộp là $ m $. Khi đó mỗi cuộc họp có 6 thành viên tham gia, nên tổng số lượt thành viên tham gia $ m $ cuộc họp là $ 6m $ (có lặp lại). Tương tự mỗi thành viên tham gia 3 cuộc họp mà có $ n $ thành viên nên số lượt thành viên tham gia là $ 3n $. Do đó $ 3n = 6m $ hay $ n = 2m $.
Trong bài toán trên ta có thể làm như sau: giả sử có $ m $ cuộc họp là $ 1,2,…,m $ và $ n $ thành viên là $ 1,2,3,…,n $. Xét bảng vuông $ m \times n $ gồm $ m $ dòng và $ n $ cột trên đó ghi các số dòng thứ $ i $ cột $ j $ là $ aij $ thỏa $ aij = 1 $ nếu người $ j $ tham gia cuộc họp thứ $ i $ và $ a{ij} = 0 $ trong trường hợp ngược lại. Ta được bảng sau:
Dựa vào trên, ta thấy mỗi dòng có 6 số 1 và mỗi cột có 3 số 1. Khi đó ta có $ 6m = 3n $ hay $ n = 2m $.
Bảng trên được gọi là một ma trận nhị phân, dùng để biểu diễn các mối quan hệ hai ngôi như phần tử thuộc tập hợp, quen nhau, đồ thị… và là mô hình biểu diễn rất hữu dụng trong các bài toán tổ hợp. Trong mỗi bảng nhị phân trên, nếu gọi $ r_i $ là số số 1 ở dòng thứ $ i $ và $ c_j $ là số số 1 ở cột thứ $ j $, ta có :
$ \sum_{i=1}^{m}r_i=\sum_{j=1}^{n}cj $
Ví dụ 5 (HK 1994) Trong một trường học có $ m $ giáo viên và $ n $ học sinh thỏa điều kiện sau:
i) Mỗi giáo viên dạy đúng p học sinh.
ii) Với hai học sinh phân biệt thì có đúng $ q $ giáo viên dạy họ.
Chứng minh rằng $ \dfrac{m}{q}=\dfrac{n(n-1)}{p(p-1)} $
Giải
Lập bảng gồm $ m $ dòng và $ n $ cột trong đó $ aij = 1 $ nếu giáo viên $ i $ dạy học sinh $ j $, và bằng $ 0 $ nếu ngược lại. Khi đó từ (i) thì mỗi dòng có đúng $ p $ số $ 1 $. Ta đếm các cặp số $ (1;1) $ trên cùng một dòng. Nếu đếm theo dòng thì mỗi dòng có $ C^2_p $ cặp, có $ m $ dòng nên số cặp là $ mC^2_p $. (1)
Nếu đếm theo cột, do điều kiện (ii) nên với hai cột bất kì thì có đúng $ q $ cặp. Do đó số cặp là $ qC^2_n $ (2). Từ (1) và (2) ta có $ mC^2_p=qC^2_n $ hay $ \dfrac{m}{q} =\dfrac{n(n-1)}{p(p-1)}$.
Trên đây là một kĩ thuật đếm theo cặp $ (1;1) $ cùng một dòng hoặc cùng một cột. Ta có mệnh đề sau:
Định lý 1. Nếu trong một bảng nhị phân $ m \times n, $ mỗi dòng có $ k $ số 1, hai cột bất kỳ có đúng $ p $ cặp $ (1;1) $ cùng một dòng.
Khi đó ta có $ pC^2_n=kC^2_m. $
Bài tập
Bài 1. Cho tập $ X = {1,2,…,8} $ và các tập $ A1,A2,…,A6 $ là các tập con của $ X $ sao cho mỗi tập $ Ai $ có $ 4 $ phần tử và mỗi phần tử của $ S $ thuộc $ m $ tập $ Ai $. Tìm $ m $.
Bài 2. Trong một vòng thi toán chung kết tại trường PNTK, các thí sinh phải giải 9 bài toán. Biết rằng mỗi thí sinh giải được đúng 6 bài, và với hai thí sinh bất kì thì giải đúng chung 3 bài. Tìm số thí sinh dự thi.
Bài 3. Gọi $ p(n,k) $ là số hoán vị của $ {1,2,…,n} $ có $ k $ điểm bất động. Chứng minh rằng:
$ \sum_{k=1}^{n}kp(n,k)=n! $
2. Chứng minh các bài toán bất đẳng thức và cực trị tổ hợp
Ví dụ 6. (Iran 2011) Cho $ n $ điểm trên mặt phẳng sao cho không có 3 điểm nào thẳng hàng. Chứng minh rằng số tam giác có diện tích bằng 1 có các đỉnh thuộc $ n $ điểm trên không vượt quá $ \dfrac{2}{3}(n^2-n) $.
Giải
Bài toán này ta đi tính số cặp (cạnh;tam giác). Với đoạn thẳng $ AB $, khi đó nếu điểm $ C $ thỏa $ S_{ABC} = 1 $ thì khoảng cách từ $ C $ đến $ AB $ bằng $ \dfrac{2}{AB} $ , vì không có 3 điểm nào thẳng hàng nên chỉ có nhiều nhất 4 điểm thỏa. Vậy với 1 đoạn ta sẽ có nhiều nhất 4 tam giác có diện tích 1 nhận đoạn thẳng đó làm đỉnh. Suy ra tổng số cặp nhiều nhất là $ 4C^2_n $.
Mặt khác nếu gọi số tam giác là $ m $ thì tổng số cặp là $ 3m $.
Từ đó ta có: $ 3m \leq 4C^2_n $ hay $ m \leq \dfrac{2}{3}(n^2-n) $.
Ví dụ 7.(USA TST 2005) Cho $ n > 1 $. Với số nguyên dương $ m $. Đặt $ X_m = {1,2,…,mn} $. Xét họ $ T $ gồm $ 2n $ tập hợp thỏa các điều kiện sau:
i) Mỗi phần tử của $ T$ là một tập con có $ m $ phần tử của $ X_m. $
ii) Mỗi cặp thuộc $ T $ có nhiều nhất một phần tử chung.
iii) Mỗi phần tử thuộc $ X_m $ thuộc đúng hai tập của $ T. $
Tìm giá trị lớn nhất của $ m $ theo $ n. $
Giải
Xét bảng vuông sao cho gồm $ 2n $ dòng và $ mn $ cột sao cho $ a_{ij} =1$ nếu số $ j $ thuộc $ a_i $ và bằng $ 0 $ trong trường hợp ngược lại.
Ta xét bài toán đếm số cặp $ (1;1) $ cùng một cột. Do (i) nên ta có số cặp nhiều nhất là $ C^2_{2n} $.
Do (ii) nên ta có số cặp là $ mn $.
Do đó $ mn \geq C^2_ {2n} $, suy ra $ m \geq 2n−1 $. Nếu $ m = 2n−1 $, ta xét mô hình sau. Cho $ 2n $ đường thẳng không có 3 đường nào đồng quy và không có hai đường nào song song. Khi Xm là tập các giao điểm và $ T $ là họ gồm các điểm thuộc một đường thẳng. Rõ ràng đây là mô hình thỏa đề bài. Bảng sau cho ví dụ $ n=2, m=3 $.
Giải
Cũng như ví dụ trên, ta thấy việc biểu diễn các mối quan hệ bằng bảng nhị phân rất thuận lợi trong việc trình bày lời giải. Trong bài này ta cũng có thể lập bảng $ b \times a $ theo quy tắc sau: dòng i cột j bằng 1 nếu giám khảo i cho thí sinh j đậu. Ta sẽ đếm số cặp $ (0;0) $ và $ (1;1) $ cùng một cột bằng hai cách.
Cách 1 ta đếm theo dòng: Vì với hai vị giáo bất kì có nhiều nhất $ k $ kết luận giống nhau nên với hai dòng bất kì có $ k $ cặp, do đó số cặp nhiều nhất là $ kC^2_b $.
Cách 2 ta đếm theo cột: Trong mỗi cột số cặp là $ C^2_m+C^2_n $ cặp, trong đó $ m $ là số các số $ 0 $ và $ n $ là số các số $ 1, $ ta có $ m+n=b=2t+1, $ suy ra $ n=2t+1-m. $
Khi đó $ C^2_m+C^2_n=\dfrac{m(m-1)+(21-m)(2t-m-1)}{2}=\dfrac{(2t-m)^2+m^2}{2} \geq t^2=\dfrac{(b-1)^2}{4}. $
Từ đó ta có $ kC^2_b \geq \dfrac{a(b-1)^2}{4} $, suy ra $ \dfrac{k}{a} \geq \dfrac{b-1}{2b.} $
Ví dụ 9. Cho $ n $ điểm trong mặt phẳng. Chứng minh rằng số cặp điểm có
khoảng cách bằng 1 không quá $ \dfrac{n}{4}+\dfrac{\sqrt{2n^3}}{2}. $
Giải
Gọi $ d_i $ là số đoạn thẳng có độ dài 1 mà có đỉnh là $ A_i $. Đặt khi
đó số cặp điểm là $ k = \dfrac{1}{2} (d_1 + d_2 + … + d_n) $. Ta đếm số cặp
$ (A,B) $ mà khoảng cách từ $ A,B $ đến $ A_i $ bằng 1. Số cặp là $ C^2 _{di} $,
suy ra tổng số cặp là $ \sum_{i=1}^{n}C^2_{d_i} $. Ta biết rằng hai điểm $ C,D $
thì có chung nhiều nhất một cặp $ (A,B) $ nên số cặp không vượt quá
$ 2C^2_n $. Do đó: $ \sum_{i=1}^{n}C^2_{d_i} \leq n(n-1) $
hay $ \dfrac{2k(2k-n)}{2n} \leq n(n-1) \Leftrightarrow 2k^2-nk-n^2(n-1) \leq 0 $
Do đó $ k \leq \dfrac{n}{4}+\dfrac{\sqrt{2n^3}}{2} $
3 Các bài toán tồn tại
Ví dụ 10. Cho 133 số nguyên dương, có ít nhất 799 cặp số là nguyên tố cùng nhau. Chứng minh rằng tồn tại 4 số nguyên dương phân biệt $ a,b,c,d $ sao cho $ a $ và $ b; b $ và $ c, c $ và $ d; d $ và $ a $ nguyên tố cùng nhau.
Giải
Mỗi số được đại diện bởi một điểm, hai số nào nguyên tố cùng nhau thì hai điểm tương ứng được nối nhau bởi một đoạn. Ta cần chứng minh có 4 đoạn $ AB,BC,CD,DA $. Ta cần chứng minh rằng có hai điểm $ B $ và $ D $ cùng nối với hai điểm $ A $ và $ C $.
Gọi $ d_i $ là số cạnh có đỉnh là $ A_i $. Khi đó ta có
$ d_1 + d_2 + … + d_{133} = 2 \times 799 $. Nếu hai đỉnh $ Y, Z $ cùng nối với đỉnh $ X $ thì ta sẽ xem $ (Y;Z) $ là một cặp. Ta sẽ tính số cặp này. Rõ ràng, tổng số cặp là
$ \sum_{i=1}^{133} C^2_{d_i}$
$=\dfrac{1}{2}\left(\sum_{i=1}^{133}d^2_i-\sum_{i=1}^{133}d_i \right) $
Ta có
$ \sum_{i=1}^{133}d^2_i \geq \dfrac{1}{133} \left(\sum_{i=1}^{133}d_i \right)^2 $
Do đó
$ \sum_{i=1}^{133}C^2_{d_i} \geq \dfrac{1}{2}(\dfrac{1}{133}(\sum_{i=1}^{133}d_i)^2)$
$-\sum_{i=1}^{133}d_i ]>C^2_{133} $
Nhưng $ 133 $ điểm thì có $ C^2_{133} $ cặp, nên sẽ có một cặp nào đó được tính hai lần, tức là tồn tại cặp $ (A,C) $ cùng được nối với $ B$ và $ D $. Tức là ta có 4 đoạn $ AB, BC,CD,DA. $
Ví dụ 11. Cho tập $ X $ có $ n $ phần tử, gọi $ A_1,A_2,…,A_m $ là một họ các tập con của $ X $, sao cho $ |Ai| = 3 $ và $ |A_i \cap A_j| \leq 1 $ với $ i \neq j $. Chứng minh rằng tồn tại một tập con $ A $ của $ X $ có ít nhất $ [\sqrt{2n}] $ phần tử và không chứa bất kì tập $ A_i $ nào.
Giải
Ta xét tập tất cả các tập con của $ X $ mà không chứa bất kỳ tập $ A_i $ nào, khi đó dễ thấy tập này là khác rỗng (xét tập có 2 phần tử là thỏa) và hữu hạn, nên tồn tại một tập $ M $ có nhiều phần tử nhất. Đặt $ |M|=k $. Khi đó, do $ M $ có số phần tử lớn nhất nên mọi tập có số phần tử lớn hơn $ M $ đều chứa một tập $ A_i. $ Xét tập $ M’=X \setminus M= \{a_1,a_2,…,a_{n-k}\} $. Khi đó $ M \cup \{a_i\} $ có $ k+1 $ phần tử, nên theo cách xác định $ M $ thì sẽ tồn tại $ A_i \subset M’,$ do $ A_i \nsubseteq M $ nên $ A_i=\{a_i,x,y\} $ trong đó $ x,y \in M. $
Hơn nữa hai tập giao nhau có không quá một phần tử nên với mỗi $ a_i $ có nhiều nhất một cặp $ (x,y) \in A_i$. Ta đếm số cặp $ (x,y) $ theo hai cách:\\
Số cặp $ (x,y) \in X $ là $ C_k^2. $
Vì $ i=1,2,…,n-k $ nên có $ n-k $ cặp. Vậy ta có:
$ n-k \leq C^2_k \Leftrightarrow k^2+k \geq 2n $
Mà $ k \leq \sqrt{k^2+k} \leq k+1, $ suy ra $ k \geq [\sqrt{2n}] $. Ta có điều cần chứng minh.
Bài tập rèn luyện
Bài 1. Cho 7 tập $ A1,A2,…,A7 $ là các tập con của $ X = {1,2,3,4,5,6,7} $, sao cho mội cặp phần tử thuộc $ X $ thuộc đúng một tập con, và $ |Ai|\geq 3 $ với mọi $ i $. Chứng minh rằng $ |A_i \cap Aj| = 1 $ với mọi $ i,j. $
Bài 2. Cho 16 bạn học sinh làm một bài kiểm tra trắc nghiệm, trong đó mỗi câu hỏi có 4 lựa chọn. Sau bài kiểm tra, ta thấy rằng với hai học sinh bất kì có nhiều nhất một câu trả lời giống nhau. Hỏi bài kiểm tra có nhiều nhất bao nhiêu câu hỏi?
Bài 3. Một hội nghị có n thành viên tham gia, hội nghị đã tổ chứng $ n + 1 $ cuộc họp, trong đó mỗi cuộc họp có đúng 3 người và không có cuộc họp nào có thành viên giống nhau. Chứng minh rằng có hai cuộc họp mà có chung đúng một thành viên.
Bài 4. (China 1996) Trong một hội nghị có 8 người tham gia, hội nghị tổ chức $ m $ cuộc họp, mỗi cuộc họp có đúng 4 người tham gia. Hơn nữa hai người bất kì thì cùng tham gia một số cuộc họp như nhau. Tìm giá trị nhỏ nhất của $ m $.
Bài 5. Cho $ A1,A2,…,Ak $ là các tập con của $ S = {1,2,…,10} $ sao cho:
i) $ |A_i| = 5,i = 1,2,…,k. $
ii) $ |A_i \cap A_j| \leq 2, 1 \leq i < j \leq k. $ Tìm giá trị lớn nhất của $ k $.
Bài 6. (IMO 2001) Có 21 bạn nam và 21 bạn nữ tham dự một kì thi học sinh giỏi toán. Biết rằng:
a) Mỗi bạn giải được nhiều nhất sáu bài.
b) Mỗi cặp một nam và một nữ thì có ít nhất một bài toán được giải bởi hai người đó.
Chứng minh rằng có môt bài toán mà giải được bởi ít nhất 3 nam và 3 nữ.
Bài 7. (USAMO 2001) Có 8 hộp, mỗi hộp chứa 6 viên bi. Mỗi viên bi được tô màu sao cho:
i) Mội hộp chứa các viên bi khác màu.
ii) Không có hai màu nào cùng xuất hiện nhiều hơn trong một hộp.
Tìm số màu ít nhất cần dùng.
Bài 8. (IMO 1989) Cho $ n $ và $ k $ là các số nguyên dương và $ S $ là tập $ n $ điểm trong mặt phẳng sao cho:
i) Không có 3 điểm nào thẳng hàng,
ii) Với điểm $ P $ bất kì thuộc $ S $ thì có ít nhất $ k $ điểm của $ S $ cách đều $ P $.
Chứng minh rằng: $ k<\dfrac{1}{2}+\sqrt{2n} $
Bài 9. (IMO 2005) Trong một cuộc thi toán trong đó đề thi có 6 bài. Mỗi một cặp bài toán được giải bởi nhiều hơn $ \dfrac{2}{5} $ số thí sinh. Không có ai giải được 6 bài. Chứng minh rằng có ít nhất 2 thí sinh giải được đúng 5 bài.
Bài 10. Trong một hội nghị có 35 người tham gia. Biết rằng có 111 cặp đôi một quen nhau. Chứng minh rằng có thể chọn ra 4 thành viên xếp ngồi vào một bàn tròn sao cho hai người ngồi gần nhau thì quen nhau.
