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 ] 

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



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

Сейчас этот форум просматривают: Shadow


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

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