Cách 1. Ta giải bài toán tổng quát: Điền các số 1.2.... n2 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| ≥ n Kí hiệu mk,Mk 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à m1,m2, ...,mn,M1,M2,… ….,Mn đôi một phân biệt. Đặt
m= max (m1,m2, ...,mn ) và M= min (M1,M2,… ….,Mn ) .
Xét hai trường hợp
· Nếu m < M thì ta có mk≤m≤Mk 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ố ak≤m<bk và với mỗi hàng k ta chọn cặp (ak,bk ) thuộc hai ô kề nhau ở hàng k. Vì b1,b2,…..bn lớn hơn m và các số b1,b2,…..bn là đôi một phân biệt nên tồn tại k ∈{1,2,….,n}. sao cho bk≥n+m và do đó
bk−ak≥(m+n)−m=n.
· Nếu m > M thì gọi i, j ∈{ 1, 2 ,...,n} là các chỉ số sao cho mi > M = Mj 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 ak,bk sao cho ak≤M<bk và ak,bk 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 ∈{ 1, 2 ,...,n}mà bk≥M+n . Suy ra
bk−ak≥(M+n)−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 ô Ai,BimaˋAiđược điền còn Bithì chưa.
Cần có Bi−Ai≤n−1 kéo theo Bi≤max(A1,A2,…..,An) + n -1,∀i
Mà các số từ 1 đến max(Ai)đều đã được điền nên Bi>max(Ai), vô lý do n số Biphân biệt.
Các trường hợp cho ta giả sử sai và ta có điều phải chứng minh.