2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Игра с АСМ-олимпиады
Сообщение02.04.2011, 06:08 
Заслуженный участник


08/04/08
8562
Дана пустая лента из $n$ ячеек. Два игрока по очереди ставят в пустые ячейки крестики. Проигрывает тот, кто на очередном ходе не сможет не поставить крестик в ячейку рядом с уже заполненной ячейкой. При каких $n$ при правильной игре выигрывает первый (ну или второй).
Решения я не знаю.

(предыстория)

Лет 6 назад давали. Иногда на таких олимпиадах дают одну-две задачи, которые можно решить не составлением программы, а решить как задачи.. Правда почему-то жюри на такие решения смотрят как на непрофессиональные...
Эту задачу я решить тогда не смог.

 Профиль  
                  
 
 
Сообщение02.04.2011, 09:21 
Заслуженный участник


12/08/10
1680
Как-то непонятно. Уже первый ход сделать нельзя.

 Профиль  
                  
 
 
Сообщение02.04.2011, 10:02 
Заслуженный участник


08/04/08
8562
Почему? Первый ход всегда сделать можно.
Обозначу ленту с крестиками вектором $(0;0;0;0;0)$.
Примеры игры:
1. А: $(0;0;1;0;0)$
В: $(0;0;1;0;1)$
А: $(1;0;1;0;1)$
В: проиграл.

2. А: $(0;1;0;0;0)$
В: $(0;1;0;1;0)$
А: проиграл.

 Профиль  
                  
 
 Re: Игра с АСМ-олимпиады
Сообщение02.04.2011, 10:02 
Заслуженный участник


09/02/06
4401
Москва
Если я правильно понял, то Игрок может ставить крестик рядом с заполненной клеткой, если при этом у него есть возможность ставить крестик на клетке, не являющейся соседнем с заполненной ранее. Если такой возможности уже нет, то он проиграл.

 Профиль  
                  
 
 
Сообщение02.04.2011, 10:04 
Заслуженный участник


08/04/08
8562
Ой! Давайте проще скажу: кто поставил крестик рядом с заполненной клеткой, тот и проиграл :-)

 Профиль  
                  
 
 Re: Игра с АСМ-олимпиады
Сообщение02.04.2011, 10:06 
Заслуженный участник


09/02/06
4401
Москва
Так бы сразу написали. Иначе первое ваше условие скорее трактуется как я писал.

 Профиль  
                  
 
 
Сообщение02.04.2011, 10:08 
Заслуженный участник


08/04/08
8562
Прошу прощенья :oops: могу исправить

 Профиль  
                  
 
 Re:
Сообщение02.04.2011, 10:13 


16/06/10
199
А если условие переформулировать, ведь после того, как поставили крестик, его и соседние с ним клетки можно вырезать из ленты...

В начале игры на столе есть одна кучка с $n$ предметами. Игрок на своём ходе выбирает кучку, берет из неё не более трёх предметов, а оставшиеся в ней предметы делит на две кучки. Выигрывает тот, кто взял последний предмет со стола.

 Профиль  
                  
 
 
Сообщение02.04.2011, 11:25 
Заслуженный участник


12/08/10
1680
При нечетном n первый выигрывает поставив в середину а потом по симметрии.

 Профиль  
                  
 
 Re: Игра с АСМ-олимпиады
Сообщение02.04.2011, 14:47 
Заслуженный участник


09/02/06
4401
Москва
При четном $n>2$ выигрывает второй, отвечая ходу первого на $i$ ходом $i\pm \frac n2$, так же по симметрии.

 Профиль  
                  
 
 Re: Игра с АСМ-олимпиады
Сообщение02.04.2011, 15:05 
Заслуженный участник


08/04/08
8562
Руст писал(а):
При четном $n>2$ выигрывает второй, отвечая ходу первого на $i$ ходом $i\pm \frac n2$, так же по симметрии.

1: $(0;0;1;0;0;0)$
2: $(0;0;1;0;0;1)$
1: $(1;0;1;0;0;1)$
2: $(1;0;1;1;0;1)$ - проиграл.
Или я неверно понял Ваш ответ? :roll:

 Профиль  
                  
 
 
Сообщение02.04.2011, 15:19 
Заслуженный участник


02/08/10
629
При n=2 побеждает первый.
При n=4 второй.
При n=6 первый (ставит крестик в крайнюю клетку, сводя ситуацию к случаю n=4, где он уже будет вторым)
При n=8 первый (крест в четвёртую клетку)

 Профиль  
                  
 
 Re:
Сообщение02.04.2011, 16:18 


02/09/10
76
MrDindows в сообщении #430400 писал(а):
При n=8 первый (крест в четвёртую клетку)

А второй - в восьмую?

 Профиль  
                  
 
 
Сообщение02.04.2011, 17:06 


24/01/11
207
Да, 8-ая прогрышная. Вообще, если верить моей программе, то среди первых двухсот n проигрышные:
4, 8, 14, 20, 24, 28, 34, 38, 42, 54, 58, 62, 72, 76, 88, 92, 96, 106, 110, 122, 126, 130, 140, 144, 156, 160, 164, 174, 178, 190, 194, 198
А закономерность такова (по крайней мере на первых 20000): если рассматривать, насколько отличаются соседние плохие n,
то получится последовательность с предпериодом «4 4 6 6 4 4 6 4 4» и периодом «12 4 4 10 4».
Осталось лишь доказать эту закономерность по индукции.

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

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



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

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


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

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