Một số vấn đề liên quan đến toán tổ hợp

BCDE và suy ra 5 đường tròn có tâm là 5 đỉnh của ngũ giác và có bán kính là 1 sẽ phủ hết đa giác này. Như vậy, bài toán được chứng minh.
Bài 6: (Olympic 30/4 năm 2014) Cho đa giác đều 9 đỉnh A1A2A9. Mỗi đỉnh của đa giác hoặc có màu đỏ hoặc có màu xanh. Chứng minh tồn tại 2 tam giác phân biệt bằng nhau có tất cả các đỉnh là đỉnh của đa giác cùng màu.
Giải: Theo nguyên lý Dirichlet thì tồn tại 5 đỉnh có cùng màu
Ta vẽ đường tròn ngoại tiếp đa giác đều 9 đỉnh, 9 đỉnh này chia đường tròn thành 9 phần.
Gọi (x,y,z) là số đo cung ( đơn vị phần ) của 1 bộ ba đỉnh. Không mất tính tổng quát, giả sử x≤y≤z. Ta tính được số các bộ ( x,y,z) là 6. Trong 5 đỉnh cùng màu có C52=10 tam giác. Theo nguyên lý Dirichlet thì có ít nhất 2 tam, giác có cùng bộ (x,y,z) (đpcm).
Bài 7: Trong một hình vuông có cạnh là 1 chứa một số đường tròn. Tổng tất cả chu vi của chúng là 10. CMR tồn tại 1 đường thẳng cắt ít nhất 4 đường tròn trong tất cả những đường tròn đó?
Giải: Ta chọn 1 cạnh hình vuông rồi chiếu vuông góc các đường tròn xuống cạnh đó. 
Ta có: Hình chiếu của 1 đường tròn bán kính R xuống AB là 1 đoạn thẳng có độ dài 2R.Vì vậy trên cạnh hình vuông đã chọn có những đoạn thẳng chiếu xuống với tổng độ dài là 10π. Mà 10π > 3 nên theo nguyên lý Dirichlet đối ngẫu suy ra có 1 điểm M nào đó thuộc AB là điểm trong chung có ít nhất 4 đoạn thẳng đã chiếu xuống. Khi đó, đường thẳng đi qua M vuông góc với AB cắt ít nhất 4 trong những đường tròn đó.
Bài 8: Cứ mỗi điểm trong mặt phẳng được tô bằng một trong hai màu đen và trắng. CMR tồn tại hình chữ nhật có các đỉnh cùng màu.
Giải: Giả sử ta có 1 lưới ô vuông tạo bởi 3 đường thẳng nằm ngang và 9 đường thẳng nằm dọc, mỗi nút lưới được tô bởi màu đen hoặc trắng.
Xét 3 nút lưới của 1 đường nằm dọc, mỗi nút có 2 cách tô màu nên mỗi bộ nút trên 2 đường nằm dọc ấy có 2.2.2=8 cách tô màu. Có 9 đường dọc, mỗi đường có 8 cách tô màu nên theo nguyên lí Dirichlet thì tồn tại 2 đường có cách tô màu như nhau. Giả sử 2 bộ ba điểm đó là A,B,C và X,Y,Z.
Vì 3 điểm A, B, C chỉ được tô bởi 2 màu nên tồn tại 2 điểm được tô bởi cùng 1 màu, chẳng hạn 2 điểm B và C. Khi đó, hình chữ nhật BYZC có 4 đỉnh được tô bởi cùng 1 màu.
Bài 9: Chứng minh rằng từ 6 số vô tỉ tùy ý có thể chọn ra được 3 số ( ta gọi ba số đó là a, b,c ) sao cho a+ b, b+ c, c+a cũng là số vô tỉ.
Giải: Xét trên mặt phẳng 6 điểm sao cho không có 3 điểm nào thẳng hàng. Với mỗi điểm, ta sẽ gắn cho nó 1 số vô tỉ. Như vậy sáu điểm được gắn sáu số vô tỉ đã cho. Hai điểm mang số a và b sẽ được nối với nhau bằng đoạn thẳng màu đỏ nếu a+b là số vô tỉ, còn màu xanh khi a + b là số hữu tỉ. Theo đề bài, tồn tại ít nhất 1 tam giác cùng màu. Giả sử tam giác đó có 3 đỉnh được gắn số a, b,c. Có 2 khả năng xảy ra:
1) Nếu tam giác đó là tam giác xanh. Khi đó, a + b, b+c, c+a là 3 số hữu tỉ. Lúc này (a+b) + (b+c) – (c+a) =2b cũng là một số hữu tỉ. Điều này vô lý vì b là số vô tỉ. 
2) Nếu tam giác ấy là tam giác đỏ. Khi ấy a+b, b+c, c+a là 3 số vô tỉ. Đpcm.
Nhận xét: Bài toán bề ngoài có vẻ không liên quan gì đến hình học nhưng lại có thể quy về bài toán hình học với một lời giải đẹp mắt.
Bài 10: Trong hình vuông cạnh 15 đặt 20 hình vuông nhỏ cạnh 1 từng đôi một không cắt nhau. Chứng minh rằng trong hình vuông lớn có thể đặt một hình tròn bán kính bằng 1 sao cho nó không cắt hình vuông nào.
Giải: Xét hình gồm tất cả các điểm cách hình vuông nhỏ cạnh 1 một khoảng không lớn hơn 1. Rõ ràng hình tròn bán kính bằng 1 có tâm nằm ngoài hình đó không thể cắt hình vuông nhỏ. Diện tích hình tròn đó bằng 5+n. Tâm hình tròn cần tìm cũng cần phải cắt các cạnh của hình vuông lớn hơn một khoảng cách lớn hơn 1, tức là ở bên trong hình vuông cạnh 13. Vì 20(5+n) <132. Hình tròn có tâm tại điểm không bị phủ có tính chất thỏa mãn đề bài.
B.BẤT BIẾN VÀ ĐƠN BIẾN:
Lý thuyết: 
- Bất biến là những đại lượng (hay tính chất) không thay đổi trong quá trình chúng ta thực hiện các phép biến đổi.
- Đơn biến là một đại lượng luôn thay đổi nhưng chỉ theo 1 chiều( tức là tăng lên hay giảm xuống).
Bài tập: 
Bài 1: Các số 1,2,3,,20 được viết lên bảng. Mỗi phép biến đổi, ta xóa 2 số a, b và thêm vào số a + b -1. Số nào sẽ còn lại trên bảng sau 19 nước?
Giải: Với bộ n số trên, ta xét đại lượng X bằng tổng các số trên bảng trừ đi n. Khi đó, X không thay đổi trong các phép biến đổi.
Lúc đầu X= ( 1+ 2+ 3++20)-20=190. Sau 19 bước, X = 190 hay số còn lại sẽ là 191.
Bài 2: Trên bảng viết các số 1,2,3,,1000. Ở mỗi bước cho phép thay một số bằng tổng các chữ số của nó. Qua trình dừng lại khi có toàn các số có một chữ số. Hỏi số số 1 còn lại trên bảng nhiều hơn hay số số 2 còn lại trên bảng nhiều hơn?
Giải: Nếu chúng ta viết tất cả các số này theo modulo 9 thì các số là bất biến trong các phép biến đổi. Do số các số đồng dư 1 mod 9 nhiều hơn số các số đồng dư 2 mod 9 trong tập { 1,2,,1000}, số các số 1 còn lại trên bảng sẽ nhiều hơn số các số 2 còn lại trên bảng.
Bài 3: Hình vuông 8x8 bỏ đi 2 ô ở góc đối nhau. Có thể phủ phần còn lại bởi 31 quân domino 1x2 được không?
Giải: Chúng ta tô màu hình vuông đen trắng như bàn cờ vua. Hai góc đối nhau luôn cũng màu nên khi bỏ chúng đi, số ô đen khác số ô trắng. Mỗi quân domino phủ đúng một ô đen, một ô trắng nên phần còn lại của hình vuông không thể phủ kín được bởi các quân domino.
Bài 4: Cho đa thức P( x ) = ax2 +bx +c, có thể thực hiện 1 trong 2 phép biến đổi:
a) Đổi chỗ a và c
b) Đổi biến x bởi x+ t với t ∈ R
Hỏi tx2 – 31x – 3 có thu được x2 – 20x -12 không? 
Giải: Bất biến của chúng ta là định thức Δ= b2 – 4ac của đa thức P(x) = ax2 +bx+c. Dễ kiểm tra rằng 2 phép biến đổi a) và b) không làm thay đổi định hướng của đa thức. Định thức Δ1 của x2 – 31x – 3 và định thức Δ2 của x2 -20x -12 là khác nhau. Ta có câu trả lời phủ định.
Bài 5: (Russian MO 1995) Cho 3 đống sỏi khác nhau. Sisyphus thực hiện di chuyển 1 viên sỏi từ 1 trong 3 đống sỏi sang 1 trong 2 đống sỏi còn lại. Mỗi lần chuyển sỏi, Sisyphus nhận được từ Zeus một số tiền bằng hiệu số giữa số sỏi của đống sỏi lấy đi và đống sỏi nhận thêm trước khi di chuyển. Nếu số chênh lệch này âm thì Sisyphus cũng phải trả cho Zues số tiền chệnh lệch đó. Trong một số bước thực hiện thì số sỏi mỗi đống sẽ trở về như ban đầu. Hỏi khi đó, số tiền tối đa mà Sisyphus nhận được là bao nhiêu?
Giải: Ta chứng minh tổng sau là bất biến a(a+1)/2 + b(b+1)/2 + c(c+1)/2 +s
Với a,b,c là số sỏi mỗi đống ban đầu và s là số tiền Sisyphus nhận được từ một thời điểm nào đó. Thật vậy, ta chuyển 1 viên sỏi từ đống sỏi có a viên sỏi sang đống sỏi có b viên sỏi. Khi đó số tiền Sisyphus nhận được hoặc mất đi là a-b.
Ta có: (a – 1)(a – 2)/2 + b(b – 1)/2 + c(c-1)/2 + s + a – b =a(a-1)/2 + b(b-1)/2 +c(c-1)/2 + s.
Do đó, đến khi số sỏi trở về ban đầu thì số tiền Sisyphus nhận được bằng số tiền ban đầu. Mà ban đầu Sisyphus không có tiền do đó đến thời điểm này Sisyphus cũng không có tiền.
Bài 6: ( IMO Shortlish 1994, Thụy Điển) Có 1994 cô gái ngồi quanh 1 bàn tròn, họ chơi chung 1 cỗ bài gồm n lá. Ban đầu, một cô giữ tất cả các lá bài. Cứ mỗi nước đi, nếu có ít nhất 1 cô gái giữ tối thiểu 2 lá bài, thì 1 trong các cô gái này chuyển 1 lá bài cho 1 trong 2 cô gái bên cạnh cô ấy. Trò chơi kết thúc khi và chỉ khi mỗi cô gái chỉ giữ nhiều nhất 1 lá bài.
a) Chứng minh rằng nếu n ≥ 1994 thì trò chơi không thể nào kết thúc được.
b) Chứng minh rằng nếu n< 1994 thì trò chơi bắt buộc phải kết thúc.
Giải: 
a) Nếu n> 1994 thì theo nguyên lí Dirichlet có ít nhất 1 cô gái giữ 2 lá bài, vì thế, trò chơi không bao giờ kết thúc được. Nếu n = 1994.
Gọi các cô gái là G1, G2,,G1994 và giả sử ban đầu G1 giữ tất cả các lá bài. Ta định nghĩa giá trị tạm thời của 1 lá bài là i nếu Gi đang giữ nó, 1≤n≤ 1994. Gọi S là tổng các giá trị tạm thời của các lá bài. Ban đầu, S=1994.
Nếu 1 cô gái khác với G1 hoặc G1994 chuyển lá bài thì S không đổi. Nếu G1 hoặc G1994 chuyển lá bài thì S tăng lên hoặc giảm đi 1994.
Suy ra S = 1994h, với h là số nguyên nào đó.
Khi trò chơi kết thúc, mỗi cô gái sẽ giữ đúng lá bài, do đó, lúc này S=997.1995. Nhưng như thế thì phải có 2h = 1995, điều này không thể.
Tóm lại, nếu n≥ 1994 thì trò chơi không thể nào kết thúc.
Khi một cô này chuyển 1 lá bài cho cô kia ở lần thứ nhất, cả hai sẽ đánh dấu tên mình lên đó. Lần sau đó, nếu một trong 2 người kia phải chuyển bài, cô ta sẽ đưa đúng lá bài được đánh số cho người kia.
Nếu làm như thế, lá bài được đánh dấu sẽ kẹt lại giữa 2 cô gái kề nhau nói trên. Nếu n< 1994, sẽ có 2 cô gái kề nhau không bao giờ chuyển lá bài cho nhau. 
Bây giờ, giả sử khi làm thế mà trò chơi không kết thúc được, thì tồn tại ít nhất 1 cô gái chuyển bài đến vô hạn lần. Từ đó suy ra có 1 cô chuyển bài đến vô hạn lần, trong khi 1 cô kề bên cô ta chỉ chuyển hữu hạn lần.
Khi cô bên này thực sự không chuyển nữa ( vì chỉ chuyển hữu hạn lần ) thì đống bài của cô ấy vẫn tiếp tục tăng lên. Điều này rõ ràng mâu thuẫn.
Bài 7: ( Bungary MO 1999 ) Ba đống sỏi có 51, 49 và 5 viên. Ta thực hiện 1 trong hai nước đi như sau. Một nước là dồn 2 đống tùy ý thành 1 đống. Nước đi khác là chọn đống có chẵn viên sỏi để chia thành 2 đống bằng nhau. Hỏi có thể thực hiện 1 dãy các nước đi như thế để chia 3 đống thành 105 đống mà mỗi đống chỉ có 1 viên sỏi hay không?
Giải: Ban đầu số sỏi trong 3 đống đều là số lẻ nên bước đi đầu tiên là dồn 2 đống lại.
Trường hợp 1: Dồn 2 đống có 5 và 49 viên, ta có 2 đống là 51 và 54 viên, mỗi đống đều là bội của 3. Bước thứ 2 ta chia đống thành 2 đống có 54 viên thành 2 đống có 27 viên. Bây giờ, số sỏi trong cả 3 đống là 51, 27,27 cùng chia hết cho 3.
 Vì cả ba đống có số lẻ viên nên bước thứ 3 ta phải gộp 2 đống có 27 và 51 viên thành đống có 78 viên. Vì 2 số 27 và 51 đều chia hết cho 3 nên tổng (=78) của chúng cũng chia hết cho 3. Tức là khi thực hiện các nước đi luân phiên thì số sỏi trong mỗi đống luôn là bội của 3.
