Trang web hay khi không có unicode trong máy

http://www.vntyping.com

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---

Toán câm (Slient Math)

Một thứ toán học không nhiều người biết tới.
Toán không dùng từ (Proof without words) hay hạn chế dùng từ một cách tối đa. Người ta sẽ diễn đạt cách chứng minh vấn đề bằng cách sử dụng những hình vẽ hay sơ đồ. Cách thể hiện vấn đề như thế này sẽ mang lại sự thú vị bởi những bất ngờ. Ngoài ra nó còn giúp ta nhìn nhận điều cần chứng minh theo một khía cạnh khác, giúp ta thấm thía và hiểu nó hơn.
Một số ví dụ
*Tổng các số lẻ liên tiếp bắt đầu từ 1

*Định lí Pytago

*Bất đẳng thức Jensen

Nguồn tham khảo
Proof without words