$40$ cells were marked on an infinite chessboard. Is it always possible to find a rectangle that contains $20$ marked cells? M. Evdokimov
Problem
Source: Tournament of Towns 2020 oral p3 (15 March 2020)
Tags: combinatorics, combinatorial geometry, grid
30.05.2020 17:35
.
12.04.2021 16:44
Answer. $\boxed{\text{No.}}$ To see this, just colour $11\times 11$ all cells on the edges. Now notice that if we pick any rectangle that does not contain one edge of $11\times 11$ square, then that rectangle contains at most $19$ squares, therefore our rectangle must contain at least one of the edges of $11\times 11$ square, but now since edge contains $11$ marked cells and every new row that we add, does not change the parity (also we cannot cover the whole $11\times 11$ square), it is impossible to find a rectangle that contains $20$ marked cells. [asy][asy] size(6cm); for (int i=0; i<=10; ++i) { fill(shift(i,10)*unitsquare, grey); } for (int i=0; i<=10; ++i) { fill(shift(10,i)*unitsquare, grey); } for (int i=0; i<=10; ++i) { fill(shift(0,i)*unitsquare, grey); } for (int i=0; i<=10; ++i) { fill(shift(i,0)*unitsquare, grey); } for (int i=0; i<=10; ++i) { draw(shift(i,0)*unitsquare); } for (int i=0; i<=10; ++i) { draw(shift(i,1)*unitsquare); } for (int i=0; i<=10; ++i) { draw(shift(i,2)*unitsquare); } for (int i=0; i<=10; ++i) { draw(shift(i,3)*unitsquare); } for (int i=0; i<=10; ++i) { draw(shift(i,4)*unitsquare); } for (int i=0; i<=10; ++i) { draw(shift(i,5)*unitsquare); } for (int i=0; i<=10; ++i) { draw(shift(i,6)*unitsquare); } for (int i=0; i<=10; ++i) { draw(shift(i,7)*unitsquare); } for (int i=0; i<=10; ++i) { draw(shift(i,8)*unitsquare); } for (int i=0; i<=10; ++i) { draw(shift(i,9)*unitsquare); } for (int i=0; i<=10; ++i) { draw(shift(i,10)*unitsquare); } [/asy][/asy]