Đây chính là bất biến trong trường hợp này. Thật vậy, khi gộp 2 đống sỏi có số sỏi chia hết cho 3 thì được 1 đống sỏi có số sỏi chia hết cho 3 và nếu chia 1 đống sỏi ( là gộp cả 2 đống có số sỏi lẻ cùng chia hết cho 3 ) có số chẵn viên sỏi chia hết cho 3 thành 2 phần bằng nhau thì số sỏi trong mỗi phần vẫn chia hết cho 3. Do đó, số sỏi trong mỗi đống vẫn chia hết cho 3 và nhiều nhất có thể được là 35 đống, mỗi đống 3 viên.
Trường hợp 2: Bước đầu tiên là dồn 2 đống có 5 và 51 viên, ta được 2 đống có 49 và 56 viên, cả 2 đều là bội của 7. Khi thực hiện hiện cái bước đi luân phiên số sỏi trong mỗi đống luôn là bội của 7. Do đó, số đống với số sỏi nhỏ nhất có thể có là 15 đống, mỗi đống 7 viên.
Trường hợp 3: Bước đầu tiên dồn 2 đống có 49 và 51 viên, ta được 2 đống là 5 và 100 viên, số sỏi trong mỗi đống đều là bội của 5. Khi thực hiện một trong hai nước đi, số sỏi trong mỗi đống nhận được luôn là bội của 5. Do đó số đống với số sỏi nhỏ nhất là 21 đống, mỗi đống 5 viên.
Vậy ta có câu trả lời phủ định.
Bài 8: ( Tạp chí Kvant) Cho dãy số 1, 0, 1, 0,1, từ số hạng thứ 7, mỗi số bằng chữ số tận cũng của tổng 6 số hạng trước đó. Chứng minh rằng dãy số đó không chứa 6 số hạng liên tiếp 0,1,0,1,0,1.
Giải: Ta phát biểu lại bài toán như sau:
Một bộ 6 số ( x1,x2,x3,x4,x5,x6) được biến đổi thành bộ (x2,x3,x4 ,x5,x6,x7) với x7 là chữ số tận cùng của tổng x1+x2+x3+x4+x5+x6. Hỏi có thể nhận được bộ (0,1,0,1,0,1) từ bộ (1,0,1,0,1,0) bằng cách thực hiện các phép biến đổi trên qua hữu hạn các bước thực hiện không?
Ta sẽ chứng minh rằng điều đó không thể bằng cách thiết lập một bất biến không đổi qua các phép biến đổi trên. Thật vậy, gọi s(x1,x2,,x6) là chữ số tận cùng của tổng 2x1 + 4x2 + 6x3 + 8x4 + 10x5 + 12x6.
Vì s(x2,x3,,x7) – s(x1 ,x2,, x6) = 2x1 + 4x2 + 6x3 + 8x4 + 10x5 + 12(x1 + x2 ++x6)-2x1 – 4x2 -  -12x6 ≡ 10(x1+x2++x6) ≡ 0 ( mod 10)
Từ đó cho thấy s(x1,x2,,x6) bất biến.
vì s(1,0,1,0,1)=18 và s(0,1,0,1,0,1) = 24 nên không thể xuất hiện bộ (0,1,0,1,0,1) trong dãy số.
Bài 9: Trong một bảng ô vuông có 100×100 ô được điền dấu (+) và dấu (-). Một bước thực hiện bằng cách đổi toàn bộ những dấu ở một hàng hoặc một cột nào đó sang dấu ngược lại. Có khả năng sau hữu hạn bước như trên , bảng ô vuông nhận được đúng 1970 dấu (-) ?
Giải: Giả sử sau hữu hạn lần biến đổi trên bảng có đúng 2011 dấu (-) , ta gọi xi là số lần biến đổi của cột i , và yj là số lần biến đổi của hàng j. Như vậy ô( i, j) sẽ phải biến đổi xi + yj lần . Do đó để ô ( i,j ) là dấu (-) thì số lần biến đổi ở ô đó phải là số lẻ suy ra: xi +yj phải là số lẻ. Ta gọi p là số các số lẻ giữa các số xi, còn q là số số lẻ giữa các số yj. Khi đó, số dấu trừ có trên bảng là:
 p(1995-q) +q(1995-p) =1995q +1995p – 2pq
