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

[avva]

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

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



1. Вариант, когда игрок видит, как лежат выбранные монеты. Первыми из тех, кто задачу не знали, решили 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, которые являются степенью двойки. Так что неудивительно, что для четырех монет решение есть; интересно, что скажем для пяти или шести его уже не существует.

Comments

[lithovore.livejournal.com]

Вторая не решается быстрее, чем за 7 ходов, даже если тарелку не вращают - существует 8 расположений монет с точностью до переворачивания их всех; поскольку все разрешенные преобразования переводят разные расположения в разные, то, чтобы гарантированно добраться до выигрышного расположения, необходимо гарантированно перебрать все возможные расположения, а на это нужно 7 ходов.
В случае произвольного количества монет вида 2^n вращение тарелки тоже не увеличивает длину "слепого" решения - весьма неожиданно, на мой взгляд.

[spartach.livejournal.com]

Если интересно, эта задача была в достаточно общей формулировке на Турнире Городов полтора года назад (http://www.turgor.ru/problems/31/os31sl.pdf , в самом низу).

Удивительный факт!

[diana-shipilova.livejournal.com]

Если придерживаться такой интерпретации, то длина гарантированного решения увеличивается на единицу в обоих вариантах. Первой это отметила, кажется, diana_shipilova.

Не совсем так. Я написала, что только во втором варианте задачи возникнет разница в один ход. В первом варианте ходов как было бы пять, так и осталось.

[french-man.livejournal.com]

Я сегодня на пляже решил слепой вариант. Так же, как у тебя вверху.