задачка (математическое)
Dec. 9th, 2013 01:40 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avvaОчень милая задачка от Джона Конвея (изобретателя игры "Жизнь").
Есть три карты: туз, король и дама, и они могут лежать на одной из трех позиций на столе перед вами - назовем эти позиции L,M,R (left, middle, right).
Карты всегда лежат лицом вверх, но если больше одной карты лежат в одной позиции, то вы видите только верхнюю. Например, может быть так, что слева лежит король на даме (и вы видите только короля), посредине туз, а справа ничего. Может, все три карты лежат справа, и вы видите только верхнюю. И так далее.
На каждом ходу вы можете переместить одну карту - всегда верхнюю - с любой позиции на любую другую. Например, если слева лежит король на даме, а посредине туз, вы можете решить снять короля и положить его на туза или на пустое место справа.
Ваша задача - придумать алгоритм, как перекладывать карты, чтобы в конце концов придти к выигрышному положению, когда слева лежат туз, король, дама (туз верхний, дама нижняя), а остальные позиции пустые. Но есть одно осложнение. У вас нет краткосрочной памяти. Каждый раз, когда вы делаете ход, вы забываете, что было раньше, и видите только карты, как они лежат сейчас.
(да, из этого следует, что вы не можете сами обнаружить, когда выиграли. Предполагаем, что есть посторонний наблюдатель, и как только в игре получается состояние туз-король-дама слева, он останавливает вас).
Это все. Нужно придумать алгоритм, который любое начальное положение приводит к выигрышному. Я думаю, что можно эту задачу решить компьютерным способом, а можно на бумаге (может, есть такие монстры, что и в уме смогут, я не из них). Я решил на бумаге, это было не очень легко и довольно приятно. Предупреждаю: если вы нашли решение и оно довольно простое, подумайте как следует, действительно ли вы учли эффект краткосрочной памяти и действительно ли любое начальное положение приходит к победе.
Есть три карты: туз, король и дама, и они могут лежать на одной из трех позиций на столе перед вами - назовем эти позиции L,M,R (left, middle, right).
Карты всегда лежат лицом вверх, но если больше одной карты лежат в одной позиции, то вы видите только верхнюю. Например, может быть так, что слева лежит король на даме (и вы видите только короля), посредине туз, а справа ничего. Может, все три карты лежат справа, и вы видите только верхнюю. И так далее.
На каждом ходу вы можете переместить одну карту - всегда верхнюю - с любой позиции на любую другую. Например, если слева лежит король на даме, а посредине туз, вы можете решить снять короля и положить его на туза или на пустое место справа.
Ваша задача - придумать алгоритм, как перекладывать карты, чтобы в конце концов придти к выигрышному положению, когда слева лежат туз, король, дама (туз верхний, дама нижняя), а остальные позиции пустые. Но есть одно осложнение. У вас нет краткосрочной памяти. Каждый раз, когда вы делаете ход, вы забываете, что было раньше, и видите только карты, как они лежат сейчас.
(да, из этого следует, что вы не можете сами обнаружить, когда выиграли. Предполагаем, что есть посторонний наблюдатель, и как только в игре получается состояние туз-король-дама слева, он останавливает вас).
Это все. Нужно придумать алгоритм, который любое начальное положение приводит к выигрышному. Я думаю, что можно эту задачу решить компьютерным способом, а можно на бумаге (может, есть такие монстры, что и в уме смогут, я не из них). Я решил на бумаге, это было не очень легко и довольно приятно. Предупреждаю: если вы нашли решение и оно довольно простое, подумайте как следует, действительно ли вы учли эффект краткосрочной памяти и действительно ли любое начальное положение приходит к победе.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2013-12-09 02:36 pm (UTC)Условие : Действие
A K/Q Q/K : A на K
K Q/A A/Q : K на A
Q K/A A/K : K на Q
0 A/K Q : Q на 0
K A 0 : A на K
A Q 0 : A на 0
Q K/A 0 : Q на 0
A 0 0 : A на 0
K 0 0 : K на 0
Q 0 0 : Q на 0