MỘT SỐ BÀI TOÁN TỔ HỢP LIÊN QUAN ĐẾN PHỦ HÌNH CHỮ NHẬT

Một hình chữ nhật m × n (có m dòng và n cột) được phân chia thành m.n ô vuông đơn vị.
Ta sẽ nghiên cứu bài toán phủ hình chữ nhật này bằng các hình được ghép từ các ô vuông đơn vị.
Với các bài toán dạng này, thường ta đánh số hoặc tô màu các ô vuông đơn vị của hình chữ nhật,
có hai cách tô màu cơ bản:
Cách 1: Tô màu đen và trắng xem kẽ trên mỗi hàng và mỗi cột
Nếu có một trong hai số m, n chẵn thì số ô đen và trắng
là bằng nhau
Nếu cả hai số đều lẻ thì màu nào được tô vào ô đầu tiên
sẽ nhiều hơn màu kia 1 đơn vị.
Cách 2: Tô màu giống nhau trên 1 hàng (hoặc cột) và xen
kẽ trên 1 cột (hoặc hàng)
Nếu có một trong hai số m, n chẵn thì số ô đen và
trắng là bằng nhau
Nếu cả hai số đều lẻ thì màu nào được tô vào ô đầu
tiên sẽ nhiều hơn màu kia m ô (nếu tô màu giống nhau theo mỗi cột).
Các dạng hình sử dụng để phủ hình chữ nhật:
Dạng 1: Monomino là một ô vuông đơn vị 1× 1 .
Dạng này không xét riêng, bởi đơn giản. Ta sẽ tìm hiểu chúng khi kết hợp với các loại khác.
Dạng 2: Domino là hình được tạo từ 2 ô vuông đơn vị, ta sẽ gặp khi xét chung cho các loại thẳng.

Dạng 3: Trimino được tạo từ 3 ô vuông đơn vị, có 2 dạng:
Trimino thẳng (sẽ được xét trong phần monomino thẳng)
L - Trimino

-----Trang 1-----


Ta xây dựng điều kiện cần và đủ để hình chữ nhật m × n bởi các L – trimino bằng các bài toán:
1. Một hình chữ nhật 4 × 5 không phủ được bởi các L – trinimo bởi 20 không chia hết cho 3.

6. Chứng minh rằng hình chữ nhật 5 × 6 có thể được phủ bởi các L – trimino.
Nhận thấy có thể chia thành các hình chữ nhật 2 × 3

7. Chứng minh rằng hình chữ nhật 5 × 9 có thể được phủ bởi các L – trimino.
Chỉ rõ một cách phủ như sau:

8. Từ bài 7 hãy chứng minh rằng hình chữ nhật 9 × 9 có thể được phủ bởi các L – trimino.
Gộp thêm các hình chữ nhật 2 × 3 vào hình chữ nhật 5 × 9 để được hình chữ nhật 9 × 9 .
3 phủ được bởi các L – trimino thì hình chữ
9. Từ đây nhận thấy: Nếu hình chữ nhật a × b với bM
nhật ( a + 2 ) × b cũng phủ được. (Dễ dàng chứng minh như ý 8)
3, b > 5 có thể được phủ bởi các L – trimino.
10. Chứng minh rằng hình chữ nhật 5 × b với bM
Hình chữ nhật như trên được ghép bởi các hình 5 × 6 và 5 × 9 .
3 có thể được phủ bởi các
11. Chứng minh rằng hình chữ nhật a × b với a ≥ 4, b ≥ 5, bM
L – trimino.
Nếu aM2 thì phân chia thành các hình chữ nhật 2 × 3 .
Nếu a M2 thì chia thành hình chữ nhật 5 × b và ( a − 5 ) × b .
12. Ta có định lý 2: Hình chữ nhật a × b với a ≥ 4, b ≥ 4 có thể được phủ bởi các L – trimino khi
3 (nghĩa là cần 1 trong hai số chia hết cho 3).
và chỉ khi abM
3 thì hình chữ nhật a × b có thể được phủ bởi các L – trimino đã được chứng minh
Nếu abM
bởi các bài toán trên, cụ thể như sau:
3 và a chẵn thì có thể phân chia thành các hình chữ nhật 2 × 3 .
Giả sử có bM
3 và a lẻ thì do 5 × b phủ được nên
Giả sử có bM


J – tetramino

T – tetramino

Tetramino thẳng

1. Với dạng O – tetramino
Hình chữ nhật m × n phủ được bởi các O – tetramino khi và chỉ khi m, n đều chẵn.
2. Với S – tetramino và Z – tetramino
Một hình chữ nhật không thể được phủ nếu chỉ dùng S – tetramino và Z – tetramino.
muốn phủ được thì phải phủ ô vuông đầu tiên,
với mỗi loại cho ta một cách phủ ô đầu.
khi đó tiếp tục sẽ chỉ có một cách để phủ ô
tiếp theo trên hàng 1, cứ như vậy sẽ không phủ
được ô cuối cùng trên hàng 1.
3. Với J – tetramino và L – tetramino.
Hình chữ nhật m × n được phủ chỉ bởi các J – tetramino hoặc L – tetramino nếu và chỉ nếu
m.nM
8.
-----Trang 4-----


