Bài 2 IMO 2014

Đề bài: Cho số nguyên dương $n\geq 2$, và bảng ô vuông $n\times n$ gồm $n^2$ ô vuông nhỏ. 1 cấu hình $n$ ô vuông nhỏ được gọi là "thanh bình" nếu mỗi hàng và mỗi cột của bảng chứa đúng 1 ô vuông nhỏ. Tìm số nguyên dương $k$ lớn nhất sao cho với mỗi cấu hình $n$ ô vuông nhỏ "thanh bình"  luôn tồn tại 1 hình vuông $k\times k$ của bảng không chứa 1 ô vuông nhỏ nào (trong $n$ ô vuông "thanh bình").

Lời giải

Trước hết tôi xin đưa ra đáp số: Với $n$ xác định một $m$ thoả mãn $m^2+1\le n\le(m+1)^2$ thì $k$ tốt nhất là $m$ hay $k=\sqrt{n-1}$.

Mỗi ô vuông nhỏ được kí hiệu $(i,j)$ trong đó $i$ là chỉ số cột, $j$ là chỉ số hàng.

Giả sử $n$ ô vuông tạo thành một cấu hình thanh bình là $(1,b_1),\text{ }(2,b_2),...,\text{ }(n,b_n)$.

*Trường hợp $n=(m+1)^2$ ta đưa ra cấu hình thoả mãn $k=m$ như sau: $b_{(m+1)(j-1)+i}=j+(m+1)(i-1)$ với $j=1,2...(m+1)$, $i=1,2,...(m+1)$. $(1)$

(chứng minh (1) sẽ có ở dưới, tôi không đưa ra tại đây để không làm đứt mạch ý tưởng giải)

*Còn với tổng quát $m^2+1\le n\le(m+1)^2$ thì từ cấu hình trên ta lần lượt bỏ $i$ hàng từ dưới lên trên, $i$ cột từ phải sang trái để tạo thành hình vuông $n\times n$ thích hợp và bổ sung thêm một số ô vuông thanh bình cần thiết để có đủ $n$ ô vuông thanh bình.

Việc chỉ ra cấu hình thoả mãn $k=m$ chứng tỏ một điều là $k$ tốt nhất phải nhỏ hơn hoặc bằng $m$.

Giả sử $k$ bằng $m$ không thoả mãn (tức là $k<m$).

Với $m$ cột liên tiếp tương ứng $m$ số là chỉ số hàng của $m$ ô thanh bình trong $m$ cột trên $b_s,\text{ }b_{s+1},..b_{s+m-1}$, sắp xếp lại theo thứ tự tăng dần là $b_{i_1}<b_{i_2}<...<b_{i_m}$.

Do $k=m$ không thoả mãn nên $b_{i_1}-1\le (m-1),\text{ }n-b_{i_m}\le (m-1),\text{ }b_{i_2}-b_{i_1}\le m,\text{ }b_{i_3}-b_{i_2}\le m,...b_{i_m}-b_{i_(m-1)}\le m$.

Hệ quả là $b_{i_1} \le m,\text{ } b_{i_m} \ge (n-m+1)$ và $b_{i_m} - b_{i_1} \le m(m-1)$.

Xét $m$ bộ $m$ cột liên tiếp là $(1,2,...m)$, $m+1,m+2,...2m$,...$\left( m(m-1)+1,m(m-1)+2,...m^2 \right)$, ta quan tâm tới chỉ số hàng của các ô thanh bình.

Gọi $x_1,\text{ }x_2,...x_m$ là chỉ số hàng bé nhất trong mỗi bộ của $m$ bộ (các $x_i$ khác nhau).

Gọi $y_1,\text{ }y_2,...y_m$ là chỉ số hàng lớn nhất trong mỗi bộ của $m$ bộ (các $y_i$ khác nhau).

Ta có $x_i\in\{1,2,..m\}$, $y_i\in\{n-m+1,n-m+2,...n\}$ và $y_i-x_i\le m(m-1)$

Do đó

$(y_1+y_2+...+y_m)-(x_1+x_2+...+x_m)\le m^2(m-1)$, suy ra $n\le m^2$, vô lí vì ta đang xét $m^2+1\le n\le(m+1)^2$.

Để kết thúc ta sẽ đi chứng minh $(1)$:

Với cấu hình như trên thì ta chọn được hình vuông $m\times m$ thoả mãn là hình có ô trên cùng bên trái là $(2,2)$, ô dưới cùng bên phải là $(m+1,m+1)$.

Chia $(m+1)^2$ cột thành $m+1$ nhóm, mỗi nhóm gồm $m+1$ cột liên tiếp.

Nhận xét: Trong mỗi nhóm, khoảng cách giữa $2$ ô thanh bình "gần" nhau nhất là $m$ (tức là có $m$ hàng nằm giữa $2$ ô đó)

Không tồn tại một hình vuông $(m+1)\times (m+1)$ thoả mãn bởi:

Khi ta xét $m+1$ cột liên tiếp, giả sử có $a$ cột thuộc nhóm $t$ và $b$ cột thuộc nhóm$t+1$, nếu có $2$ ô thanh bình "sát nhau" (tức là giữa chúng không có ô thanh bình nào nữa) có khoảng cách là $m+1$ thì $1$ ô thuộc cột thuộc nhóm $t$ và một ô thuộc cột thuộc nhóm $t+1$, điều này trái với nhận xét trên.

---đêm Hà Nội 19/7/2015---