|
|
 |
Условие
В левой нижней клетке доски 100×100 стоит фишка. Чередуя горизонтальные и вертикальные ходы в соседнюю по стороне клетку (первый ход горизонтальный), она дошла сначала до левой верхней клетки, а потом до правой верхней. Докажите, что найдутся две такие клетки A и B, что фишка не менее двух раз делала ход из A
в B.
Решение
Раскрасим клетки в шахматном порядке так, что левая нижняя клетка X чёрная. Тогда левая верхняя Y белая. Из чёрной клетки X делается горизонтальный ход, следующий ход – из белой вертикально, потом – снова из чёрной горизонтально и так далее, чередуясь. Это значит, что из чёрной клетки фишка всегда выходит горизонтально, а из белой – вертикально. В частности, в Y фишка попала горизонтальным ходом.
Пусть одинаковых ходов не было. Тогда никакую сторону клетки фишка не может пересечь дважды: в том же направлении – в силу предположения, а в противоположном – в силу указанного выше чередования.
Поскольку пройденную сторону клетки снова проходить нельзя, будем "строить" вдоль неё стену. Очевидно, стены образуют связное множество. Когда фишка доберётся до Y, стены соединят нижний и верхний края доски. Вся доска разобьётся стенами на области, причём Y и правая верхняя клетка Z окажутся в разных областях. Следовательно, из Y в Z фишка пройти не сможет. Противоречие.
Замечания
5 баллов
