В стране некоторые пары городов соединены дорогами, которые не пересекаются вне городов. В каждом городе установлена табличка, на которой указана минимальная длина маршрута, выходящего из этого города и проходящего по всем остальным городам страны (маршрут может проходить по некоторым городам больше одного раза и не обязан возвращаться в исходный город). Докажите, что любые два числа на табличках отличаются не более чем в полтора раза.

   Решение

Тема:    [ Выигрышные и проигрышные позиции ]

Сложность: 3 Классы: 7,8,9

Прислать комментарий

Условие

В нижнем левом углу шахматной доски 8 на 8 стоит фишка. Двое по очереди передвигают её на одну клетку вверх, вправо или вправо-вверх по диагонали.  Выигрывает тот, кто поставит фишку в правый верхний угол. Кто победит при правильной игре?

Ответ

Назовем клетку доски выигрышной, если игрок, который ходит из этой клетки, выигрывает при правильной игре. Остальные клетки назовем проигрышными.
  Будем обозначать выигрышные клетки знаком "+", а проигрышные - знаком "-". Начнем заполнять доску. Клетки g7, g8 и h7 - очевидно, выигрышные, так как из них можно первым же ходом попасть в h8. Далее, клетки f8 и h6 - проигрышные, потому что из них можно попасть только в выигрышные клетки. Продолжая таким образом заполнять доску, увидим, что в клетке a1 стоит "+". Значит, при правилльной игре побеждает первый игрок.

Источники и прецеденты использования