CÁC BÀI TOÁN HAY CÓ LỜI GIẢI DÀNH CHO HSG

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