1863
358
467
всего задач:
всего разделов:
активных пользователей:
  Login: (регистрация)
  Пароль:
    

30 мартра 2005

Форумы снова функционируют.

21 декабря 2004

Видимо в связи с обнаруженными дырами в phpBB, форум был взломан, а через него взломано и всё остальное содержимое ceemat.ru. Всё кроме форума восстановлено, ведется дискуссия по поводу его сохранения.
Приносим извинения за неудобства.

29 сентября 2004

Форум обновился до версии 2.0.10

15 мая 2004

Новый раздел: "Программирование"

16 апреля 2004 года

Задачи Ярославского турнира математических боев — 124 задачи с решениями.

29 марта 2004

Таллинская викторина: занимательные вопросы и задачи для увлеченных химией.

Rambler's Top100

Костромской ЦДООШ СУНЦ МГУ - Школа им. А. Н. Колмогорова.\r\nОфициальный сайт

Весенний тур. Тренировочный вариант. 8-9 класс (5)

Итог подводился по трем задачам, по которым достигнуты наилучшие результаты.

Стоимость задач
Номер задачи 1 2 3 4 5
Баллы 4 4 4 5 5

Двое играющих по очереди красят стороны n-угольника. Первый может покрасить сторону, которая граничит с 0 или 2 покрашенными сторонами, второй — сторону, которая граничит с одной покрашенной стороной. Проигрывает тот, кто не может сделать хода. При каких n второй может выиграть независимо от игры первого?

Ответ: при n > 4 и n = 4.

Докажем, что первый игрок сможет выиграть при любых n, больших 4.

Будем называть дырой ломаную из нескольких неокрашенных сторон, идущих подряд. После первого хода n - 1 неокрашенных сторон образуют дыру. Заметим, что по условию второй игрок не сможет уменьшить количество дыр. Иначе, он бы покрасил сторону, которая граничит с двумя покрашенными. А по правилам, он этого сделать не может.

Стратегия первого игрока: каждым ходом создавать новую дыру длиной 1, пока это возможно. (Заметим, что при n > 4 первый игрок уже на втором своем ходу обязательно создаст хотя бы одну дыру длины 1, то есть такие дыры обязательно будут.) Если он не может создать новую дыру длины 1, то неокрашенными остались несколько дыр длиной 1 и, быть может, дыра длины 2. Если такая дыра есть, то первый красит одну из маленьких дыр. Второму приходится покрасить сторону большой дыры, и после очередного хода первого игрока он проигрывает. Если же дыры длины 2 нет, то первый может покрасить любую дыру и второй снова проиграет.

Остается рассмотреть случаи n = 3 и n = 4.
При n = 3, очевидно, выигрывает первый игрок.
А при n = 4 при любой игре выигрывает второй.

 5 Декабря 2003     21:57 
Раздел каталога :: Ссылка на задачу