Bài toán lát hình kinh điển

Lát hình chữ nhật bằng domino

Cho hình chữ nhật kích thước 2n×2n, chia thành các ô vuông đơn vị. Chứng minh rằng có thể lát kín hình này bằng n^2 quân domino 1×2 sao cho: Không có hai domino nào cắt nhau và Mỗi domino phủ đúng hai ô, và không chồng lấn

Đây là một bài toán tổ hợp hình học kinh điển, rất đẹp và có thể giải bằng tư duy trực quan hoặc bằng lý thuyết đồ thị. Dưới đây là phần giải chi tiết, kèm cả chứng minh hình học và logic tổ hợp.

🧩 Đề bài:

Cho hình chữ nhật kích thước , chia thành các ô vuông đơn vị.

Chứng minh rằng ta có thể lát kín hình này bằng $n^2$ quân domino sao cho:

Mỗi domino phủ đúng 2 ô liền kề
Không có domino nào cắt nhau hoặc chồng lấn
Toàn bộ hình được lát kín hoàn toàn

✅ Ý tưởng chính:

Ta sẽ tô caro và lát theo quy luật xen kẽ, rồi chứng minh:

Số lượng domino đủ dùng
Cách lát hoàn toàn không chồng chéo
Từng bước đảm bảo không giao nhau

🔷 Bước 1: Tổng số ô và số quân domino cần dùng

Hình chữ nhật có kích thước $2n×2n=4n^2$ ô vuông đơn vị
Mỗi domino phủ đúng 2 ô
"Chứng minh rằng có thể lát kín hình bằng 2n² domino

✅ Giải bằng phương pháp Caro + Lát theo hàng chẵn

🌈 Cách 1: Lát từng hàng ngang

Chia hình chữ nhật thành hàng, mỗi hàng có ô.
Với mỗi hàng, lát từ trái qua phải bằng các domino ngang

📌 Một hàng dùng đúng domino

📌 Có hàng → dùng $2n×n=2n^2$ domino

⟹ Lát kín và không chồng lấn, không cắt nhau

✅ Thỏa mãn yêu cầu đề bài

🌈 Cách 2: Lát bằng domino đứng (2 × 1)

Lát theo từng cột dọc, mỗi cột gồm ô
Lát từ trên xuống dưới, mỗi domino chiếm 2 ô
Có cột → mỗi cột cần $n$ domino

→ Tổng: $2n×n=2n^2$ domino

✅ Không cắt, không chồng lấn, phủ kín toàn bộ

🧠 Cách chứng minh bằng tô màu đen trắng (caro)

Tô hình như bàn cờ caro: các ô xen kẽ đen trắng
Mỗi domino luôn che 1 ô trắng + 1 ô đen
Tổng số ô trắng = tổng số ô đen = $2n^2$
→ Ta cần 2n^2 domino, mỗi domino đi qua 1 trắng + 1 đen → đúng

✅ Điều này chứng minh điều kiện cần và đủ cho việc lát bằng domino.