Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
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, которые являются степенью двойки. Так что неудивительно, что для четырех монет решение есть; интересно, что скажем для пяти или шести его уже не существует.
Subscribe
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 3 comments