Cho bảng vuông $n\times n$ gồm $n^{2}$ ô vuông đơn vị. Điền vào các ô đơn vị các số nguyên sao cho hai ô cạnh nhau (có cạnh chung) được điền vào hai số chênh lệch nhau không quá $1$ đơn vị. Chứng minh rằng có một số xuất hiện ít nhất $n$ lần.
Chứng minh rằng có một số xuất hiện ít nhất $n$ lần
#1
Đã gửi 30-04-2016 - 16:47
- Zaraki, nhungvienkimcuong, ineX và 2 người khác yêu thích
#2
Đã gửi 03-05-2016 - 23:18
Cho bảng vuông $n\times n$ gồm $n^{2}$ ô vuông đơn vị. Điền vào các ô đơn vị các số nguyên sao cho hai ô cạnh nhau (có cạnh chung) được điền vào hai số chênh lệch nhau không quá $1$ đơn vị. Chứng minh rằng có một số xuất hiện ít nhất $n$ lần.
Bài này là bài quen thuộc anh ạ tuy nhiên cách giải của nó khá rối rắm
Trên mỗi hàng chọn ra số lớn nhất. Gọi số bé nhất trong các số đó là $a$
Trên mỗi hàng chọn ra số bé nhất. Gọi số lớn nhất trong các số đó là $b$
Trên mỗi cột chọn ra số lớn nhất. Gọi số bé nhất trong các số đó là $c$
Trên mỗi cột chọn ra số bé nhất. Gọi số lớn nhất trong các số đó là $d$
Trước hết ta chứng minh $c \geq b$
Thật vậy gọi $e$ là số nằm trên cột chứa $c$ và hàng chứa $b$
Khi đó theo cách gọi $c\geq e,e \geq b$ suy ra $c \geq b$
Tương tự $a \geq d$
TH1 : $a>b$
Gọi $x$ là một số bất kỳ nằm giữa $a$ và $b$
Khi đó dễ thấy hàng nào cũng phải chứa $x$ (Vì trên mỗi hàng $x$ đều không nhỏ hơn số bé nhất của hàng đó và không lớn hơn số lớn nhất của hàng đó)
Khi đó $x$ lặp lại $n$ lần
TH2 :$a \leq b$
-Nếu $c>d$ thì xét tương tự TH1
-Nếu $c \leq d$
Theo trên ta có: $c \geq b \geq a \geq d$
Từ đây dễ suy ra $a=b=c=d$ suy ra cả $n^2$ số trên bảng đều bằng nhau
Vậy tồn tại một số xuất hiện ít nhất $n$ lần
- thinhrost1, Ego, dunghoiten và 2 người khác yêu thích
#3
Đã gửi 11-05-2016 - 05:49
Bài này là bài quen thuộc anh ạ tuy nhiên cách giải của nó khá rối rắm
Trên mỗi hàng chọn ra số lớn nhất. Gọi số bé nhất trong các số đó là $a$
Trên mỗi hàng chọn ra số bé nhất. Gọi số lớn nhất trong các số đó là $b$
Trên mỗi cột chọn ra số lớn nhất. Gọi số bé nhất trong các số đó là $c$
Trên mỗi cột chọn ra số bé nhất. Gọi số lớn nhất trong các số đó là $d$
Trước hết ta chứng minh $c \geq b$
Thật vậy gọi $e$ là số nằm trên cột chứa $c$ và hàng chứa $b$
Khi đó theo cách gọi $c\geq e,e \geq b$ suy ra $c \geq b$
Tương tự $a \geq d$
TH1 : $a>b$
Gọi $x$ là một số bất kỳ nằm giữa $a$ và $b$
Khi đó dễ thấy hàng nào cũng phải chứa $x$ (Vì trên mỗi hàng $x$ đều không nhỏ hơn số bé nhất của hàng đó và không lớn hơn số lớn nhất của hàng đó)
Khi đó $x$ lặp lại $n$ lần
TH2 :$a \leq b$
-Nếu $c>d$ thì xét tương tự TH1
-Nếu $c \leq d$
Theo trên ta có: $c \geq b \geq a \geq d$
Từ đây dễ suy ra $a=b=c=d$ suy ra cả $n^2$ số trên bảng đều bằng nhau
Vậy tồn tại một số xuất hiện ít nhất $n$ lần
Mình nghĩ không ổn phần trường hợp 1.
Giả sử tồn tại $a>b+3$
Thì tồn tại x sao cho $a>x>b+2$
Nếu chọn hàng có số lớn nhất là $b+2$ và số nhỏ nhất là $b$ thì không thoả mãn cách giải của bạn là với $x$ bất kì nằm giữa $a, b$ thì hàng nào cũng phải chứa $x$
#4
Đã gửi 11-05-2016 - 11:04
Mình nghĩ không ổn phần trường hợp 1.
Giả sử tồn tại $a>b+3$
Thì tồn tại x sao cho $a>x>b+2$
Nếu chọn hàng có số lớn nhất là $b+2$ và số nhỏ nhất là $b$ thì không thoả mãn cách giải của bạn là với $x$ bất kì nằm giữa $a, b$ thì hàng nào cũng phải chứa $x$
MÌnh không hiểu bạn đang nói gì
Mình đang gọi số nhỏ nhất trong các số lớn nhất của mỗi hàng là $a$(Tức là mỗi hàng chọn ra số nhỏ nhất có $n$ số như vậy. $a$ là số nhỏ nhất trong các số đó). Khi đó số lớn nhất của mỗi hàng đều >a mà làm gì có hàng nào có số lớn nhất là $b+2$
- thinhrost1 yêu thích
#5
Đã gửi 13-05-2016 - 22:28
Bài này là bài quen thuộc anh ạ tuy nhiên cách giải của nó khá rối rắm
Trên mỗi hàng chọn ra số lớn nhất. Gọi số bé nhất trong các số đó là $a$
Trên mỗi hàng chọn ra số bé nhất. Gọi số lớn nhất trong các số đó là $b$
Trên mỗi cột chọn ra số lớn nhất. Gọi số bé nhất trong các số đó là $c$
Trên mỗi cột chọn ra số bé nhất. Gọi số lớn nhất trong các số đó là $d$
Trước hết ta chứng minh $c \geq b$
Thật vậy gọi $e$ là số nằm trên cột chứa $c$ và hàng chứa $b$
Khi đó theo cách gọi $c\geq e,e \geq b$ suy ra $c \geq b$
Tương tự $a \geq d$
TH1 : $a>b$
Gọi $x$ là một số bất kỳ nằm giữa $a$ và $b$
Khi đó dễ thấy hàng nào cũng phải chứa $x$ (Vì trên mỗi hàng $x$ đều không nhỏ hơn số bé nhất của hàng đó và không lớn hơn số lớn nhất của hàng đó)
Khi đó $x$ lặp lại $n$ lần
TH2 :$a \leq b$$n$
-Nếu $c>d$ thì xét tương tự TH1
-Nếu $c \leq d$
Theo trên ta có: $c \geq b \geq a \geq d$
Từ đây dễ suy ra $a=b=c=d$ suy ra cả $n^2$ số trên bảng đều bằng nhau
Vậy tồn tại một số xuất hiện ít nhất $n$ lần
Mình không chắc lắm về cách của bạn vì có cả đống trường hợp các số trên bảng không bằng nhau mà vẫn thoả mãn điều kiện đề bài. Ví dụ như có duy nhất 1 số 2 và các số còn lại đều là 1. Sau đây là cách giải của mình:
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
Bài viết đã được chỉnh sửa nội dung bởi JUV: 19-05-2016 - 11:57
- nhungvienkimcuong, Lareadx và nguyenhaan2209 thích
0 người đang xem chủ đề
0 thành viên, 0 khách, 0 thành viên ẩn danh