2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Красим точки на окружности
Сообщение23.04.2018, 18:59 
Модератор
Аватара пользователя


11/01/06
5660
На окружности расположены $n$ изначально непокрашенных точек. Два игрока по очереди красят по одной ранее непокрашенной точке в красный (первый игрок) и синий (второй игрок) цвета.
Игра заканчивается, когда все точки покрашены. Пусть $r$ - максимальное количество подряд идущих красных точек, $b$ - максимальное количество подряд идущих синих точек.
Первый игрок выигрывает, если $r>b$, второй - если $r<b$.

Докажите, что если $n$ нечётно, то у первого игрока есть выигрышная стратегия.
Если же $n$ чётно, то выигрышной стратегии нет ни у кого из игроков.

(источник задачи)

 Профиль  
                  
 
 Re: Красим точки на окружности
Сообщение23.04.2018, 22:45 


01/11/14
195
Ответ удалил, т. к. невнимательно прочитал условие. Придется думать...

 Профиль  
                  
 
 Re: Красим точки на окружности
Сообщение23.04.2018, 23:12 


20/04/10
1776
В случае нечётного $n$ выигрышная стратегия для первого такая: для удобства пронумеруем точки от 1 до $n$ и пусть первый ход первого - это закрашивание точки 1. Если второй игрок закрасил точку 2, то первому игроку вторым ходом нужно закрасить точку $n-1$, т.е. которая стоит через одну от закрашенной на первом ходе (это даст потенциальную возможность на следующем шаге собрать три точки подряд). Если второй продолжит увеличивать число своих подряд закрашенных (т.е. закрасит 3), то этим следует заняться и первому игроку (закрашивает $n$), ведь последний ход будет за ним и он победит. Если второй поставит свой цвет в точку $n$, тогда первый ходит $n-3$. Если такое поведение игроков сохранится до конца игры, то первый победит со счётом 2:1. Другие отклонения от этой схемы (например, когда второй блокирует своими точками возможность наращивать количество подряд идущих точек первого) приведут к тому, что первый игрок как минимум будет иметь 3 очка, а второй по крайней мере на одно меньше. И все дальнейшие попытки второго догнать первого, будут блокироваться первым.

 Профиль  
                  
 
 Re: Красим точки на окружности
Сообщение24.04.2018, 00:44 


01/11/14
195
Для четных n:
Ничейная стратегия 2-го игрока: после каждого хода 1-го игрока закрашивать противоположную точку.
Ничейная стратегия 1-го игрока: после каждого хода 2-го игрока закрашивать противоположную точку, если она не закрашена; в противном случае закрашивать любую незакрашенную точку.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 4 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group