Cho bảng ô vuông kích thước 2000x2001 (bảng gồm 2000 hàng và 2001 cột). Hãy tìm số nguyên dương k lớn nhất sao cho ta có thể tô màu k ô vuông con của bảng thỏa mãn điều kiện:hai ô vuông con nào được tô màu cũng không có đỉnh chung.
Trả lờiBài 6 đề thi HSG quốc gia Việt Nam năm 2001, bảng B.
Được tạo lúc 2021-05-21 23:06:06 , cập nhật lúc 2021-05-21 23:06:06
hangtuan
tintuyet128
Chỉnh sửa lần cuối vào 2021-05-22 08:01:30
Nội dung
Nguồn: Nguyễn Tất Thu
hangtuan
Làm toán
Bình luận được tạo lúc 2021-05-23 00:33:34Chỉnh sửa lần cuối vào 2021-05-23 00:33:34
Nội dung
Mình có 1 hướng thế này.
Ta sẽ chia bảng thêm 1 cột nữa để tạo thành bảng 2000x2002. Ta chia bảng này ra thành các bảng vuông con 2x2, thì được: 1000x1001 bảng con 2x2. Lưu ý mỗi bảng con này chỉ có tối đa 1 ô được tô màu. Nên bảng 2000x2002 có tối đa 1000x1001 ô được tô màu. Suy ra bảng 2000x2001 có tối đa 1000.1001 ô được tô màu. Và ta có thể xây dựng được cách tô thỏa mãn.