Логика или математика?

Небольшая предыстория.
Как-то давным-давно в Ялте, на Массандровском пляже, интеллигентного вида жулик (а они все, в основном, такие) предложил скоротать время забавной игрой...
Требуется всего пятнадцать спичек, раскладываются они на три кучки- три, пять, семь. Играют вдвоём, начинает любой.
Можно брать одним ходом любое количество спичек из единственной кучки. Проигрывает тот, кто берёт последнюю.
Из далёкого детства я помнил подобные загадки из "Занимательной математики", там были даже какие-то выкладки, но очередь хода точно имела значение. Тогда он уточнил, что проигравший первую, выбирает очередь хода.
Поиграли пол-часика бесплатно (с переменным успехом) и по рублю (в одну калитку) :|
Дома я попытался подвести теоретическую базу- не хватило мозгов. Может быть, кто-нибудь из здесь присутствующих, с университетским образованием и(или) развитой логикой сможет это сделать.
Тогда я достиг некоторых практических успехов. На обратной дороге купе попалось любознательное и про пиво и закусь я уже не волновался! Деньги, потраченные на пляже, в течение суток окупились несколько раз...
Но неумолимые годы...
И я забыл алгоритм выигрыша, да и он не был подтверждён теоретически!
Итак.
Кто хочет бесплатного пива в дороге? Тренируемся... Спички лежат

!!! !!!!! !!!!!!!

Если Вы готовы сыграть- выберите начинающего и сделайте ход (если Вы первый)

Теоретики с объяснением этой лабуды приветствуются!

Не теоретик, но попробую.

Первый игрок выигрывает. Берем количество спичек в каждой кучке, переводим в двоичную форму: т.е. 011, 101, 111. Складываем отдельные цифры без переноса разрядов (сложение по модулю 2, XOR то бишь): 011 ⊕ 101 ⊕ 111 = 001. Несложно доказать, что если сумма по модулю 2 равна нулю, то привести ее снова к нулю за один ход нельзя (любой ход меняет чётность по крайней мере в одном столбике). Оттуда и стратегия: каждым ходом приводим сумму к нулю.

Работает к любым количеством спичек, но результат зависит, конечно, от начальной суммы: если вместо 3-5-7 брать, скажем, 3-5-6, то первый игрок проигрывает.

P.S. Выбор хода в общем случае чуть-чуть сложнее чем я думал. Сумму (назовем ее S) действительно надо приводить к нулю, но по следующему алгоритму: добавляем S к количеству спичек Х в каждой кучке (все ещё по модулю 2), выбираем любую кучку где Х⊕S < Х, и берём оттуда Х⊕S спичек.

В данном случае, 011⊕001 = 010, значит можно из первой. Берём 010 = 2 спички, остается 1,3,5.

Рад, что Вы откликнулись!
Я пока судорожно вспоминаю двоичную систему и сложение по модулям :|
Но увидел Ваше сообщение... Из какой позиции Вы получили 1-3-5 одним ходом?
Берём любое кол-во из одной кучки!

Анализировал эту фигню когда-то давно. Шел от эндшпиля. Есть типовые выигрывающие позиции. Их штук 10 или меньше. 1-1-1, 1-2-3, 2-2, 3-3 , 4-4 и т.д. Этого вполне достаточно, чтобы обыграть лошка при любой очередности хода. При углубленном 5-минутном изучении алгоритм выигрыша выводится легко.
Да, начальная позиция была проще, по-моему, 2-3-4. Но это не имеет большого значения..

Так же с конца, шёл и я!
Методом тыка! Но где теория?
Вариант 1-1-1 (теоретически выигранный) не вписывается в теорию Влада?
Или я неправильно складываю?

Лошка- да! А ну как он ТИПО моего ялтинского учителя?

Имеет! Возможностью маневра.
Первый ход из Вашей начальной с переходом в 2-3-1 ( а другого победного нет!) выучит за пять розыгрышей и "дремучий лошара"...
Хотелось бы подвести теоретическую базу для увеличения количества спичек, в случае если вы напоролись на профи!
И 3-5-7 он играет на автопилоте :|

