Задание №180813: Командная олимпиада 2024
Двое по очереди проводят ребра изначально пустого графа на n вершинах (n ⩾ 3). Проигрывает тот, после чьего хода в графе образуется нечетный цикл. При каких n выигрывает начинающий?
Что проверяет это задание
Задание относится к теме «Командная олимпиада 2024» и рассчитано на уровень 8 класса. Для решения понадобятся:
- анализ условия
- выбор формулы
- проверка вычислений
Источник: Турнир математических боёв и командная олимпиада МЦНМО — официальный архив · 2024
Качество материала
Показываем, из чего состоит страница и можно ли проверить материал по первоисточнику.
Последняя проверка решения:
Происхождение задания
- Банк заданий
- Турнир математических боёв и командная олимпиада МЦНМО — официальный архив
- Организатор
- МЦНМО
- Год материала
- 2024
- Материалы
- 1 файл
Связанные понятия
План самостоятельного решения
- Перепишите известные данные и отдельно сформулируйте, что требуется найти или доказать.
- Свяжите условие с темой «Командная олимпиада 2024» и выберите подходящее правило, формулу или способ рассуждения.
- Запишите промежуточные шаги: это помогает заметить потерянный знак, случай или логический переход.
- Сверьте результат со всеми ограничениями условия и только затем откройте подробный разбор.
Ориентировочное время: 15 минут.
Закрепить тему
После разбора попробуйте решить ещё десять заданий по предмету «Математика». Вариант формируется заново, а ответы можно сразу проверить.
Решение по шагам
Ответ: При n, дающих остаток 2 при делении на 4.
Решение. Пусть n – нечетно. Тогда второй каждым ходом уменьшает число
компонент связности, пока это возможно. Когда получается связный граф, он
двудольный, поскольку нечетных циклов нет. При этом в долях количества вер-
шин разной четности. Теперь любой ход может быть сделан только между до-
лями, иначе две вершины одной доли можно соединить как проведенным этим
ходом ребром, так и цепочкой других ребер в силу связности. А тогда нашелся
нечетный цикл. Следовательно, оставшаяся игра приведет к построению пол-
ного двудольного графа с четным числом ребер. В этой ситуации побеждает
второй игрок.
Пусть n – четно, но не делится на 4. В этом случае первый разбивает все вер-
шины на пары и соединяет две вершины одной пары. Если второй соединяет
вершины некоторой пары, то первый делает так же (их к моменту хода будет
доступно нечетное количество). Если второй соединяет две вершины из разных
пар, то первый соединяет парные к ним вершины. Если после этого получился
нечетный цикл, то он и до этого должен быть нечетный цикл.
Если n делится на 4, то второй после хода первого начинает действовать по
стратегии, аналогичной предыдущему случаю.
Канада, 2019
Самопроверка после решения
- Я использовал все данные из условия и не добавил неподтверждённых предположений.
- Каждый переход в рассуждении объяснён правилом, формулой или ранее доказанным фактом.
- Ответ соответствует вопросу, а обозначения и единицы измерения записаны однозначно.
- Я сравнил свой ход решения с разбором и понял причину каждого отличия.
Типичные ошибки
- Не проверить область допустимых значений.
- Потерять знак при переносе или раскрытии скобок.
- Не выполнить обратную подстановку.