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

[phuocdinh1999]

Cho hình vuông đơn vị $2n*2n$. Người ta tô màu $3n$ ô bất kỳ của hình vuông. Chứng minh luôn chọn được $n$ hàng và $n$ cột sao cho các hàng và cột đó chứa tất cả $3n$ ô đã tô.

Bài viết đã được chỉnh sửa nội dung bởi phuocdinh1999: 04-07-2014 - 09:17

[dshung1997]

Cho hình vuông đơn vị $2n*2n$. Người ta tô màu $3n$ ô bất kỳ của hình vuông. Chứng minh luôn chọn được $n$ hàng và $n$ cột sao cho các hàng và cột đó chứa tất cả $3n$ ô đã tô.

Cách làm của mình thế này

Từ $2n$ đã cho, chọn $n$ hàng có 'số ô được tô màu' nhiều nhất. Còn lại $n$ hàng. Ta chứng minh sô ô đc tô màu còn lại ( nghĩa là k nằm trên $n$ hàng đã chọn ) $\leq n$. 

Giả sử số ô đc tô màu còn lại $\geq n+1$ mà còn lại $n$ hàng k được chọn.Theo nguyên lí Dirichlet thì có ít nhất 1 hàng chứa ít nhất 2 ô đc tô màu. Theo cách chọn ở trên thì các hàng phải có nhiều ô đc tô màu nhất nên số ô trong $n$ hàng được chọn phải $\geq 2$
Khi đó tổng tất cả các ô được tô màu $\geq (2n+(n+1))$ hay $> 3n$. Vô lí

Khi đó ta có điều giả sử sai . Suy ra số ô đc tô màu còn lại $\leq n$. Đương nhiên nằm trên $n$ cột 

Bài viết đã được chỉnh sửa nội dung bởi dshung1997: 18-07-2014 - 11:01