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
Chương trình cài đặt như sau:
Uses crt;
Const
fo = ′phuchu_l.out ′;
Var
a : array [1..150, 1..150] of integer;
m, n, sl : integer;
f : text;
Procedure Init;
Begin
clrscr;
write( ′Nhap kich thuoc m, n : ′);
readln(m, n);
End;
Procedure error;
Begin
write( ′KHONG THE XEP DUOC! ′);
readln;
halt;
End;
Procedure Check;
Begin
if m * n mod 3 <> 0 then error;
sl := 0;
End;
Procedure xep3(m, n : integer);
Var
sl1, i : integer;
Begin
if m mod 2 <> 0 then error;
sl1 := sl;
for i := 1 to m do
begin
if i mod 2 = 1 then inc(sl, 2);
a[i, n - 2] := sl;
a[i, n] := sl + 1;
if i mod 2 = 1 then a[i, n - 1] := sl + 1
else a[i, n - 1] := sl;
end;
End;
Procedure xep(m, n : integer);
Var
c, i, sl1 : integer;
Begin
c := 1;
while (c < n)and(c<>n - 2) do
begin
sl1 := sl;
for i := 1 to m do
begin
if i mod 3 = 1 then inc(sl);
if i mod 3 = 0 then inc(sl);
a[i, c] := sl;
end;
inc(c); sl := sl1;
for i := 1 to m do
begin
if i mod 3 = 1 then inc(sl);
if i mod 3 = 2 then inc(sl);
a[i, c] := sl;
end;
inc(c);
end;
if c = n - 2 then xep3(m, n); {xet rieng 3 cot cuoi}
End;
Procedure Print;
Var
i, j, k : integer;
Begin
assign(f, fo);rewrite(f);
if m mod 3 = 0 then
for i := 1 to m do
begin
for j := 1 to n do
begin
textbackground((a[i, j] mod 7));
if (m <= 15) and (n <= 15) then write(a[i, j] : 4);
write(f, a[i, j] : 5);
textbackground(black);
end;
writeln; writeln(f);
end
else
for j := 1 to m do
begin
for i := 1 to n do
begin
textbackground((a[i, j] mod 7));
if (m <= 15) and (n <= 15) then write(a[i, j] : 4);
write(f, a[i, j] : 5);
textbackground(black);
end;
writeln;writeln(f);
end;
close(f);
writeln( ′Moi mo tep phuchu_l.out xem ′);
readln
End;
Begin
Init;
check;
if m mod 3 = 0 then xep(m, n)
else xep(n, m);
Print;
End.
II. Bài toán 2:
Hãy phủ một nền nhà hình vuông kích 2N * 2N (N ≤ 7) bằng những viên gạch thước thợ sao cho còn lại đúng một ô tại vị trí (x, y) cho trước (lỗ thoát nước).
Dữ liệu: Đọc từ màn hình N
Kết quả: Xuất ra file LATCHU_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 Dấu X thể hiện lỗ thoát nước.
Ví dụ: N = 2, X = 2, Y = 2 ta có vídụ về một cách xếp thoả mãn như sau:
