Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
avva

Category:

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

Очень милая задачка от Джона Конвея (изобретателя игры "Жизнь").

Есть три карты: туз, король и дама, и они могут лежать на одной из трех позиций на столе перед вами - назовем эти позиции L,M,R (left, middle, right).
Карты всегда лежат лицом вверх, но если больше одной карты лежат в одной позиции, то вы видите только верхнюю. Например, может быть так, что слева лежит король на даме (и вы видите только короля), посредине туз, а справа ничего. Может, все три карты лежат справа, и вы видите только верхнюю. И так далее.

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

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

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

Это все. Нужно придумать алгоритм, который любое начальное положение приводит к выигрышному. Я думаю, что можно эту задачу решить компьютерным способом, а можно на бумаге (может, есть такие монстры, что и в уме смогут, я не из них). Я решил на бумаге, это было не очень легко и довольно приятно. Предупреждаю: если вы нашли решение и оно довольно простое, подумайте как следует, действительно ли вы учли эффект краткосрочной памяти и действительно ли любое начальное положение приходит к победе.
Tags: задачка
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.
  • 56 comments
Previous
← Ctrl ← Alt
Next
Ctrl → Alt →
Previous
← Ctrl ← Alt
Next
Ctrl → Alt →