Олимпиада имени Леонарда Эйлера 2017-2018 учебный год, II тур заключительного этапа

Из клетчатой доски размером $70 \times 70$ вырезали 2018 клеток. Докажите, что доска распалась не более чем на 2018 кусков. Два куска, не имеющие общих точек кроме вершин клеток, считаются не соединёнными друг с другом. ( И. Рубанов )

Комментарий/решение

Комментарии от администратора Комментарии от администратора №1.    
Решение. Нетрудно построить цикл, проходящий по разу через все клетки доски $70 \times 70$ так, что соседние клетки в нем имеют общую сторону: можно, например, пройти всю первую вертикаль от нижней клетки до верхней, потом ходить по вертикалям «змейкой» от верхней горизонтали до второй снизу и обратно, а по последней вертикали вернуться на первую горизонталь и по ней — в исходную клетку. «Расклеим» все общие стороны клеток на доске, кроме общих сторон между соседними клетками нашего цикла. Даже после этого 2018 выброшенных клеток будут разбивать этот цикл не более чем на 2018 частей, а при обратной склейке цикла в доску число частей не увеличится.