Разбиение доски на части

Сначала докажем, что жук короед может действовать так, чтобы не допустить появления более развившихся деревьев. Раскрасим клетки доски в два цвета как на рисунке. Заметим, что садовник каждым своим ходом увеличивает высоту не более деревьев, стоящих на черных клетках. Тогда жук будет ходить в те же самые черные клетки ответным ходом. Тогда развившиеся деревья могут возникнуть только на белых клетках, то есть их не более

Теперь докажем, что садовник всегда сможет вырастить хотя бы развившихся деревьев. Разобьем доску на квадраты Пусть садовник по очереди сходит в центр каждого из этих квадратов по раз. Предположим, что, если некоторое фиксированное дерево не стало развившимя, то жук ходил в это дерево не менее раз. Поскольку садовник всего сделал ходов, жук также сделал такое же количество ходов, то есть сходил в клеток. С другой стороны, если он смог помешать садовнику сделать деревьев развивмися, то он сделал не менее хода в клетки. Выбрав получаем, что — противоречие. Значит, садовник может сделать хотя развившихся деревьев.