Cho n là số nguyên dương thỏa mãn tính chất: Nếu n quân domino được đặt lên một bàn cờ \[6 \times 6\] sao cho mỗi quân domino chiếm đúng 2 ô vuông đơn vị và không quân domino chèn lên nhau thì ta luôn có thể đặt thêm một quân domino lên bàn cờ mà không cần phải di chuyển các quân domino đã có. Xác định giá trị lớn nhất của n.
#2
Đã gửi 26-07-2012 - 12:50
The Gunner
-
- Thành viên
-
- 93 Bài viết
Hạ sĩ
Bài này xài đơn ánh 
Ta gọi các ô được chèn bởi các quân domino là 1, còn các ô ko được chèn là 0.
Xét hình chữ nhật $5 \times 6$ nằm ở miền trên của hình vuông $6 \times 6$ thế thì ở hàng cuối phải có nhiều nhất 3 ô 0.
Giả sử ko quá 11 quân domino cần lắp mà ko thể đặt thêm thì số ô 0 là 14 do đó số ô 0 trong hình $5 \times 6$ ít nhất là $11$
mà ta nhận thấy với mỗi ô 0 thì ô ngay dưới nó là ô 1, và hai ô 1 nằm dưới 2 ô 0 ko thể cùng được chèn bởi một quân domino vì khi đó hai ô 0 ở trên cũng sẽ được lắp bởi quân domino
Do đó với mỗi ô 0 thì ngay trên nó phải có 1 quân domino. Do đó mỗi ô 0 trong hình $5 \times 6$ tương ứng với một quân domino ko chèn lên hàng trên cùng của bàn cờ. Do đó số quân domino ko nhỏ hơn số ô 0 là $11$.Do đó số quân domino phải là 11
mặt khác với $11$ quân domino thì hàng trên cùng phải bị phủ bởi ít nhất một quân domino. Do đó với x=11 vẫn còn có thể đặt thêm một quân domino nữa.
với 12 quân domino thì ta xếp xem kẻ mỗi cột 2 quân domino xếp thẳng đứng thì ko thể lắp thêm 1 quân domino nào đc nữa
Ta gọi các ô được chèn bởi các quân domino là 1, còn các ô ko được chèn là 0.
Xét hình chữ nhật $5 \times 6$ nằm ở miền trên của hình vuông $6 \times 6$ thế thì ở hàng cuối phải có nhiều nhất 3 ô 0.
Giả sử ko quá 11 quân domino cần lắp mà ko thể đặt thêm thì số ô 0 là 14 do đó số ô 0 trong hình $5 \times 6$ ít nhất là $11$
mà ta nhận thấy với mỗi ô 0 thì ô ngay dưới nó là ô 1, và hai ô 1 nằm dưới 2 ô 0 ko thể cùng được chèn bởi một quân domino vì khi đó hai ô 0 ở trên cũng sẽ được lắp bởi quân domino
Do đó với mỗi ô 0 thì ngay trên nó phải có 1 quân domino. Do đó mỗi ô 0 trong hình $5 \times 6$ tương ứng với một quân domino ko chèn lên hàng trên cùng của bàn cờ. Do đó số quân domino ko nhỏ hơn số ô 0 là $11$.Do đó số quân domino phải là 11
mặt khác với $11$ quân domino thì hàng trên cùng phải bị phủ bởi ít nhất một quân domino. Do đó với x=11 vẫn còn có thể đặt thêm một quân domino nữa.
với 12 quân domino thì ta xếp xem kẻ mỗi cột 2 quân domino xếp thẳng đứng thì ko thể lắp thêm 1 quân domino nào đc nữa
- perfectstrong, funcalys, Stranger411 và 3 người khác yêu thích
Những ngày cuối cùng còn học toán
winwave1995
1 người đang xem chủ đề
0 thành viên, 1 khách, 0 thành viên ẩn danh