Theo giả sử thì ta có đẳng thức:
 1995q + 1995p -2pq = 2011 (*)
Ta nhận thấy p và q là 2 số lẻ nên VT là số chẵn, VP là số lẻ. Mâu Thuẫn.
Bài 10: Chứng minh rằng phương trình sau không có nghiệm nguyên khác 0:
 8x4 + 4y4 + 2z4 = u4.
Giải: Giả sử phương trình có nghiệm nguyên (x0;y0;z0;u0) ≠ (0;0;0;0)
Ta có: 8x04 + 4y04 + 2z04 = u04 , suy ra u04 ⋮ 2 => u0 ⋮ 2. Đặt u0 = 2u1. Ta được:
4x04 + 2y04 + z04 =8u14, suy ra z04 ⋮ 2 => z0 ⋮ 2. Đặt z0=2z1. Ta được:
2x04 + y04 + 8z14 =4u14, suy ra y04 ⋮ 2 => y0 ⋮ 2. Đặt y0=2y1. Ta được:
x04 + 8y14 + 4z14 =2u14, suy ra x04 ⋮ 2 => x0 ⋮ 2. Đặt x0=2x1. Ta được:
8x14 + 4y14 + 2z14 = u1. Vậy (x1;y1;z1;u1;) cũng là một nghiệm nguyên của phương trình.
Và nghiệm này có dạng (x0/2;y0/2;z0/2;u0/2), quy trình này có thể lặp mãi mãi đến bước k : (xk/2;yk/2;zk/2;uk/2). Các số xk/2;yk/2;zk/2;uk/2 nguyên với mọi k thuộc N. Điều này chỉ xảy ra ở các biến bằng 0. Vậy phương trình đã cho không có nghiệm nguyên khác không.
C. NGUYÊN LÍ CỰC HẠN:
Lý thuyết: Một tập hữu hạn ( khác rỗng ) các số thực bất kì đều có phần tử lớn nhất và phần tử nhỏ nhất. Nguyên lí này đơn giản giúp chúng ta có thể “ khởi đầu “ từ 1 trong 3 “ đầu mút”, nhỏ nhất hoặc lớn nhất, từ đó, chúng ta có được những thông tin bổ sung mà nếu xét ở một vị trí bất kì khác sẽ không có được.
Bài tập:
Bài 1: (Moscow MO 1984) Trên vòng tròn người ta xếp ít nhất 4 số thực không âm có tổng bằng 1. Chứng minh rằng tổng tất cả các tích các cặp số kề nhau không lớn hơn . 
Lời giải – Gợi ý:
Ta cần chứng minh rằng với mọi n ≥ 4 số thực không âm а1, ..., аn, có tổng bằng 1, ta có bất đẳng thức 
a1a2 + a2a3 + ... + an - 1an + ana1 ≤ 1/4. 
Với n chẵn n (n = 2m) điều này có thể chứng minh dễ dàng: đặt a1 + a3 + ... + a2m - 1 = a; khi đó, rõ ràng, 
a1a2 + a2a3 + ... + an - 1an + ana1 ≤ (a1 + a3 + ... + a2m−1) × (a2 + a4 + ... + a2m) = a(1 − a) ≤ 1/4. 
Giả sử n lẻ và ak – là số nhỏ nhất trong các số đã cho. (Để thuận tiện, ta giả sử 1 < k < n − 1 – điều này không làm mất tính tổng quát khi n ≥ 4.) Đặt bi = аi, với i = 1,..., k − 1, bk = ak + ak + 1 và bi = ai + 1 với i = k + 1,..., n − 1. Áp dụng bất đẳng thức của chúng ta cho các số b1,..., bn - 1, ta được: 
a1a2 + ... + ak - 2ak - 1 + (ak - 1 + ak + 2) bk + ak + 2ak + 3 + ... + an - 1an + ana1 ≤ 1/4. 
Cuối cùng, ta sử dụng bất đẳng thức 
ak - 1ak + akak + 1 + ak + 1ak + 2 ≤ ak - 1ak + ak - 1ak + 1 + ak + 1ak + 2 ≤ (ak - 1 + ak + 2) bk. 
để suy ra điều phải chứng minh.
Đánh giá trên đây là tốt nhất; dấu bằng xảy ra khi 2 trong n số bằng 1/2, còn các số còn lại bằng 0. 
Bài 2:(CRUX, Problem 1420) Nếu a, b, c là các số nguyên dương sao cho 
	0 < a2 + b2 – abc ≤ c