Một số bài toán gợi ý để giải quyết ý trên (Xét với L – tetramino, với J – tetramino hoàn
toàn tương tự)
a. Tổng số lượng L – tetramino là số chẵn.
Chứng minh
Giả sử hình chữ nhật m × n được tô bởi k , suy ra
m.n = 4k , cần chứng minh k chẵn.
Nhận thấy trong hai số m, n có ít nhất 1 số chẵn,
giả sử là n.

bởi k – omino thẳng.
1.2 . Chứng minh rằng nếu m hoặc n cùng không chia hết cho k thì hình chữ nhật m × n
không thể được phủ bởi k – omino thẳng.
Chứng minh: Thực hiện phép chia có dư: m = k .q1 + r1; n = k .q2 + r2 với 0 < r1; r2 < k
Đánh số hình chữ nhật theo quy tắc sau: Trên mỗi cột các số được đánh giống nhau, trên
mỗi hàng các số được xếp liên tiếp theo thứ tự 1, 2, …, k, 1, 2, … đến hết, trên mỗi hàng sẽ
kết thúc tại r2
1

2

3

…

r2

1

2

3

…

r2

M

M

Do cách đánh số suy ra số r2 được đánh nhiều hơn số r2 + 1 đến m đơn vị, suy ra
S r2 +1 − S r2 = m ⇒ mMk , điều này vô lí.
2. Một hình chữ nhật có thể được phủ bởi 1 monomino và một số k – omino thẳng khi nào?

Nếu được thì đặt monomino ở vị trí nào?
Bài toán: Nếu hình chữ nhật m × n được phủ bởi 1 monomino và một số k – omino thẳng
khi và chỉ khi ( mn − 1) Mk .
Nếu hình chữ nhật m × n được phủ bởi 1 monomino và một số k – omino thẳng thì hiển
nhiên ta có ( mn − 1) Mk .
Ta chứng minh điều ngược lại
Xét trường hợp với k = 2 , suy ra m, n đều lẻ.
Ta xếp monomino ở một ô thuộc cột hoặc dòng có thứ tự lẻ (tính từ dòng đầu hoặc cột đầu)
-----Trang 6-----


Với k > 2 .
Vị trí của ô vuông đơn vị là giao của dòng x và cột y được kí hiệu ( x, y ) .
m ≡ n ≡ 1( mod k )
m ≡ n ≡ −1( mod k )
Bài toán được giải quyết khi 
hoặc 
 x ≡ y ≡ 1( mod k )
 x ≡ y ≡ 0 ( mod k )

-----Trang 7-----


Một số bài toán
Bài 1: Cho hình chữ L như hình vẽ .
Chứng minh rằng không thể phủ hình này bởi các trimino


2

3

1

Dễ thấy được cách phủ với các quân ( 1 × 3) .

1

2

3

1

2

3

1

1

2

3

1


2

3

1

2

3

1

Suy ra điều kiện để phủ được là S1 ≡ S 2 ≡ S3 ( mod 3)

1

2

3

1

2

3

1

(điều này đã được nêu rõ trong chứng minh định lý:

x

x

x

x

x

x

x

x

x

x

Đánh dấu các ô như hình vẽ
Nhận thấy mỗi L – trimino khi đặt vào hình chữ nhật
sẽ chỉ phủ được tối đa 1 ô được đánh dấu.
Giả sử mỗi ô của hình chữ nhật được phủ bởi đúng
k quân L – trimino, suy ra số lượng L – trimino tối
thiểu là 12k .
Nghĩa là sẽ phủ được không ít hơn 36k ô đơn vị của hình chữ nhật (các ô có thể được đếm nhiều
lần)
Bên cạnh đó chỉ có đúng 35k ô đơn vị được phủ, số lượng này nhỏ hơn 36k m suy ra vô lí.


đen và trắng xen kẽ (như hình ảnh của bàn cờ vua) sao cho 4 góc là 4 ô được tô đen. Tìm n để có
thể phủ tất cả các ô đen bởi L – trimino. Trong trường hợp phủ được hãy tìm số lượng L –
trimino tối thiểu phải dùng.
Giải
Nhận xét với n = 1,3 không thỏa mãn.
Với n = 5 . Đánh dấu các ô như hình vẽ
Suy ra phải có tối thiếu 9 L – trimino , suy ra số ô vuông đơn
vị sinh ra là không ít hơn 27 ô, số lượng này lớn hơn thực tế
là 25 ô.
Với n = 7 , ta chỉ ra được một cách phủ thỏa mãn, cần dùng
-----Trang 10-----

x

x

x

x

x

x

x

x

x


( k + 3)
+k+2=
4

2

,

ta có điều phải chứng minh.

Bài toán 7 (VMO – 2006). Xét bảng ô vuông m × n ( m, n ≥ 3) . Thực hiện trò chơi sau:
mỗi lần đặt 4 viên bi vào 4 ô của bảng, mỗi ô một viên bi, sao cho 4 ô đó tạo thành một
trong các hình dưới đây:

Hỏi sau một số lần ta có thể nhận được bảng mà số bi trong các ô bằng nhau được không
nếu:
a) m = 2004, n = 2006?
b) m = 2005, n = 2006?
Giải
Bảng đã cho có thể chia thành các hình chữ nhật 4 × 2 nên có thể nhận được trạng
thái mà số bi trong các ô bằng nhau.