Нет. Я, вероятно, ошибся. Начальная не 2-3-4, а 4-4-4. Точно помню, что была выигрывающая позиция 4-4. Тут помню, а тут не помню...
Обострение старческого силикоза)))

Извиняюсь, сам не знаю откуда 1-3-5 взял. К тому же, неправильно прочитал условия — алгоритм привел для игры, в которой взятие последней спички выигрывает. Да и сам алгоритм переврал, вспомнил его по кускам и поленился проверить на бумаге. В том варианте игры, который я попытался описать (взятие последней спички выигрывает), кучки надо приводить к Х⊕S: то есть для 3-5-7, берем 3-2=1 из первой, получаем 2-5-7.

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

Уважаемый Жак!
Не хотелось бы тревожить лишний раз Ваш "старческий силикоз"...
Но истина дороже!
Начальная 4-4-4, ход лоха.
Забирает полностью одну кучку, осталось 4-4, про которые Вы пишете, наверное справедливо, с победой!
Включаем мозги, не можем же мы выставлять лоху пиво!

- Доктор, у меня провалы в памяти.
- И как часто?
- Что часто?
- Провалы.
- Какие провалы?

С годами начинаешь все больше ценить то, что еще в состоянии удивить и вызвать эмоции.
Я, правда, забыл! Удивлен..

Уважаемый Влад!
Пока математические выкладки не понял, но рискну утверждать, что предложенный ход выигрывает и в моей игре (когда взятие последней проигрывает).
Возможно ли такое с математической точки зрения? :|

Как ни странно, так и получается. Начальная стратегия действительно та же самая: берем любую кучку в которой Х⊕S < Х, оставляем в ней Х⊕S спичек, получаем ноль в сумме по модулю 2. Останавливаемся в тот момент, когда остается только одна кучка с двумя спичками или больше. Так как в этой ситуации S не равен нулю, это может случиться только после хода противника. Теперь просто берем либо Х либо Х-1 спичек из наибольшей кучки, оставляя нечетное количество кучек по одной спичке, и теперь все ходы форсированны.

На практике получается так (за Б хожу как попало, не уверен что существует какая-то разумная стратегия за второго игрока):

Расклад: 3,5,7
A: 2,5,7
Б: 2,5,1
A: 2,3,1
Б: 2,1,1
A: Cтоп, переходим в эндшпиль. Оставляем нечетное число единиц: 1,1,1.
Б: 0,1,1, и проигрывает.

Ну вот мы и с теорией!
Действительно, странный факт, что в обе игры выигрывает начинающий!
Но если в Вашу (с последней выигрывающей)- это чистая математика, то в моей (с последней проигрывающей)- финт ушами при переходе в эндшпиль позволяет её отнести к логически-математическим? :blush:

Неверно.
Например, если взявший последнюю выигрывает, то позиция (1 1) проигрышна для начинающего.
Аналогично, если взявший последнюю проигрывает, то позиция (1 1 1) проигрышна для начинающего.
Тут, по сути, все сводится к тому, равен ли xor всех кучек нулю

Вот теория:
http://ru.wikipedia.org/wiki/Ним_(игра)

Спасибо за ссылку!
Теперь я и название этой бодяги знаю.
Анонимус, проверьте, всё верно!
В позиции 3-5-7 выигрывает начинающий и в случае прямого НИМа, и в случае МИЗЕРа.

кто-нибудь головоломку Эйнштейна решал? (сам он утверждал, что её могут решить только 2% людей, правда в уме, по моему в уме её вообще невозможно решить)
головоломка Эйнштейна[u]http://www.softportal.com/get-4222-einstein-golovolomka-ejnshtejna.html[/u]

