Что мы знаем о лисе? Голосов: 3 Адрес блога: http://avva.livejournal.com/ Добавлен: 2007-11-28 00:44:36 блограйдером Lurk

решение задачки (математическое)

2011-05-29 22:25:24 (читать в оригинале)

Многие читатели правильно решили оба варианта четверговой задачки про переворачивание монет. Спасибо всем, кто присылал версии :)

Я вскоре раскрою все комментарии к той записи, а пока что вот правильные решения (не единственные - можно по-разному решать):

drexo и i_shmael.

Можно решить за 5 ходов. 1: Первым ходом выбираем две смежные монеты и делаем обе орлами. 2: Потом выбираем две противоположные монеты и делаем обе орлами. Если мы еще не выиграли, то осталась только одна решка. 3: Опять выбираем две противоположные монеты и только одну из них переворачиваем. Теперь (если не выиграли) у нас два смежных орла, две смежные решки. 4: Выбираем две смежные монеты, обе переворачиваем. Если не выиграли, у нас два орла и две решки вперемешку. 5: Выбираем две противоположные монеты, обе переворачиваем, выиграли.

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

2. Вариант, когда игрок не видит, как лежат выбранные монеты. Первыми из тех, кто задачу не знали, решили kapla55 и niobium0.

Можно решить за 7 ходов. Сначала заметим, что если мы начинаем с позиции ООРР или ОРОР, то выигрываем за три хода следующим образом: 1: меняем две противоположные; 2: меняем две смежные; 3: меняем две противоположные. Просто проверьте, что ОРОР приводит к выигрышу после первого из этих ходов, а ООРР - после всех трех.

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

1-3: делаем три хода как выше.
4: Если еще не выиграли, то выбираем две любые монеты и переворачиваем одну из них. Мы либо выиграли, либо перешли в ОРОР или ООРР.
5-7: опять делаем три хода как выше.

---

Несколько педантичных замечаний под конец.

Во-первых, я не совсем корректно сформулировал условие выигрыша, потому что написал, что оно проверяется "после каждого хода": если игра начинается с того, что все монеты уже лежат орлом или все решкой, то согласно моему описанию она еще не выиграна. Если придерживаться такой интерпретации, то длина гарантированного решения увеличивается на единицу в обоих вариантах. Первой это отметила, кажется, diana_shipilova. Потом я в комментариях прояснил, что "выигрышные" начальные позиции не надо рассматривать, можно считать в таком случае, что игра выиграна, не начавшись.

Во-вторых, я уверен, что эти задачи нельзя решить быстрее, чем за 5 и 7 ходов соответственно (гарантированным образом, ясно), но я не знаю, как это строго доказать, и не пытался особо. Если кто-то может доказать, было бы интересно увидеть.

В-третьих, в этой статье (англ.), требующей некоторого знания математики, рассматривается много вариантов этой задачи. В частности, в самом конце статьи рассматривается вариант, похожий на вторую задачу, когда игрок не видит монет; при этом монет много, некое число n, и игрок может на каждом ходу выбирать любое подмножество монет и переворачивать их все. Для случая n=4 это то же самое, что условие второй задачи, с незначительными изменениями. В статье доказывается, что такая задача имеет решение только для тех n, которые являются степенью двойки. Так что неудивительно, что для четырех монет решение есть; интересно, что скажем для пяти или шести его уже не существует.