| решение задачки (математическое) |
[май. 29, 2011|09:25 pm]
Anatoly Vorobey
|
Многие читатели правильно решили оба варианта четверговой задачки про переворачивание монет. Спасибо всем, кто присылал версии :)
Я вскоре раскрою все комментарии к той записи, а пока что вот правильные решения (не единственные - можно по-разному решать):
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, которые являются степенью двойки. Так что неудивительно, что для четырех монет решение есть; интересно, что скажем для пяти или шести его уже не существует. |
|
|