Я, если честно, слукавил, что забыл алгоритм выигрыша 3-5-7 со своего хода.
Но, согласитесь, странновато будет в купе складывать двоичные на бумажке или в голове... :|
Лучше вызубрить, как таблицу Налимова. А в случае опытного противника (и ничейного счёта) предложить ему в какой-то момент сменить пластинку (последняя выигрывает)
С большой вероятностью он решит, что начинающий проигрывает и отдаст первый ход вам...
И в случае

Вы опять с пивом!
Маньякам можно выучить и более крупные расклады, но с такими не хотелось бы ехать в одном купе
Осталось купить билет на югА, едой и питьём мы обеспечены!
Хотя, если у вас знакомая и азартная билетёрша, можно и билет выиграть :kissing:
Всем приятного отдыха!

З.Ы. Билеты берём в разные купе!

Не спорю, алгоритм хороший, проверенный! Но не имеет отношения к настольным играм... :|
Предлагаю такой: в левую - бумажник, правой - за волосы и об стол.
Правила настольных соблюдены

Ну вот и физподготовку разработали. Пока он там XOR вычисляет, мы его за волосы и апстол.

Вот и теоретики подтянулись...
Физкульт-привет!
Г-н Полоудин советовал по поводу новых настольных игр обращаться в РШФ
http://kasparovchess.crestbook.com/viewtopic.php?pid=411698#p411698
Влад, может и мы рискнём соавторами, а Василия возьмём отбиваться от рэкетиров? :|

Я имел в виду общий случай, который как бы и логично анализировать вместо конкретных 3-5-7.

Простите, но Вы имели ввиду не общий случай, а конкретный глубокий эндшпиль...
В любом случае, спасибо за участие!

Эйнштейн отдыхает, люди зарабатывают пиво!
Кстати, ссылка не работает :kissing:

Зачем РШФ, надо прямо к Илюмжинову, в рамках рывка к рынку. Будет классика, быстрые, блиц, ну и Ним с мордобоем, с последующим матчем на звание абсолютного чемпиона. Чтобы долго не думали, будем выдавать только по одной спичке. И пусть спонсоры решат.

А Василий будет бумажник держать в левой руке, а правой Данайлова отпихивать. Данайлов полезет за бумажником, а Василий отпихнет. Не лезь, мол, Данайлов, за бумажником. А то Топалову вообще спичек не дадим.

Один умный профессор однажды в университете задал студенту интересный вопрос.

Профессор: Бог хороший?
Студент: Да.
Профессор: А Дьявол хороший?
...
Студент: Нет.
Профессор: Верно. Скажи мне, сынок, существует ли на Земле зло?
Студент: Да.
Профессор: Зло повсюду, не так ли? И Бог создал все, верно?
Студент: Да.
Профессор: Так кто создал зло?
Студент: ...
Профессор: На планете есть уродство, наглость, болезни, невежество?
Все это есть, верно?
Студент: Да, сэр.
Профессор: Так кто их создал?
Студент: ...
Профессор: Наука утверждает, что у человека есть 5 чувств, чтобы исследовать мир вокруг.
Скажи мне, сынок, ты когда-нибудь видел Бога?
Студент: Нет, сэр.
Профессор: Скажи нам, ты слышал Бога?
Студент: Нет, сэр.
Профессор: Ты когда-нибудь ощущал Бога? Пробовал его на вкус? Нюхал его?
Студент: Боюсь, что нет, сэр.
Профессор: И ты до сих пор в него веришь?
Студент: Да.
Профессор: Исходя из полученных выводов, наука может утверждать, что Бога нет.
Ты можешь что-то противопоставить этому?
Студент: Нет, профессор. У меня есть только вера.
Профессор: Вот именно. Вера - это главная проблема науки.
Студент: Профессор, холод существует?
Профессор: Что за вопрос? Конечно, существует. Тебе никогда не было холодно?
(Студенты засмеялись над вопросом молодого человека)
Студент: На самом деле, сэр, холода не существует. В соответствии с законами физики, то,
что мы считаем холодом в действительности является отсутствием тепла. Человек или предмет можно
изучить на предмет того, имеет ли он или передает энергию. Абсолютный ноль (-460 градусов по Фаренгейту)
есть полное отсутствие тепла. Вся материя становится инертной и неспособной реагировать при этой
температуре. Холода не существует. Мы создали это слово для описания того, что мы чувствуем при отсутствии тепла.
(В аудитории повисла тишина)
Студент: Профессор, темнота существует?
Профессор: Конечно, существует. Что такое ночь, если не темнота?
Студент: Вы опять неправы, сэр. Темноты также не существует. Темнота в действительности есть отсутствие света.
Мы можем изучить свет, но не темноту. Мы можем использовать призму Ньютона, чтобы разложить белый свет
на множество цветов и изучить различные длины волн каждого цвета. Вы не можете измерить темноту.
Простой луч света может ворваться в миртемноты и осветить его. Как вы можете узнать насколько темным
является какое-либо пространство? Вы измеряете, какое количество света представлено. Не так ли?
Темнота это понятие, которое человек использует, чтобы описать, что происходит при отсутствии света.

