Đến nội dung

Hình ảnh

chứng minh tồn tại một số lặp lại $n$ lần

- - - - -

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

#1
lovemathforeverlqd

lovemathforeverlqd

    Binh nhất

  • Thành viên mới
  • 26 Bài viết

Cho bảng gồm $n*n$ ô vuông, mỗi ô vuông là 1 số nguyên. Biết rằng 2 số bất kì liền cạnh nhau có hiệu không lớn hơn 1. Chứng minh có 1 số xuất hiện $n$ lần.

Thanks :)


Bài viết đã được chỉnh sửa nội dung bởi lovemathforeverlqd: 26-07-2016 - 09:10


#2
L Lawliet

L Lawliet

    Tiểu Linh

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

Cho bảng gồm $n*n$ ô vuông, mỗi ô vuông là 1 số nguyên. Biết rằng 2 số bất kì liền cạnh nhau có hiệu không lớn hơn 1. Chứng minh có 1 số xuất hiện $n$ lần.

Thanks :)

Lời giải 1.

Giả sử không có số nào được xuất hiện quá $n$ lần thì lúc đó với mỗi số $a$ bất kì thì tồn tại nhiều nhất $n-1$ cột có chứa số $a$ và nhiều nhất $n-1$ hàng chứa số $a$. Từ đó suy ra có 1 hàng và 1 cột không chứa số $a$. Gọi $m,n$ lần lượt là số lớn nhất và số nhỏ nhất được viết lên bảng. Với mỗi số tự nhiên $b$ bất kì ở trong khoảng $[n;m]$ thì gọi hình chữ thập tạo bởi một hàng và một cột không chứa $b$ là $C_b$. Ta có nhận xét rằng $C_b$ chỉ chứa các số lớn hơn $b$ hoặc chỉ chứa các số nhỏ hơn $b$. Thật vậy nếu tồn tại 2 số $c$ và $d$ sao cho $c>b>d$ và $c$ và $d$ đều thuộc $C_b$ thì vì 2 ô liên tiếp chênh lệch nhau không quá 1 đơn vị nên tất cả các số nằm giữa $c$ và $d$ đều nằm trên $C_b$ vì có thể dịch chuyển từ $c$ đến $d$ thông qua 1 số ô liên tiếp nắm trong $C_b$. Vì vậy nên $b$ nằm trên $C_b$(vô lí)

Lại có $n$ là số nhỏ nhất viết lên bảng nên $C_n$ chỉ chứa các số lớn hơn $n$, tương tự $C_m$ chỉ chứa các số nhỏ hơn $m$. Vì vậy tồn tại số tự nhiên $s$ sao cho $m>s\geq n$ và $C_s$ chỉ chứa các số lớn hơn s, $C_{s+1}$ chỉ chứa các số bé hơn $s+1$. Hai hình chữ thập đó cắt nhau tại ít nhất 1 ô chứa số $e$  thoả mãn $s+1>e>s$( vô lí) 

Vậy giả sử sai, hay tồn tại 1 số lặp lại ít nhất $n$ lần

 

Lời giải 2.

Đầu tiên có nhận xét sau : Cho một số số được viết liên tiếp nhau sao cho khoảng cách giữa hai số liên tiếp không quá 1 . Trong dãy đó , nếu tồn tại một số nhỏ hơn (hoặc bằng) $k$ và một số lớn hơn (hoặc bằng) $k$ thì sẽ có ít nhất một số trong dãy là $k$ .

 

Trở lại với bài toán :

Gọi $m$ là số lớn nhất trong $n$ số nhỏ nhất của mỗi hàng .

Ta chứng minh $m$ là số nhỏ nhất .

Thật vậy , nếu mỗi hàng đều có một số lớn hơn hoặc bằng $m$ ta áp dụng nhận xét cho từng hàng (đều có số nhỏ hơn hoặc bằng $m$ là số nhỏ nhất mỗi hàng ) thì mỗi hàng có ít nhất một số là $m$

Xét trường hợp tồn tại một hàng nào đó chỉ có toàn số nhỏ hơn $m$ . Ta lại có hàng chứa số $m$ là hàng gồm toàn số lớn hơn hoặc bằng $m$ . Áp dụng nhận xét cho mỗi cột thì mỗi cột có ít nhất một số là $m$

Từ trên có dpcm


Bài viết đã được chỉnh sửa nội dung bởi L Lawliet: 26-07-2016 - 12:24

Thích ngủ.





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

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