Chủ đề này có 2 trả lời

[dangqxdang]

Điền các số tự nhiên từ $1$ tới $n^2$ vào bảng ô vuông $n \times n$ ô vuông (mỗi ô một số không lặp lại). Chứng minh tồn tại 2 ô vuông chung cạnh có hiệu hai số lơn hơn hoặc bằng $n +1$.

Bài viết đã được chỉnh sửa nội dung bởi perfectstrong: 28-10-2023 - 00:42
Tiêu đề & LaTeX

[Nguyen Bao Khanh]

Nếu như 2 ô chung cạnh thì mình có thể đưa ra phản ví dụ nhé, bài toán chỉ đúng với 2 ô chung đỉnh thôi.
Đây là lời giải của mình:
Bằng cách đếm tối ưu, xét 2 ô được ghi số $1;n^2$. Giữa 2 ô ấy có tối đa $n-1$ cặp ô (trong trường hợp ô ghi số 1 ở hàng thứ 1, ô ghi số $n^2$ ở hàng thứ $n$), theo nguyên lý đirichlet tồn tại 1 cặp ô ghi 2 số có giá trị tuyệt đối của hiệu không bé hơn $\lfloor \frac{(n^2-1)-1}{n-1} \rfloor +1=n+1$

Bài viết đã được chỉnh sửa nội dung bởi Nguyen Bao Khanh: 09-02-2024 - 21:36

[Hoang72]

Bài này theo mình nghĩ, là yêu cầu chứng minh tồn tại hai ô chung cạnh có hiệu hai số lớn hơn hoặc bằng $n$.

Xét $k$ là số nguyên dương nhỏ nhất sao cho các số $1,2,...,k$ hoặc xuất hiện trên mọi hàng, hoặc xuất hiện trên mọi cột.

Không mất tính tổng quát, coi $k$ số này xuất hiện trên mọi hàng.

NX. Mọi hàng đều chứa ít nhất một ô không chứa một trong các số $1,2,...,k$.

Chứng minh. Giả sử tồn tại hàng $i$ trái với tính chất trên. Khi đó các số $1,2,...,k$ cũng xuất hiện trên mọi cột, mà các số $1,2,..,k-1$ không xuất hiện trên mọi cột nên $k$ thuộc hàng $i$. Chứng tỏ các số $1,2,...,k-1$ vẫn xuất hiện trên mọi hàng, mâu thuẫn.

Như vậy, với hàng $i$ bất kì, ta tìm được hai ô chứa hai số $a_i,b_i$ sao cho $a_i\in\left\{1,2,...,k\right\}$ và $b_i > k$. Chú ý $b_1,b_2,...,b_n$ là các số lớn hơn $k$ nên tồn tại một số $b_j$ không nhỏ hơn $k + n$.

Thế thì $b_j - a_j \geq n$, và $b_j,a_j$ là hai số ở hai ô chung cạnh. (đpcm)