А теперь скажите, сэр, смерть существует?
Профессор: Конечно. Есть жизнь, и есть смерть - обратная ее сторона.
Студент: Вы снова неправы, профессор. Смерть - это не обратная сторона жизни, это ее отсутствие.
В вашей научной теории появилась серьезная трещина.
Профессор: К чему вы ведете, молодой человек?
Студент: Профессор, вы учите студентов тому, что все мы произошли от обезьян.
Вы наблюдали эволюцию собственными глазами?
Профессор покачал головой с улыбкой, понимая, к чему идет разговор.
Студент: Никто не видел этого процесса, а значит вы в большей степени священник, а не ученый.
(Аудитория взорвалась от смеха)
Студент: А теперь скажите, есть кто-нибудь в этом классе, кто видел мозг профессора? Слышал его,
нюхал его, прикасался к нему?
(Студенты продолжали смеяться)
Студент: Видимо, никто. Тогда, опираясь на научные факты, можно сделать вывод, что у профессора нет мозга.
При всем уважении к вам, профессор, как мы можем доверять сказанному вами на лекциях?
(В аудитории повисла тишина)
Профессор: Думаю, вам просто стоит мне поверить.
Студент: Вот именно! Между Богом и человеком есть одна связь - это ВЕРА!
Профессор сел.

Этого студента звали Альберт Эйнштейн.

Продолжаю утверждать, что Эйнштейн отдыхает... :-[
Как в прямом смысле (почил в бозе), так и в переносном (про головоломку тишина)

Байки это все. Объяснение (англоязычное) тут: http://www.snopes.com/religion/einstein.asp.

А я прошусь в кассиры.

Виноват. Вроде бы создали Ассоциацию настольных логических игр. Надо туда, если посыл в РШФ не нравится.

Как раз нравится!
Вам, как москвичу, мы с Владом поручаем пролоббировать эту затею в высших сферах
В случае удачных переговоров, кассиром Вы приняты!

З.Ы. И руководителем Московской федерации НИМа

Конечно, байки. Сейчас Эйнштейну приписывают все что угодно. Начало напоминает "Любознательную Бетси" Марка Твена, доказательство того, что тьмы не существует дырявое и физик вряд ли скажет что холод существует.

Спасибо за доверие.
Сложившаяся ситуацию напомнила анекдот времен начала перестройки.
Встречаются двое.
- Слушай, возьмешь вагон сахара?
- Почем?
- Столько-то.
- Беру.
И разошлись. Один пошел искать деньги, второй - вагон сахара.

.

Может, тогда и в шахматные поддавки надо играть так же? Разыгрываем классический дебют, следим за позиционными тонкостями, за оценкой Гудини. И лишь в самый последний момент интересуемся: во что мы там играем, в поддавки или в шахматы? И в зависимости от этого - либо всё отдаём, либо раздаём люлей.