Chứng minh rằng a2 + b2 – abc là số chính phương.
Lời giải – Gợi ý:
Giả sử ngược lại rằng tồn tại các số nguyên dương a, b, c sao cho 0 < a2 + b2 – abc ≤ c và k = a2 + b2 – abc (1) không phải là số chính phương. 
Bây giờ ta cố định k và c và xét tập hợp tất cả các cặp số nguyên dương (a, b) thỏa mãn phương trình (1), tức là ta xét 
	S(c, k) = {(a, b) Î (N*)2: a2 + b2 – abc = k}
Giả sử (a, b) là cặp số thuộc S(c, k) có a + b nhỏ nhất. Không mất tính tổng quát có thể giả sử a ≥ b. Ta xét phương trình 
	x2 – bcx + b2 – k = 0	
Ta biết rằng x = a là một nghiệm của phương trình. Gọi a1 là nghiệm còn lại của phương trình này thì a1 = bc – a = (b2 – k)/a. 
Ta có thể chứng minh được rằng a1 nguyên dương. Suy ra (a1, b) cũng thuộc S(c, k).
Tiếp theo ta có a1 = (b2-k)/a < a2/a = a, suy ra a1 + b < a + b. Điều này mâu thuẫn với cách chọn (a, b).
Bài 3:   a. Trên một mạng lưới ô vuông vô hạn trên một mặt phẳng, đặt vào mỗi ô vuông một số tự nhiên sao cho số trong mỗi ô bằng trung bình cộng của bốn số trong các ô vuông có cạnh kề với ô đó. Chứng minh tất cả các số bằng nhau.
b. Nếu số trong mỗi ô bằng trung bình cộng của bốn số trong các ô vuông bốn góc. Ta có thể đặt được tối đa bao nhiêu giá trị của các số?
Lời giải – Gợi ý:
a. Tồn tại ô vuông với số được điền bé nhất, 4 ô kề cạnh cũng được đặt cùng số bé nhất đó. Với ô vuông khác bất kì ta luôn tìm được một dãy các ô vuông kề cạnh bắt đầu từ ô vuông đó tới ô vuông với số bé nhất, do vậy cũng được đặt số bé nhất. Vậy tất cả các số đều bằng nhau.
b. Tô màu đen trắng theo kiểu bàn cờ, ta chứng minh được tất cả các số trong các ô cùng màu phải bằng nhau. Tối đa đặt được 2 giá trị của các số vào mạng lưới ô vuông.
Bài 4: Trong một buổi tiệc với một số lượng người tham gia nhất định, xét quan hệ “bạn bè” theo nghĩa: “Nếu A là bạn của B thì B cũng là bạn của A”. Chứng minh rằng người trong buổi tiệc luôn có thể chia làm hai nhóm để đưa vào trong hai phòng khác nhau sao cho: Với mỗi người trong một phòng bất kì, ít nhất một nửa số bạn của người đó ở phòng còn lại.
Lời giải – Gợi ý:
Với một cách chia bất kì số người thành 2 nhóm, gọi  là số lượng tất cả các cặp  sao cho  và  ở khác phòng và  là bạn của nhau. Xét cách chia với  lớn nhất có thể (vì số cách chia là hữu hạn nên  nhận hữu hạn giá trị), ta chứng minh cách chia này thỏa mãn yêu cầu.
Thật vậy, với người  bất kì, gọi  là số bạn của anh ta trong cùng phòng và  là số bạn của anh ta khác phòng. Nếu ta chuyển  sang phòng còn lại thì ta sẽ cộng  vào . Do giả thiết chọn  là lớn nhất nên ta phải có  hay . Vậy với cách chia mà  lớn nhất có thể thì thỏa mãn yêu cầu.
Bài 5:  Trong một đường tròn tâm  đã cho, xét tập hợp  gồm một số hữu hạn các dây cung thỏa mãn tính chất sau: mỗi dây cung thuộc tập  đi qua trung điểm của một dây cung khác cũng thuộc . Chứng minh rằng tất cả các dây cung này đều là đường kính.
Lời giải – Gợi ý:
Xét dây cung với độ dài ngắn nhất .
Giả sử  không là một đường kính, theo giả thiết  đi qua trung điểm của một dây cung  khác. Gọi  lần lượt là trung điểm của , ta dễ dàng chứng minh được  và do đó , trái với tính ngắn nhất của .
Vậy  phải là một đường kính và do vậy tất cả các dây cung trong tập  đều là các đường kính.
Bài 6: (Định lý Sylvester) Cho tập hợp  gồm hữu hạn các điểm trên mặt phẳng thỏa mãn tính chất sau: Một đường thẳng đi qua 2 điểm thuộc  đều đi qua ít nhất một điểm thứ ba thuộc . Khi đó tất cả các điểm của  nằm trên một đường thẳng.
Lời giải – Gợi ý:
Giả sử phản chứng là tồn tại một tập hợp  gồm hữu hạn điểm không thẳng hàng nhưng mọi đường thẳng qua hai điểm trong  đều chứa ít nhất ba điểm. Một đường thẳng gọi là đường nối nếu nó đi qua ít nhất hai điểm trong . Giả sử  là cặp điểm và đường nối có khoảng cách dương nhỏ nhất trong mọi cặp điểm-đường nối.
Theo giả thiết,  đi qua ít nhất ba điểm trong , nên nếu hạ đường cao từ  xuống  thì tồn tại ít nhất hai điểm nằm cùng một phía của đường cao (một điểm có thể nằm ở ngay chân đường cao). Trong hai điểm này, gọi điểm ở gần chân đường cao hơn là , và điểm kia là . Xét đường thẳng  nối  và . Khoảng cách từ tới  nhỏ hơn khoảng cách từ  tới , mâu thuẫn với giả thiết về  và . Một cách để thấy điều này là tam giác vuông với cạnh huyền  đồng dạng và nằm bên trong tam giác vuông với cạnh huyền .
Do đó, không thể tồn tại khoảng cách dương nhỏ nhất giữa các cặp điểm-đường nối. Nói cách khác, mọi điểm đều nằm trên đúng một đường thẳng nếu mọi đường nối đều chứa ít nhất ba điểm.
Bài 7: Cho  và  lần lượt là tập hữu hạn (lớn hơn 2 phần tử) gồm các điểm đen và trắng trên mặt phẳng, thỏa mãn tính chất sau: Mỗi đoạn thẳng nối hai điểm cùng màu luôn qua một điểm khác màu. Chứng minh rằng cả hai tập điểm đều thuộc một đường thẳng.
Lời giải – Gợi ý:
Giả sử ngược lại, hai tập điểm không cùng nằm trên một đường thẳng. Khi đó, tồn tại một hoặc hơn các tam giác với đỉnh là các điểm thuộc .
Xét tam giác có diện tích nhỏ nhất. Rõ ràng, ít nhất hai đỉnh của tam giác cùng màu theo nguyên lý Dirichlet. Do vậy, phải có một điểm với màu khác giữa chúng. Tuy nhiên điểm này cùng với hai điểm khác (là đỉnh của tam giác bên trên) lập thành một tam giác có diện tích nhỏ hơn diện tích của tam giác đã xét. Ta thu được mâu thuẫn.
Vậy tất cả các điểm thuộc hai tập đều nằm trên một đường thẳng.
Bài 8:  Cho  điểm  nằm trên một mặt phẳng thỏa mãn tính chất sau: Nếu ta chọn ra từ đó ba điểm bất kì  thì diện tích của tam giác luôn bé hơn 1. Chứng minh rằng toàn bộ  điểm đó nằm bên trong hoặc trên biên của một tam giác với diện tích bé hơn 4.
Lời giải – Gợi ý:
Gọi  là ta giác có diện tích lớn nhất trong số các tam giác với ba đỉnh lấy từ điểm đã cho. Để cho gọn ta kí hiệu diện tích tam giác  bởi . Ta có, . Xét tam giác  là tam giác sao cho  lần lượt là trung điểm của các cạnh .
Thế thì . Ta chứng minh  điểm đã cho nằm bên trong hoặc trên biên của tam giác . Thật vậy, giả sử ngược lại, tồn tại điểm nằm ngoài tam giác . Khi đó, ta có thể nối  với hai đỉnh của  để tạo thành một tam giác với diện tích lớn hơn diện tích tam giác . Ta thu được mâu thuẫn. Từ đó ta có đpcm.
Bài 9: Trong mỗi ô của bảng 2 x n ta viết các số thực dương sao cho tổng các số của mỗi cột bằng 1. Chứng minh rằng ta có thể xoá đi ở mỗi cột một số sao cho ở mỗi hàng, tổng của các số còn lại không vượt quá n+14
(Bài này ở trong tài liệu về Nguyên lí cực hạn của thầy Trần Nam Dũng-ĐH KHTN TPHCM).
Lời giải – Gợi ý:
Ta giải bài toán bằng quy nạp theo cách nếu bài toán đúng cho n thì nó cũng đúng cho n+2
Dễ thấy bài toán đúng cho n=2 và n=3.
Giả sử bài toán đúng cho n, ta chứng minh bài toán đúng cho n+2. Thật vậy, xét n cột đầu. Khi đó tồn tại cách xóa đi n ô thỏa tổng của mỗi hàng không vượt quá n+14. Còn hai ô sau cùng ta xóa đi số lớn nhất ở mỗi hàng ( như trường hợp n=2) thì mỗi số còn lại ở mỗi hàng đều không vượt quá 12. Cộng lại thì bài toán đúng cho n+2. Vậy ta có đpcm.
Bài 10:  Cho trước một bảng