Đề bài:
Cho bảng vuông 9×9 gồm 81 ô vuông đơn vị. Viết 81 số tự nhiên vào 81 ô vuông đơn vị sao cho trên mỗi hàng và mỗi cột có tối đa 4 số tự nhiên phân biệt xuất hiện.
Hỏi trên bảng vuông có tối đa bao nhiêu số tự nhiên phân biệt?
Hướng dẫn:
Ta sẽ chứng minh trong bảng không thể có quá 28 số tự nhiên phân biệt.
Thật vậy, giả sử ngược lại trên bảng có ít nhất 29 số phân biệt. Do có 9 dòng nên theo nguyên lý Dirichlet, phải có một dòng nào đó có đúng 4 số phân biệt.
Không mất tính tổng quát, ta có thể giả sử đó là dòng 1. Với ít nhất 25 số phân biệt và 8 dòng còn lại, thì vẫn theo nguyên lý Dirichlet phải có một dòng nào đó có đúng 4 số phân biệt, ta giả sử 4 số đó xuất hiện ở dòng 2.
Xét từng cột và 7 dòng còn lại, không dễ dàng, ta có thể suy luận được tổng số các số phân biệt tối đa bằng 8 + 9 × 2 = 26, nhỏ hơn 29.
Đây là một điều mâu thuẫn. Bây giờ ta dựng một bảng 9 × 9 với 28 số. Chia bảng thành 9 bảng nhỏ 3 × 3. Ở bảng trên cùng bên trái, điền các số từ 1 đến 9. Ở bảng ở giữa, điền các số từ 10 đến 18. Ở bảng dưới cùng bên phải, điền các số từ 19 đến 27. Điền các số 0 vào tất cả các vị trí còn lại. Mỗi dòng và cột đều có đúng 4 số phân biệt.
Vậy đáp số là 28.
Trần Phương
Phó giám đốc Trung tâm hỗ trợ phát triển tài năng