Cho một bảng ô vuông $3k\times 3k$ ($k$ là số nguyên dương), các ô của bảng được đánh tọa độ theo cột và hàng: ô $(i;j)$ nằm trên cột thứ $i$ từ trái qua phải và trên hàng thứ $j$ từ dưới lên trên. Người ta muốn đặt $4k$ viên bi vào các ô của bảng, mỗi ô có không quá một viên, thỏa mãn đồng thời hai điều kiện sau:
- Mỗi hàng và mỗi cột đều có ít nhất một viên bi;
- Mỗi viên bi nằm cùng hàng hoặc cùng cột với ít nhất một viên bi khác.
a) Xét $k=1$. Có bao nhiêu cách đặt 4 viên bi vào bảng thỏa mãn các điều kiện trên? (Hai cách đặt bi được coi là khác nhau nếu có một ô $(i;j)$ có bi trong một cách đặt nhưng không có bi trong cách còn lại.)
b) Xét $k\ge 1$ tổng quát. Xác định số tự nhiên $N$ lớn nhất sao cho với mọi cách đánh dấu $N$ ô phân biệt trên bảng, luôn tồn tại một cách đặt $4k$ viên bi thỏa mãn các điều kiện trên mà không có viên bi nào đặt ở một trong $N$ ô đã được đánh dấu.

LỜI GIẢI.

a) Trước hết, do trong 4 viên bi sẽ luôn có ít nhất hai viên bi nằm cùng một hàng hoặc cùng một cột, giả sử là $A$ và $B$. Không mất tính tổng quát giả sử $A,B$ cùng hàng nếu cùng cột thì ta có thể xoay bảng ô vuông một góc $90°$. Khi đó trong 9 ô còn lại sẽ có đúng hai ô không nằm cùng hàng hoặc cùng cột với $A$ và $B$, giả sử là $X$ và $Y$ (Lưu ý $X$ và $Y$ sẽ nằm cùng cột do $A$ và $B$ cùng hàng).



Điều này dẫn tới tồn tại ít nhất một viên bi nằm trong hai ô $X$ và $Y$ này, giả sử là $C$. Gọi viên bi cuối cùng chưa được điền là $D$, khi đó do $C$ không nằm cùng hàng với $A$ và $B$ nên $D$ phải nằm trên hàng còn lại. Cuối cùng, do $C$ không nằm cùng hàng với $A$ và $B$ nên $D$ phải nằm phải nằm cùng hàng hoặc cùng cột với $C$. Chú ý, $C$ không nằm cùng hàng với $D$ nên $C,D$ phải cùng cột. Từ đó suy ra $\{C,D\}=\{X,Y\}$ hay với $A,B$ cùng hàng hoặc cùng cột được xác định trước thì $C,D$ xác định duy nhất.

Từ đó, ta quy bài toán về việc đếm số cặp ô nằm cùng hàng hoặc cùng cột. Ta có 3 hàng, 3 cột và với mỗi hàng hoặc mỗi cột có $C_3^2=3$ cách chọn hai ô bất kì. Vậy số cặp ô nằm cùng hàng hoặc cùng cột trên bảng $3\times 3$ là $6\cdot 3=18$. Chú ý, do vai trò của bộ $\{A,B\}$ và $\{C,D\}$ là như nhau nên đáp số của bài toán là 9.

b) (Dựa trên lời giải của Nguyễn Nguyễn) Ta sẽ chứng minh đáp số của bài toán là $N=3k-1$. Với $N=3k$, ta đánh dấu tất cả các ô ở hàng đầu tiên, khi đó sẽ không có cách nào đặt được $4k$ viên bi thỏa mãn yêu cầu (do hàng một không có bất kì ô nào).

Với $N=3k-1$, ta chia bảng $3k\times 3k$ thành các thành $k^2$ khối $3\times 3$. Ta phân $k^2$ khối này vào $k$ tập hợp sao cho mỗi tập hợp có $k$ khối và hai khối bất kỳ trong cùng một tập hợp khác hàng và khác cột của nhau. (Hình dưới đây minh họa cho $k=3$, theo đường chéo)



Do $N=3k-1$ nên theo nguyên lý Dirichlet sẽ có một tập hợp trong $k$ tập hợp này chỉ chứa tối đa 2 ô vuông được đánh dấu. Xét $k$ khối có kích thước $3\times 3$ trong tập hợp này, ta có thể đặt vào mỗi khối 4 viên bi sao cho

- Trong khối $3\times 3$ sẽ có có tối đa hai ô được đánh dấu và những viên bi sẽ không được đặt vào những ô này.
- Mỗi hàng và mỗi cột sẽ chứa ít nhất 1 viên bi.
- Mỗi viên bi nằm cùng hàng hoặc cùng cột với ít nhất một viên bi khác.

Đây chính là bài toán trong trường hợp $k=1$. Ta có thể dễ dàng giải quyết bài toán này dựa trên các cách điền thỏa mãn ở câu a) nên có được điều phải chứng minh.