Viết 100 số nguyên dương đầu tiên 1,2,...,100 vào một bảng ô vuông kích thước
Cách 1. Ta giải bài toán tổng quát: Điền các số 1.2.... \({n^{2\;}}\) với n > 1 vào các ô vuông của bảng cỡn nn Khi đó tồn tại hai ô vuông kề nhau (chung cạnh) chứa hai số x, y mà |x - y| \( \ge \) n Kí hiệu \({m_k},{M_k}\;\) tương ứng là số nhỏ nhất và số lớn nhất của hàng thứ k với k = 1, 2 ,...,n. Chú ý là \({m_1},{m_2},\) ...,\({m_n},{M_1},{M_2}, \ldots \ldots .,{M_n}\) đôi một phân biệt. Đặt
m= max (\({m_1},{m_2},\) ...,\({m_n}\) ) và M= min (\({M_1},{M_2}, \ldots \ldots .,{M_n}\) ) .
Xét hai trường hợp
· Nếu m < M thì ta có \({m_k} \le m \le {M_k}\;\) với mọi k = 1, 2 ,...,n. Điều này suy ra với hàng k bất kỷ thì tồn tại hai số \({a_k} \le m < {b_k}\;\) và với mỗi hàng k ta chọn cặp (\({a_k},{b_k}\;\) ) thuộc hai ô kề nhau ở hàng k. Vì \({b_1},{b_2}, \ldots ..{b_n}\) lớn hơn m và các số \({b_1},{b_2}, \ldots ..{b_n}\) là đôi một phân biệt nên tồn tại k \( \in \left\{ {1,2, \ldots .,n} \right\}\;\). sao cho \({b_k} \ge n + m\) và do đó
\({b_k} - {a_k} \ge \left( {m + n} \right) - m = n.\)
· Nếu m > M thì gọi i, j \( \in \{ \) 1, 2 ,...,n} là các chỉ số sao cho \({m_i}\) > M = \({M_j}\) Khi đó tại mỗi cột luôn tồn tại các số không vượt quá M (ví dụ như số hàng j) và các số lớn hơn M (ví dụ như số ở hàng i). Khi đó với cột k bất kỳ tồn tại \({a_k},{b_k}\;\) sao cho \({a_k} \le M < {b_k}\) và \({a_k},{b_k}\) thuộc hai ô kề nhau của cột k. Tương tự như trường hợp đầu tiên thì ta cũng có tồn tại k \( \in \{ \) 1, 2 ,...,n}mà \({b_k} \ge M + n\) . Suy ra
\({b_k} - {a_k} \ge \left( {M + n} \right) - m = n.\)
Trong mọi tình huống ta đều có điều phải chứng minh.
Cách 2. Giả sử phản chứng, tồn tại cách điền để không tồn tại x,y như vậy. Ta lần lượt điền các số bắt đầu từ 1 vào bảng ô vuông, xét thời điểm đầu tiên mà cả n cột đều đã được điền số. Ta xét hai trường hợp sau:
· Nếu tồn tại cột nào đó đã được phủ hoàn toàn, ta sẽ đổi vai trò của hàng và cột (xét thời điểm đầu tiên cả n hàng đều có số). Nếu khi đó lại tồn tại một hàng được phủ hoàn toàn, thì tức là hai thời điểm đang xét trùng nhau. Điều này là không thể vì ô vừa được thêm phải là ô cuối cùng của hàng và cột đó, xét thời điểm ngay trước đó cho ta tất cả các hàng đều đã được điền.
· Nếu không tồn tại cột đã phủ hoàn toàn, do mỗi cột đều có ô đã điền, ta có thể chọn ra ở cột thứ i được cặp ô \({A_i},{B_i}m\`a \;{A_i}\)được điền còn \({B_i}\;\)thì chưa.
Cần có \({B_i} - {A_i} \le n - 1\;\) kéo theo \({B_i} \le max\)(\({A_1},{A_2}, \ldots ..,{A_n}\)) + n -1,\(\forall i\)
Mà các số từ 1 đến max(\({A_i})\;\)đều đã được điền nên \({B_i} > {\rm{max}}\left( {{A_i}} \right)\), vô lý do n số \({B_i}\;\)phân biệt.
Các trường hợp cho ta giả sử sai và ta có điều phải chứng minh.