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

[Strygwyr]

Cho một bảng kích thước $2n\times 2n$ ô vuông. Người ta đánh dấu $3n$ ô vuông bất kỳ của bảng. Chứng minh rằng có thể chọn ra $n$ hàng và $n$ cột của bảng sao cho các ô được đánh dấu đều nằm trên $n$ hàng hoặc $n$ cột này.

[ilovelife]

Cho một bảng kích thước $2n\times 2n$ ô vuông. Người ta đánh dấu $3n$ ô vuông bất kỳ của bảng. Chứng minh rằng có thể chọn ra $n$ hàng và $n$ cột của bảng sao cho các ô được đánh dấu đều nằm trên $n$ hàng hoặc $n$ cột này.

$KHTN$ thi thử đợt vừa rồi lấy bài này, mình có xem qua, có vẻ ta cần chứng minh, ta luôn chọn được $n$ hàng chứa tất cả $2n$ ô được đánh dấu và cũng chọn được $n$ cột chứa $2n$ ô được đánh dấu

Khi chọn như vậy thì $n$ điểm bị chọn $2$ lần ...

$\implies$ luôn chọn được $3n$ điểm được đánh dấu

[4869msnssk]

$KHTN$ thi thử đợt vừa rồi lấy bài này, mình có xem qua, có vẻ ta cần chứng minh, ta luôn chọn được $n$ hàng chứa tất cả $2n$ ô được đánh dấu và cũng chọn được $n$ cột chứa $2n$ ô được đánh dấu

Khi chọn như vậy thì $n$ điểm bị chọn $2$ lần ...

$\implies$ luôn chọn được $3n$ điểm được đánh dấu

mình không ra đc 

[ilovelife]

mình không ra đc 

Mình cũng chưa làm hẳn hoi, có gì mai mình làm (giờ đi ngủ) $A \rightarrow Z$ (nhưng chắc tí nữa là có người giải ngay ấy mà ). Hoặc là để cho chắc, bạn thử hỏi xem có ai cầm đáp án không, hoặc hỏi nguyenta98 ấy, hôm trước thử xem điểm có ai được $10$ không, hình như thấy mỗi bạn ấy

Bài viết đã được chỉnh sửa nội dung bởi ilovelife: 19-05-2013 - 21:13

[nguyenta98]

bài đó dễ mà,đầu tiên cậu chọn $n$ cột có số ô được đánh dấu là lớn nhất, khi đó ta cm số ô đánh dấu mà chưa nằm trong $n$ cột theo cách chọn trên $\le n$ thật vậy nếu số ô đánh dấu mà chưa được chọn $>n$ hay $\geq n+1$ thì do ta đã chọn $n$ cột nên còn $2n-n=n$ cột, $n$ cột đó chứa $\geq n+1$ ô đánh dấu theo nguyên lý dirichlet tồn tại một cột chứa hai ô đánh dấu $(1)$, mà ta theo cách chọn $n$ cột ban đầu có số ô đánh dấu lơn nhất nên mỗi cột đó $\geq 2$ ô (do $(1)$) từ đó số ô đánh dấu $\geq 2.n+(n+1)>3n$ mâu thuẫn, do đó số ô được đánh dấu chưa được chọn trong $n$ cột nhỏ hơn hoặc bằng $n$, chọn $n$ hàng chứa cả $n$ ô đó sẽ có đpcm