Bài toán xếp gạch chữ L nổi tiếng

Mô típ các bài toán phủ gạch chữ L

Công Hiệp

Các bài toán loại lát nền bằng những viên gạch thước thợ khá quen thuộc đối với mỗi

chúng ta. Nó từng được nhắc tới khá nhiều trong tạp chí và trong các kỳ thi HSG. Cùng

với một số bài mang tính tham khảo thêm, tôi muốn cùng các bạn tổ hợp lại những bài tập

tin nhưng mang đậm tính suy luận toán học này.

Trước hết, hãy xét bài toán cơ sở:

I. Bài toán 1: Hãy phủ kín một nền nhà hình chữ nhật kích thước M*N (M, N ≥ 3) bằng

những viên gạch thước thợ (hình chữ L, chiếm 3 ô vuông đơn vị) hoặc thông báo là không

thể làm được điều đó.

Dữ liệu: Đọc từ màn hình kích thước M N

Kết quả: Xuất ra file PHUCHU_L.OUT -1 nếu không tồn tại cách phủ, ngược lại in ra ma

trận số biểu hiện cách phủ, trong đó cứ 3 số giống nhau tạo miền liên thông hình chữ L thể

hiện một viên gạch

Ví dụ: M = 3 và N = 4

Cơ sở thuật toán: Dễ thấy rằng nếu cả hai chỉ số kích thước của bảng M, N đều không

chia hết cho 3 thì bài toán vô nghiệm, bởi khi đó M*N không chia hết cho 3 trong khi đó,

số ô mà các viên gạch phủ được lại luôn chia hết cho 3. Trong các trường hợp ngựơc lại,

không mất tính tổng quát ta giả sử M (số dòng) chia hết cho 3 (nếu N chia hết cho 3 thì ta

lại đảo cạnh). Ta tách hai trường hợp:

Nếu N là số chẵn, đặt N = 2k. Ta hoàn toàn có thể làm tương tự như trường hợp 3*4 ở trên,

2 viên gạch đặt chồng lên nhau sẽ phủ kín hình chữ nhật 3*2 -> ghép những viên gạch này

ta sẽ có được hình chữ nhật kích thước M*N tuỳ ý (với M = 3q và N = 2k).

Trong trường hợp N là số lẻ, dễ thấy N -3 là số chẵn => ta đã phủ được hình chữ nhật M *

(N-3) như cách làm trên. Vấn đề còn lại là phủ nốt hình chữ nhật kích thước M*3 (3 cột

cuối cùng). Dễ thấy nếu M chia hết cho 2 thì ta lại quay chỉ số 3 làm dòng và M là số cột,

ta sẽ phủ nốt hình chữ nhật kích thước 3*M này => bài toán có nghiệm, trong trường hợp

ngược lại (M lẻ), bài toán vô nghiệm.

Ví dụ: M = 6, N = 5