2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Два игрока и куча камней
Сообщение06.03.2016, 12:32 


06/03/16

11
Два игрока по очереди берут от одного до 13 камней из кучи, содержащей в начале 2004
камня. Повторять ход, только что сделанный другим игроком, нельзя. Проигрывает не имеющий
хода. Кто выиграет при правильной игре?
Соображения: во-первых я пытался смотреть все это дело по модулю 14, но по четному модулю плохо смотреть, поскольку противник походит половину от этого модуля, и ваша стратегия рушится. Далее я пытался расставить выигрышные и проигрышные ходы, но поняв, что там не образуется закономерности, отказался от этой идеи. Мне кажется, что все-таки модуль 15 должен подойти, но пока что я не очень понимаю как отвечать первому на некоторые ходы второго (а именно, 1) Сразу скажу, что подбираю стратегию для первого.
Какие предложения, друзья?

 Профиль  
                  
 
 Re: два игрока...
Сообщение07.03.2016, 00:50 
Заслуженный участник


10/01/16
2318
kfkfkf
ВСЕ Ваши соображения - правильные!
(И про 14, и про 15...). Но задачка -тяжеловата....
Понятно, что ничего иного, кроме метода выигрышных позиций, здесь не прокатит.
Что будет позицией: пара (кол-во камней, последний ход врага).
Поначалу Победные позиции (т.е., те, в которых начинающий проигрывает) ищутся легко (но непонятно):
это $(a,a)$, где $a=1,3,4,5,7,9,11,12,13$. Но потом идет странная (14,7), и , наконец, супер-позиция $(15, \ast)$. Потом опять что-то неясное, а затем супер $(29, \ast)$ (вот они, и 14, и 15). Следующий супер - 44, и, наверное, следующий -58... Ну вот, это и докажем: супер-позицииями $(x, \ast)$ будут те, для которых $x=29n$ и $x=29n + 15$. Поехали!
Пусть в куче $29n$ камней, $n> 0 $. Будем дополнять ход врага до 14 (и загоним его во второй супер). Единственно, когда у нас будет проблема - это если враг возьмет 7 камней. На это мы ответим 11, после чего ходы 1-10 дополним до 11 (итого взято $11+11+7 = 29$, попали в супер-1), а на ходы 12-13 дополним до 25 (будет взято $7+11+25=43 = 29+14$, попали в супер-2).
Если в куче $29n + 15$ камней: дополнять будем до 15. Проблем нет - за исключением гадкого хода 1 :D . На это мы ответим 7, и затем на ходы 1-6 дополним до 7 (взято $1 + 7 +7 =15$, как и хотели), а на ходы 8-13 дополним до 21 (взято $1+7 + 21 = 29$). Уффф.
Поскольку $2004 = 29\cdot 69 +3$ , первый выигрывает ходом "3".

 Профиль  
                  
 
 Re: Два игрока и куча камней
Сообщение07.03.2016, 16:50 


06/03/16

11
Спасибо большое! Решение понятно! я тоже пробовал смотреть по модулю 29, но не получалось, потому что упустил, что при ходе 7-11-?: ? не может быть равен 11...

 Профиль  
                  
 
 Re: Два игрока и куча камней
Сообщение10.03.2016, 17:51 


20/03/14
12041
 !  В связи с созданием клона в период временной блокировки, блокировка kfkfkf переходит в постоянную. Сообщения клона удалены.

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

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



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

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


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

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