Bài toán: Lát gạch domino trên bàn cờ bị cắt góc
Đây là bài toán chứng minh điều không thể — một thách thức đặc biệt. Kỹ thuật then chốt là tìm bất biến (invariant) bằng cách tô màu bàn cờ — một yếu tố phụ trợ sáng tạo không hề có trong đề bài. Pólya gọi đây là mẫu mực của tư duy "nhìn thấy cái ẩn".
Một bàn cờ $8 \times 8$ bị cắt bỏ hai ô góc đối diện (hai ô cùng màu). Hỏi: có thể lát kín phần còn lại bằng $31$ quân domino $1 \times 2$ không?
Mỗi quân domino chiếm đúng 2 ô liền kề (ngang hoặc dọc). Phần còn lại của bàn cờ có $64 - 2 = 62$ ô.
Ẩn số là gì? Điều kiện là gì? Bài này yêu cầu tìm hay chứng minh?
Mệnh đề cần xét: "Có thể lát kín 62 ô còn lại bằng 31 quân domino $1 \times 2$."
Điều kiện: Mỗi domino phủ đúng 2 ô liền kề; tất cả 62 ô phải được phủ, không chồng lấp.
Điều kiện cần (dễ thấy): Số ô $62 = 2 \times 31$ — chia hết cho 2. OK, điều kiện cần thỏa.
→ Câu hỏi: điều kiện cần này có đủ không?
Hãy thử đặc biệt hóa. Với bàn cờ nhỏ hơn ($4 \times 4$), kết quả thế nào?
— Thử mãi mà không lát được (2 ô trắng thừa ra!).
— Phỏng đoán: KHÔNG thể lát được.
→ Bây giờ ta cần chứng minh điều này, không phải chỉ thử.
Rất nhiều người ngừng lại sau khi "thử nhiều cách mà không lát được" rồi kết luận là không thể. Đây không phải chứng minh! Pólya nhấn mạnh: thử nhiều mà thất bại chỉ là bằng chứng heuristic, không phải chứng minh toán học. Ta cần một lập luận chặt chẽ.
Bạn có biết bài toán liên quan không? Có tính chất nào bất biến qua mọi cách lát không?
Ý tưởng then chốt: Mỗi domino luôn phủ đúng 1 ô trắng và 1 ô đen (vì ô trắng và đen xen kẽ như trên bàn cờ thực). Đây là bất biến không đổi bất kể ta đặt domino thế nào!
Ý tưởng cốt lõi — Yếu tố phụ trợ: Tô màu
Ta không cần thêm đường, điểm hay biến. Thay vào đó, nhìn lại bàn cờ bằng mắt mới: bàn cờ đã có màu đen-trắng xen kẽ. Mỗi domino $1 \times 2$ đặt ngang hoặc đặt dọc đều bắt buộc phủ 1 ô trắng + 1 ô đen.
→ Sau khi lát bất kỳ số domino, số ô trắng được phủ luôn bằng số ô đen được phủ.
→ Nếu có thể lát kín, thì số ô trắng còn lại phải bằng số ô đen còn lại: $\Delta = 0$.
→ Đây là điều kiện cần để có thể lát. Nếu $\Delta \neq 0$, chắc chắn không lát được!
Đếm số ô trắng và đen trên bàn cờ bị cắt.
Hai góc bị cắt: góc trên-trái $(1,1)$ và góc dưới-phải $(8,8)$ — theo quy ước tô màu chuẩn, cả hai ô này cùng màu (giả sử đều là ô trắng).
Sau khi cắt: 30 ô trắng, 32 ô đen.
Chênh lệch: $\Delta = |30 - 32| = 2 \neq 0$.
→ Không thể lát kín! ✓
• Ô $(1,1)$: $1+1=2$ (chẵn) → màu trắng.
• Ô $(8,8)$: $8+8=16$ (chẵn) → màu trắng.
→ Sau khi cắt: còn $30$ ô trắng và $32$ ô đen.
Tương tự với domino đặt dọc: ô $(i,j)$ và $(i+1,j)$, tổng chỉ số lệch nhau 1 → một trắng, một đen.
Bất biến: mỗi domino phủ đúng 1 ô trắng và 1 ô đen.
→ Giả thiết sai → Không thể lát được. $\square$
Bạn có thể kiểm tra kết quả không? Có thể kiểm tra bằng trường hợp đặc biệt?
Kiểm tra ngược: Nếu cắt 2 góc khác màu (ví dụ $(1,1)$ và $(1,8)$): $\Delta = 0$. Và thực tế, bàn cờ $8 \times 8$ cắt 2 ô trắng-đen khác nhau lát được 31 domino. Điều kiện $\Delta = 0$ là điều kiện cần (và trong trường hợp này cũng đủ — có thể chứng minh thêm).
Bạn có thể tổng quát hóa không?
Tổng quát hóa 2 (Đẹp hơn!): Bàn cờ $8 \times 8$ cắt bỏ tùy ý $k$ ô trắng và $k$ ô đen (cùng số). Khi đó điều kiện cần thỏa, nhưng có lát được không? — Câu trả lời là có nếu ta có thể phân bàn cờ thành $32 - k$ "thịt" và các ô bị cắt không ngắt các "thịt". Bài toán này dẫn vào lý thuyết ghép đôi (matching theory) trong lý thuyết đồ thị.
Bạn có thể dùng phương pháp này cho bài toán khác không?
• Chứng minh không thể đi tua du lịch nhất định trên bản đồ.
• Bài toán mã cờ vua (knight's tour).
• Lý thuyết đồ thị 2 phía (bipartite graph).
• Bài toán lịch (scheduling), tô màu bản đồ.
Bài học heuristic sâu hơn
Pólya mô tả thao tác trí tuệ quan trọng: nhìn cùng một đối tượng từ nhiều góc. Bàn cờ được "nhìn" theo hai cách:
- Cách 1 (vật lý): 62 ô riêng biệt cần phủ bởi domino.
- Cách 2 (tô màu): 30 ô trắng + 32 ô đen. Ngay lập tức thấy mâu thuẫn.
Cách nhìn thứ hai không thêm thông tin mới — bàn cờ vẫn vậy — nhưng làm lộ ra cấu trúc ẩn. Đây là bản chất của yếu tố phụ trợ: không thêm thứ mới mà nhìn thứ cũ bằng mắt mới.
Kỹ thuật tô màu
Gán màu/số cho các phần tử để lộ ra bất biến. Cực kỳ hiệu quả trong bài toán tổ hợp "chứng minh không thể".
Tìm bất biến
Một đại lượng không đổi qua mọi phép biến đổi hợp lệ. Nếu cần đạt trạng thái có đại lượng này khác với trạng thái đầu → không thể!
Phản chứng
Giả sử điều cần chứng minh là sai, rồi dẫn đến mâu thuẫn. Mạnh khi tấn công trực tiếp gặp khó.
Đặc biệt hóa để thử
Trước khi chứng minh, thử trên bài nhỏ hơn (4×4 thay vì 8×8) để xây dựng trực giác và phỏng đoán.
Mở rộng — Lát gạch $L$-tromino
Bàn cờ $2^n \times 2^n$ bị cắt bỏ một ô bất kỳ. Chứng minh: có thể lát kín phần còn lại bằng các L-tromino (quân cờ hình chữ L phủ 3 ô).
Đây là bài toán nổi tiếng cần kỹ thuật quy nạp kết hợp chia đôi (divide & conquer). Phương pháp:
1. Chia bàn cờ $2^n \times 2^n$ thành 4 bàn cờ $2^{n-1} \times 2^{n-1}$.
2. Đặt 1 L-tromino ở chính giữa phủ 1 ô trong mỗi "phần tư" không chứa ô bị cắt.
3. Quy nạp xuống $n-1$.
Đây là ví dụ đẹp về kết hợp quy nạp với đặc biệt hóa (n=1 là cơ sở, bước chuyển dùng cấu trúc chia đôi).