Xếp hình?
Lời nói đầu
Trong series báo cáo này, (chúng) tôi sẽ trình bày một vấn đề, không hẳn là một “thuật toán” mà là một bài toán: làm sao để bao phủ một mặt phẳng bằng hình vẽ cho trước. Dạng tổng quát của bài toán này là NP-khó, nhưng trong một số trường hợp thì ta vẫn có những lỗi đi riêng nhờ sự trợ giúp của máy tính.
Bài 1
Cho một mạng lưới hình vuông cạnh 2n mà mỗi ô vuông có cạnh là 1. Hãy bao phủ mạng lưới trên bằng hình vẽ sau, biết rằng có một ô nào đó được để trống.
Trong đó:
n – độ dài của mạng lưới
x,y – tọa độ của ô để trống
Ý tưởng:
Nếu mạng lưới được bao phủ hết bằng hình trên, thì chắc hẳn số ô của mạng lưới phải chia hết cho 3
Thật vậy, 2nx2n – 1 = (4-1)(4n-1 + 4n-2 + … + 4 + 1) chia hết cho 3
Tiếp theo, chúng ta sẽ giải quyết vấn đề "lấp kín các ô còn lại trong mạng lưới". Hãy chia mạng lưới làm 4 mạng lưới vuông nhỏ hơn bằng nhau
Dễ dàng nhận thấy nếu n = 1, ta luôn có đáp số cho bài toán. Trước khi đến với dạng tổng quát, ta cần đi qua trường hợp n = 2
Giả sử rằng ô vuông cần được để "trống" là một trong những ô trong hình kia, ta có thể có nhiều cách chọn khác nhau mà vẫn giải quyết được bài toán
Với trường hợp tổng quát, ta có thể "sử dụng" 3 hình trên để giải hết tất cả các trường hợp của n.
Bài 2
Cho một mạng lưới hình vuông có cạnh (6N+1). Hãy bao phủ mạng lưới trên bằng hình vẽ sau, biết rằng có một ô nào đó được để trống.
Trong đó:
n - độ dài của mạng lưới theo yêu cầu
x, y - tọa độ của ô để trống
Ý tưởng:
Đầu tiên, ta xét với trường hợp N=1 nhỏ nhất
Bằng các phép đối xứng, xoay hình, ta có thể giải được tất cả những bài toán N=1 bằng 3 hình trên.
Giả sử, ta biết làm thế nào để lát mạng lưới vuông cạnh 6N+1, ta sẽ thử tìm cách lát mạng lưới vuông cạnh 6N+7
Dễ dàng thấy rằng, hình vuông (6N+1) x (6N+1) nhỏ hơn hình vuông (6N+7) x (6N+7) nên ta sẽ chia hình 6N+7 thành hình nhỏ như sau
Và cuối cùng, phần "thừa" ở góc phải trên của hình chính là bài toán với N = 1 ban đầu.
//Last edit: Tập tin nội bộ trường chuyên KHTN, tham khảo acm.sgu.ru ; ACM ICPC 1997 ; Bugs CEOI 2002 ; IOI 2005 ; CSP 1993 ; ...
Full post đăng tải trên minhtt159.wordpress.com
Nguồn : Tin Tuyển 2013 (Trần Tuấn Minh - Nguyễn Mạnh Cường - Nguyễn Hoàng Long)
