Задание №178310: Турнир Ломоносова 2012
3. «Колонизаторы». На карте точками отмечены города, некото рые соединены дорогами. Играют двое. За ход каждый игрок захваты вает один город, который не был никем захвачен ранее. Нельзя захваты вать город, соединённый дорогой с городом противника. Проигрывает тот, кто не сможет сделать свой ход по правилам игры. Кто — начинающий или его соперник — победит в этой игре, как бы ни играл его партнёр? а) Рассмотрите карту с 20-ю городами, показанную на рисунке: б) Рассмотрите карту с 20-ю городами, показанную на рисунке: в) Пусть n городов расположены в виде кольца, как показано на рисунке. Кто — начинающий или его соперник — победит в зависимости от n? n 1 n 7 − n 1 n 1 7 − 6 1 2 6 2 5 4 3 5 4 3 Карта к пункту «в». Карта к пункту «г». г) Пусть 2n городов расположены в виде двойного кольца, как пока зано на рисунке. Кто — начинающий или его соперник — победит в зависимости от n? 23
Что проверяет это задание
Задание относится к теме «Турнир Ломоносова 2012». Для решения понадобятся:
- анализ условия
- выбор формулы
- проверка вычислений
Источник: Турнир имени М. В. Ломоносова — официальный архив · 2012
Качество материала
Показываем, из чего состоит страница и можно ли проверить материал по первоисточнику.
Последняя проверка решения:
Происхождение задания
- Банк заданий
- Турнир имени М. В. Ломоносова — официальный архив
- Организатор
- Редакция «Я сам решу»
- Год материала
- 2012
- Материалы
- 1 файл
Связанные понятия
План самостоятельного решения
- Перепишите известные данные и отдельно сформулируйте, что требуется найти или доказать.
- Свяжите условие с темой «Турнир Ломоносова 2012» и выберите подходящее правило, формулу или способ рассуждения.
- Запишите промежуточные шаги: это помогает заметить потерянный знак, случай или логический переход.
- Сверьте результат со всеми ограничениями условия и только затем откройте подробный разбор.
Ориентировочное время: 15 минут.
Закрепить тему
После разбора попробуйте решить ещё десять заданий по предмету «Математика». Вариант формируется заново, а ответы можно сразу проверить.
Решение по шагам
3. «Колонизаторы».
a) Победит второй игрок, отвечая
симметрично относительно центра сим
метрии картинки. Очевидно, что у него
всегда будет ход, причём этот ход не нарушит правил, иначе бы правила
нарушал предыдущий ход соперника.
Подобные рассуждения применимы и в других пунктах этой задачи,
там, где рассматривается симметричная стратегия.
26
б) Победит начинающий. Он может
сначала захватить город, отмеченный
кружочком, а затем на каждый ход вто
рого отвечать симметрично относительно оси симметрии картинки.
в) При n = 2 победит первый, при чётном n > 2 победит второй — он
может отвечать симметрично первому относительно центра картинки.
При нечётном n победит первый игрок.
Докажем это индукцией по n.
Для n = 1 и n = 3 решение очевидно.
Пусть при n < 2k + 1 выигрышная стратегия за первого игрока най
дена. Рассмотрим n = 2k + 1. Первым ходом мы захватываем город № 1.
Пусть соперник сделал свой ход, захватив город № m. Можно считать3,
что 2 < m (cid:54) k. Тогда мы захватываем город № (2m 1).
−
Теперь захвачено 3 города
(на рисунке показаны кружоч 2k
2m+2
ками; цифрой в кружочке ука
2m+1 2k+1
зано, кто захватил этот город),
C
которые делят игровое поле на 2m 1 1
3 сектора: A, B и C. Незахвачен
2m 1 1 2
ные города на рисунке обозна −
чены жирными точками. Оче 2m 2 A 3
− B
редной ход — у второго игрока.
Сектора A и B имеют одина
k
ковую структуру, в каждом из 2 m 1
них имеется (m 2) незахвачен m + 1 m −
−
ных городов. Если второй игрок
делает какой-то ход в одном из этих секторов, первый тут же отвечает
аналогичным ходом в другом секторе, то есть захватывает город, распо
ложенный на таком же расстоянии от города № m, что и город, только
что захваченный соперником.
Что касается оставшейся части игрового поля, то, мысленно объеди
нив захваченные первым игроком города № 1 и № (2m 1), можно заме
−
тить, что сектор С эквивалентен исходной игре с количеством городов
n = 2(k m + 1) + 1 = (2k + 1) 2(m 1), где первым игроком уже сде
− − −
лан первый ход. Это число положительное, нечётное и меньшее 2k + 1.
Следовательно, здесь у первого игрока по предположению индукции
есть выигрышная стратегия.
3Если это не так, то достаточно поменять направление нумерации городов на
противоположное.
27
Таким образом, игра распалась на независимые фрагменты, в каж
дом из которых у первого игрока есть выигрышная стратегия. Следо
вательно, выигрышная стратегия также есть и в игре в целом.
г) При чётном n победит второй игрок. На каж
дый ход первого он может определить центрально
симметричный город и занять соответствующий
ему, но на другом кольце. n 1 n
7 −
При нечётном n победит начинающий. Первым 1
ходом он занимает любой город X, затем рассмат 6
2
ривает прямую l, проходящую через X и центр 5 4 3
кольца. Если теперь соперник занимает какой-то
город, первый игрок отражает его симметрично
относительно прямой l, но занимает не определён
ный таким образом город, а смежный с ним город на другом кольце.
Примечание. Игровое поле в этом случае можно представить себе
как цилиндр, на краях оснований которого друг над другом располо
жены города (одно из оснований соответствует внутреннему кольцу, а
другое — внешнему).
Соответственно, при чётном n ходы делаются симметрично относи
тельно центра цилиндра.
При нечётном n ходы делаются симметрично относительно прямой,
проходящей через центр цилиндра и середину дороги, соединяющей
город X и смежный с ним город на другом кольце (другом основа
нии цилиндра). По правилам игры второй игрок не может симметрично
ответить на первый ход первого игрока (эти города соединены доро
гой), и вынужден сделать какой-нибудь другой ход. В дальнейшем же
по правилам игры на все возможные ходы второго игрока возможны
симметричные ответы первого игрока.
Задания для конкурса по математическим играм предложили:
№ 1 — А. В. Шаповалов,
№ 2 — John Horton Conway (Принстон, США),
№ 3 — И. В. Раскина.
Тексты заданий и решений подготовили:
А. В. Хачатурян, В. А. Клепцын.
28
Критерии оценивания
За каждую задачу ставится от 0 до 20 баллов: сумма баллов за пункты
этой задачи или 20 баллов (если сумма по пунктам больше 20).
Если из решения видно, что школьник неправильно понимает усло
вия задачи (и само понятие стратегии) — за задачу ставится 0 баллов.
Используемые формулы
в) При n = 2 победит первый, при чётном n > 2 победит второй — онДля n = 1 и n = 3 решение очевидно.Рассмотрим n = 2k + 1.n = 2(k m + 1) + 1 = (2k + 1) 2(m 1), где первым игроком уже сде
Самопроверка после решения
- Я использовал все данные из условия и не добавил неподтверждённых предположений.
- Каждый переход в рассуждении объяснён правилом, формулой или ранее доказанным фактом.
- Ответ соответствует вопросу, а обозначения и единицы измерения записаны однозначно.
- Я сравнил свой ход решения с разбором и понял причину каждого отличия.
Типичные ошибки
- Не проверить область допустимых значений.
- Потерять знак при переносе или раскрытии скобок.
- Не выполнить обратную подстановку.