Đề bài:
Có 10 người bạn đi nghỉ mát Vũng Tàu. Họ thuê 10 phòng sát nhau từ phòng 201 đến 210 thành một dãy dọc như hình vẽ.
| 201 | 202 | 203 | 204 | 205 | 206 | 207 | 208 | 209 | 210 |
Nhóm trưởng đề ra một quy định. Sau mỗi đêm, mọi người sẽ đổi phòng cho nhau, sao cho 2 người bất kỳ ở cạnh nhau không quá một đêm. Hỏi nhóm bạn này có thể ở lại Vũng Tàu tối đa bao nhiêu ngày nếu tuân thủ nghiêm ngặt quy định trên? Hãy nêu rõ cách xếp phòng mỗi ngày để đạt được điều đó.
Đáp án:
Ta phát cho mỗi người 9 lá phiếu. Sau mỗi đêm, ta sẽ thu lại từ mỗi người 1 hoặc 2 phiếu tùy thuộc đêm trước người đó ngủ cạnh 1 hay 2 người. Như thế ta phát tất cả 90 phiếu và sau mỗi đêm ta thu lại 18 phiếu (8 phòng bên trong thu 2 phiếu, 2 phòng đầu hè thu 1 phiếu).
Vậy nhóm bạn ở được tối đa 90/18 = 5 ngày.
Việc sắp xếp thế nào để đạt được điều này hóa ra không đơn giản. Từ lý luận ở phần trên, ta rút ra một kết luận quan trọng: Để có thể xếp được đủ 5 ngày thì mỗi người phải dùng đủ 9 phiếu, tức là mỗi người chỉ được ở hai phòng đầu hè một lần. Đây là nguyên tắc quan trọng để ta xây dựng ví dụ. Dưới đây là một ví dụ:
1-2-3-4-5-6-7-8-9-10
2-4-6-8-10-1-3-5-7-9
3-6-9-1-4-7-10-2-5-8
4-8-1-5-9-2-6-10-3-7
5-10-4-9-3-8-2-7-1-6
Để kiểm tra, chú ý hiệu các số cạnh nhau ở hàng 1 bằng 1, ở hàng 2 bằng 2 hoặc 9, ở hàng 3 bằng 3 hoặc 8, ở hàng 4 bằng 4 hoặc 7, ở hàng 5 bằng 5 hoặc 6 nên tất cả các đôi một khác nhau.
Trần Nam Dũng
ĐH Khoa học Tự nhiên, ĐH Quốc gia TP HCM