a)

b)

Tô màu các ô như hình vẽ

Dễ thấy, mỗi lần đặt bi có 2 viên được đặt vào các ô màu đen và 2
viên được đặt vào ô màu trắng. Do đó, nếu gọi S ( n ) là số bi trong


S ( n ) − T ( n ) = n = 2006
vô lý.
Nhận thấy câu hỏi ý 2 tương tự bài Russia 1996, ta suy nghĩ hướng giải dựa trên tư tưởng
đó, và có lời giải thứ 2.
Lời giải 2
Đánh dấu các ô như hình vẽ, khi đó mỗi hàng và mỗi
cột đều có 1003 viên bi

x

x

x

x

x

x

x

x

x

Nhận thấy mỗi lần đặt bi có nhiều nhất 1 ô trong số
các ô được đánh dấu sẽ có bi.


các số trong hình (H2) đều là số lẻ. Do m, n chắn nên tổng các số trong toàn bộ hình chữ
nhật m × n là số chẵn. Để lát được thì tổng số hình (H1) và (H2) được sử dụng phải là số
chẵn. Khi đó, m.n chia hết cho 24, vô lý.
Bài 9 (Belarus 1999): Có 1 nền đất hình vuông 7 × 7 được chia thành 49 ô vuông đơn vị. Thực
hiện việc lát nền đất bởi 3 loại gạch lát nền:
Loại 1: Monomino (1× 1 )
Loại 2: Trimino thẳng (1 × 3 )
Loại 3: L – trimino (có 3 ô đơn vị, hình chữ L)
Giả sử A có 1 viên loại 3 và rất nhiều viên loại 2, B có 1 viên loại 1.
a. Chứng minh rằng B có thể lát viên gạch của mình lên một ô vuông đơn vị nào đó trên nền đất
mà A không thể lát kín phần còn lại.
b. Giả sử A có thêm 1 viên loại 3 nữa. Chứng minh rằng dù B lát viên gạch của mình ở đâu thì A
cũng lát kín được phần còn lại.
Giải
Đánh số các ô vuông đơn vị của hình chữ nhật như hình
vẽ, ô màu đen là ô B lát viên gạch của mình
Số các số 1 là 17, số 2 là 15, số 3 là 16
Nhận xét về các quân của A khi đặt nên hình chữ nhật
này:
Với Trimino thẳng, sẽ phủ được 3 ô có đủ 3 số lượng 1,
2 và 3.
L – trimino sẽ phủ được hoặc 3 số 1, 2, 3 hoặc 3 ô có 2
số giống nhau (ví dụ 2 ô 1 và 1 ô 3…)
Nếu A chỉ dùng Trimino thẳng thì hiển nhiên không phủ được.
-----Trang 13-----


Nếu A dùng thêm L – trimino thì lúc đó có hai trường hợp
• Phủ được 3 ô 1, 2, 3 còn lại không phủ được bởi trimino thẳng, hoặc phủ được 2 ô giống
nhau và 1 ô khác thì


2

1

Nhận thấy mỗi domino khi đặt vào hình chữ
nhật sẽ phủ được đúng hai ô mang số 1 và 2.

2

1

2

1

2

1

x

x

2

1

2



1

2

Nhận thấy số lượng số 1 và 2 bằng nhau và
bằng 28

1

2

1

x

x

2

1

2

1

2

1


1

2

1

2

1

2

1

2

1

2

Vậy số lượng tối đa các quân domino cần dùng
là 28.
Một số bài tập tham khảo

Bài 11: Tìm n để hình vuông n × n có thể được phủ bởi các hình chữ nhật 2 × 2 và 3 × 3 .
Bài 12: Tìm n ≥ 3 để hình vuông n × n cắt bỏ đi 4 ô vuông đơn vị ở 4 góc có thể được phủ bởi
các quân L – tetramino.
-----Trang 14-----



[7] www.mathlinks.ro

-----Trang 16-----