Đến nội dung

Hình ảnh

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


  • Please log in to reply
Chủ đề này có 2 trả lời

#1
dangqxdang

dangqxdang

    Hạ sĩ

  • Thành viên
  • 81 Bài viết

Đ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


#2
Nguyen Bao Khanh

Nguyen Bao Khanh

    Hạ sĩ

  • Hái lộc VMF 2024
  • 73 Bài viết
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


#3
Hoang72

Hoang72

    Thiếu úy

  • Điều hành viên OLYMPIC
  • 539 Bài viết

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)

 






1 người đang xem chủ đề

0 thành viên, 1 khách, 0 thành viên ẩn danh