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