Bài toán 3.13 (VMO 1992). Một bảng hình chữ nhật kẻ ô vuông có 1991 hàng và 1992 cột (nghĩa là bảng gồm 1991×1992 ô vuông). Kí kiệu ô vuông nằm ở giao của hàng thứ m (kể từ trên xuống dưới) và cột thứ n (kể từ trái
qua phải) là (m;n). Tô màu các ô vuông của bảng theo cách sau: lần thứ nhất tô 3 ô (r;s), (r + 1;s+ 1), (r + 2;s + 2), với r, s là hai số tự nhiên cho trước thỏa mãn 1≤ r ≤ 1989 và 1 ≤s ≤ 1990. Từ lần thứ 2 mỗi lần tô đúng 3 ô chưa có màu nằm cạnh nhau hoặc trong cùng một hàng hoặc trong cùng một cột. Hỏi bằng cách đó có thể tô được tất cả các ô vuông của bảng đã cho hay không.
Lời giải.
Ta giả sử có thể tô hết các ô trong bảng. Khi đó tất cả có 664.1991 lần tô. Điền số các ô như sau: Tại ô (m;n) ta điền số m.n. Gọi S là tổng các số ở các ô đã điền.
Ta có S = (1 + 2 +· · ·+ 1991) (1 + 2 +· · ·+ 1992)≡ 0 (mod 3).
Mặt khác, gọi Si tổng các số ở 3 ô điền lần thứ i với 1 ≤i ≤664.1991. Ta có:
S1 = rs+ (r + 1) (s+ 1) + (r + 2) (s+ 2) ≡2 (mod 3) Si ≡0 (mod 3), 2 ≤ i ≤ 664.1991
(vì Si là tổng 3 số có dạng ab,(a+ 1)b,(a+ 2)b).
Suy ra S ≡2 (mod3).
Điều mâu thuẫn này chứng tỏ điều giả sử sai. Vậy không thể tô tất cả các ô trong bảng đã cho.
Bài toán 3.14 (VMO 2001). Cho một bảng ô vuông kích thước 2000×2001 (bảng gồm 2000 hàng và 2001 cột). Hãy tìm số nguyên dương k lớn nhất sao cho ta có thể tô màu k ô vuông con của bảng thỏa mãn điều kiện: hai ô vuông con nào được tô màu cũng không có đỉnh chung.
Lời giải.
Ta qui ước: thứ tự của các hàng được tính từ trên xuống dưới và thứ tự các cột được tính từ trái qua phải.
Kí hiệu (i;j) là ô vuông nằm ở hàng i, cột j; k(T) là số ô được tô màu ở cách tô màu T .
Xét một cách tô màu T thỏa mãn điều kiện bài toán.
Ta thấy, nếu ô (i;j), (1 ≤ i ≤ 1999,1 ≤ j ≤ 2001) được tô màu thì các ô (i+ 1;j) và các ô kề với nó trong cùng một hàng không được tô màu. Điều này cho phép ta thực hiện phép biến đổi sau đối với T:
Xóa màu ở tất cả các ô (i;j) mà i lẻ và tô màu các ô (i+ 1;j). Rõ ràng, sau khi thực hiện phép biến đổi nói trên vớiT , ta thu được một cách tô màu T’ thỏa mãn đề bài và:
+ k(T0) = k(T)
+ Tất cả các ô ở hàng thứ 2i−1 với i = 1,2,3, . . . ,103 đều không được tô màu.
Từ điều kiện của đề suy ra trong một hàng có không quá 1001 ô được tô màu. Do đó k(T) ≤ 1001.103.
Ta xét cách tô màu sau:
Tô tất cả các ô (2i; 2j−1) với i = 1,2, . . . ,103, j = 1,2, . . . ,1001. Ta thấy cách tô màu này thỏa mãn điều kiện bài toán và số ô được tô màu là 1001.103.
Vậy số nguyên k lớn nhất cần tìm là kmax = 1001.103.
Bài toán 3.15 (VMO 2006). Cho m, n là các số nguyên lớn hơn 3 và bảng ô vuông kích thước m×n(bảng gồm m hàng và n cột). Cho phép đặt bi vào các ô vuông con của bảng theo cách sau: mỗi lần đặt 4 viên bi vào 4 ô vuông con (mỗi ô 1 viên) mà 4 ô vuông đó tạo thành một trong các hình dưới đây:
Hỏi bằng cách thực hiện một số lần hữu hạn phép đặt bi nói trên, ta có thể đặt bi vào tất cả các ô vuông con của bảng sao cho số bi trong mỗi ô vuông con đều bằng nhau hay không, nếu:
1. m = 2004 và n = 2006.
2. m = 2005 và n = 2006. Lời giải.
1. Nhận thấy: Bằng cách thực hiện hai lần phép đặt bi, ta có thể đặt vào mỗi ô vuông con của bảng 4× 2 một viên bi. Có thể phân chia bảng 2004×2006 thành các bảng 4×2. Từ đó bằng cách thực hiện một số hữu hạn phép đặt bi của đề bài, ta có thể đặt bi vào tất cả các ô vuông con của bảng 2004×2006 sao cho số bi trong mỗi ô đều bằng nhau (bằng 1).
2. Giả sử sau một số hữu hạn lần phép đặt bi của đề bài, ta đặt được vào mỗi ô vuông con của bảng 2005×2006 k viên bi. Tô màu tất cả các ô vuông con thuộc hàng lẻ của bảng bởi màu đen và coi các ô không được tô màu có màu trắng. Khi đó, số các ô màu đen bằng 2006.1003 và số ô màu trắng bằng 2006.1002.
Ta thấy, ở mỗi lần đặt bi, đều đặt đúng hai viên bi vào các ô màu đen và đúng hai viên bi vào các ô màu trắng. Do đó sau mỗi lần đặt bi, số bi trong các ô màu đen và số bi trong các ô màu trắng luôn bằng nhau. Suy ra, khi ở mỗi ô có k viên bi, ta phải có 2006.1003k = 2006.1002k hay k = 0. Điều vô lí này chứng tỏ giả sử ban đầu là sai. Vì thế, không thể đặt bi vào các ô vuông con của bảng sao cho số bi trong mỗi ô vuông con đều bằng nhau.
Bài toán 3.16 (Vietnam TST 1993). Gọi hình chữ nhật 2×3 (hoặc 3×2) bị cắt bỏ một ô vuông 1× 1 ở góc được gọi là hình chữ nhật khuyết đơn.
Hình chữ nhật 2× 3 (hoặc 3× 2) bị cắt bỏ hai hình vuông ở hai góc đối diện được gọi là hình chữ nhật khuyết kép. Người ta ghép một số hình vuông 2×2, một số hình chữ nhật khuyết đơn và một số hình chữ nhật khuyết kép sao cho không có hai hình nào chờm lên nhau để tạo thành một hình chữ nhật kích thước 1993×2000. Gọi s là tổng số hình vuông 2×2 và hình chữ nhật khuyết kép trong mỗi cách ghép nói trên. Tìm giá trị lớn nhất của s.
Lời giải.
Gọi y là số hình chữ nhật khuyết đơn. Ta có đẳng thức về diện tích
4s+ 5y = 2000.1993 (13)
Điền số 0 vào các ô (2k,2t) với 1 ≤ k ≤ 996,1 ≤ t ≤ 1000 , ta thấy có 996.1000 số 0 được điền. Ta thấy:
+ Hình vuông 2×2 và hình chữ nhật khuyết kép chứa đúng một số 0 + Hình chữ nhật khuyết đơn chứa x số 0 (với x = 1 hoặc x = 2).
Suy ra
996.1000 = 1.s+ x.y ≥ s+y (14) Từ (13) và (14) suy ra 2000.1993 = 5(s+y)−s ≤ 5.996.1000−s. Do đó s≤ 994000.
Ta xét các hình ghép thỏa mãn với s = 994000.
Kết luận
Luận văn đã trình bày và đạt được một số kết quả sau:
- Trình bày cách giải các bài toán đếm trong hình học tổ hợp thông qua việc phân loại các đối tượng đếm trong hình học.
- Trình bày các nguyên lí cơ bản như nguyên lí bất biến, nguyên lí Dirichlet, nguyên lí cực hạn và các phương pháp vận dụng các nguyên lí đó để giải các bài toán hình học tổ hợp.
- Trình bày được một số dạng toán liên quan, đặc biệt là đã tiếp cận được một số bài toán khó về hình học tổ hợp trong các kì thi chọn học sinh giỏi quốc gia và quốc tế.