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

[Zz Isaac Newton Zz]

Cho bảng hình chữ nhật kích thước $m\times n$( $m$ là hàng, $n$ là cột $m< n$ ). Đặt một số viên bi vào một số ô của bảng sao cho mỗi cột có ít nhất một viên bi. Chứng minh rằng có ít nhất hai viên bi mà hàng chứa nó có nhiều bi hơn cột chứa nó.

 

[JUV]

Với mỗi viên sỏi ở cột $i$, gán cho mỗi viên $1$ số $\frac{1}{t}$ với $t$ là số viên sỏi trên cột $i$. Tổng các số trên mỗi cột là $1$ nên tổng các số trên cả bảng là $n$. Vì $n\geq m+1$ nên hoặc tồn tại một hàng có tổng các số viết trên đó $\geq 2$ hoặc tồn tại $2$ hàng mà tổng các số trên mỗi hàng $> 1$. Trên một hàng có tổng các số $\geq 1$, chọn ra số lớn nhất $\frac{1}{k}$. Mỗi khác đều $\leq \frac{1}{k}$ và tổng các số trên hàng đó $> 1$ nên có nhiều hơn $k$ viên sỏi trên hàng đó. Vậy viên sỏi mang số lớn nhất đó là $1$ viên sỏi cần tìm. Nếu có $2$ hàng có tổng $> 1$ thì ta tìm được $2$ viên sỏi, nếu có $1$ hàng có tổng $\geq 2$ thì chọn ra số lớn nhất trong các số trên hàng là $a$. Lưu ý $a\leq 1$ nên tổng các số còn lại $\geq 1$ nên chọn được thêm số lớn thứ nhất trong các số còn lại là $\frac{1}{k}$, số viên sỏi trong hàng chứa nó $\geq k+1$(tính cả viên sỏi được chọn lúc đầu.) $\Rightarrow Q.E.D$

Bài viết đã được chỉnh sửa nội dung bởi JUV: 11-12-2016 - 08:21