?

Log in

No account? Create an account
задачка, математическое - задачка, математическое - По делам сюда приплыл, а не за этим Page 2 — ЖЖ [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

задачка, математическое [фев. 10, 2010|03:34 pm]
Anatoly Vorobey
Тюремщик играет с двумя заключенными в следующую игру. Во дворе тюрьмы на земля нарисована доска размером 8x8 клеток, и в центре каждой клетки либо лежит, либо не лежит камешек. Сначала во двор выходит первый заключенный, и тюремщик указывает ему на какую-то клетку доски. Заключенный в ответ должен выбрать какую-то клетку, на свой выбор, и изменить ее состояние: либо убрать камень из центра, если он там был, либо положить в центр, если его там не было.

Потом первого заключенного уводят, и выводят второго. Он должен посмотреть на доску и угадать, на какую клетку указал тюремщик первому заключенному.

Заключенные могут заранее договориться о стратегии, но до того, как выводят первого, они не знают, как выглядит доска, и после этого любое общение между ними запрещено. Могут ли заключенные так договориться действовать, чтобы второй всегда мог правильно отгадать выбранную клетку?

Update: я раскрываю правильные решения - их штук шесть набралось за прошедшие пять часов, первыми были buddha239 и plakhov. Не заглядывайте в комменты, если хотите сами подумать.
СсылкаОтветить

Comments:
Страница 2 из 2
<<[1] [2] >>
[User Picture]From: alexsles
2010-02-10 03:04 pm
Что то так сложно все пошли.
Доска на ЗЕМЛЕ.Камень оставляет след на земле.А дальше надо просто изначально договориться,что надо делать ОДНО И ТОЖЕ к выбранной тюремщиком клетке.

Сумбурно немного,но Вы меня поняли.Надеюсь.
(Ответить) (Thread)
[User Picture]From: avva
2010-02-10 03:25 pm
Следа на земле не остается. Вообще никаких "трюков" нет, решение "честное".
(Ответить) (Parent) (Thread)
From: carpet_god
2010-02-10 03:05 pm
а если они договорятся, что после того, как тюремщик загадает клетку, первый заключенный в уме поворачивает доску по часовой стрелке 1 раз и убирает камень, если он есть в клетке тюремщика, и ставит, если нету.
приходит второй, смотрит на доску, поворачивает ее в уме, и смотрит, инвертировался ли где-нибудь камень.

что-то я сказал, пойду почерчу на бумажке
(Ответить) (Thread)
From: carpet_god
2010-02-10 03:08 pm
не, не то, совсем не то
(Ответить) (Parent) (Thread)
[User Picture]From: plakhov
2010-02-10 03:06 pm
Стратегия: в итоговой xor всех с камнями = указанной
Думал минут на 5 дольше, чем нужно, т.к. не заметил, что клетка (0:0) нас спасает, если уже и так равен.
(Ответить) (Thread)
[User Picture]From: avva
2010-02-10 03:10 pm
Да, правильно.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: gambo
2010-02-10 03:07 pm
увидел много знакомых слов
и зачем я сюда полез? ))

как раз Солженицына читаю
почитай Фрида, он какой-то неотрывабельный
(Ответить) (Thread)
[User Picture]From: avva
2010-02-10 03:11 pm
Попробую Фрида, да, мне понравилось у тебя описание.
(Ответить) (Parent) (Thread)
[User Picture]From: kapahel
2010-02-10 03:30 pm
Пронумеруем клетки числами от 0 до 63. Первый заключенный может своим ходом добиться любого остатка суммы номеров клеток с камнями от деления на 64.
(Ответить) (Thread)
[User Picture]From: avva
2010-02-10 03:40 pm
Точно может?
(Ответить) (Parent) (Thread) (Развернуть)
From: avm.myopenid.com
2010-02-10 03:46 pm
Клетки доски кодируются двоичными векторами от 000000 до 111111. Состояние доски L0 вычисляется как сумма всех клеток по модулю два. Когда тюремщик указывает на клетку x, 1-й заключённый изменяет состояние клетки (L0 ⊕ x). 2-й заключённый вычисляет состояние доски L1 и указывает на соответствующую клетку.
(Ответить) (Thread)
[User Picture]From: avva
2010-02-10 03:48 pm
Ага, все верно. Я заскриню пока ваш ответ.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: unbe
2010-02-10 04:18 pm
пусть указали клетку с порядковым номером X
первый xor-ит порядковые номера клеток, где есть камни в исходной позиции (число S), и меняет клетку с порядковым номером S xor X
второй xor-ит номера клеток в новой позиции и получает X.
вроде так :)
(Ответить) (Thread)
[User Picture]From: avva
2010-02-10 06:09 pm
верно, да ;)
(Ответить) (Parent) (Thread)
[User Picture]From: janatem
2010-02-10 04:45 pm
Изложу ход рассуждений. Вначале общие рассуждения.

Геометрия доски значения не имеет; есть просто 64 клетки, каждая из которых может находиться в одном из двух состояний.

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

Для наглядности можно представить всё множество состояний доски в виде 64-мерного гиперкуба, где вершины -- состояния, а ребра символизируют возможность перейти из одного состояния в другое. Тогда задача формулируется следующим образом: раскрасить вершины гиперкуба в 64 цвета так, чтобы у каждой вершины все соседи были разных цветов. Для удобства можно обозначать вершины последовательностями из нулей и единиц длины 64.

Теперь решение.

Будем действовать по индукции -- доказывать для размерности гиперкуба 2^n для всех n >= 1.

Для n=1 раскраска очевидна: 00 и 01 имеют цвет A, 10 и 11 -- цвет B.
Идея индуктивного перехода в том, чтобы представить цвет более длинной последовательности в виде суперпозиции цветов составляющих ее более коротких подпоследовательностей. Т.е. при переходе от n=1 к n=2 для последовательности 0011 ее цвет C(0011) будет C(00)C(11) = AB. Причем возможно четыре разных цвета: AA, AB, BA и BB. Восстановить строгое доказательства, думаю, уже несложно.

Теперь осталось выразить написанное выше в виде конкретного алгоритма, чтобы можно было "посчитать в уме". Но это я уже поленился сделать.
(Ответить) (Thread)
[User Picture]From: dibr
2010-02-10 04:48 pm
Нам нужно передать 6 бит.

Делим множество из 64 клеток напополам на два подмножества: А1={1-32} и А2={33-64}. Первым битом считаем чётность количества камней в множестве А1. Чтобы передать бит, мы должны либо сохранить чётность А1 (изменить множество А2), либо изменить чётность А1 (изменить множество А1). Выбираем нужное множество.

Делим каждое из подмножеств А1 и А2 напополам (В1={1-16}, В2={17-32}, В3={33-48}, В4={49-64}), объединяем попарно с чередованием (В13=В1+В3, В24=В2+В4). Вторым битом считаем чётность множества В13. В соответствии с этим выбираем подмножество В1, В2, В3 или В4 так, чтобы и В13 и А1 оказались нужной чётности.

Для третьего бита процедура повторяется с подмножествами размера 8, четвёртого - 4, пятого - 2, и шестого - 1, то есть последним шагом разбиения и выбора мы выбираем именно клетку.

Ну, а следующий заключённый просто считает чётности соответствующих множеств :-)

Хотел записать множества в виде формул, но запутался с "показательством" возможности выбрать такую точку, чтобы все нужные множества были нужной чётности. В словесном виде это более-менее понятно...
(Ответить) (Thread)
[User Picture]From: avva
2010-02-10 06:08 pm
Да, это работает. Есть более простой способ описать ровно то же решение, тут в комментах найдете ;)
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: omnibee
2010-02-10 05:06 pm
всего состояний доски: 2^64
всего клеток: 64

т.е. на входе у нас 64битное число, тюремщик выбирает бит, надо задача сводится к изменению входного числа посредством изменения одного бита, чтобы он принадлежал одному из 64 классов.

т.е. требуется разделить все 64битные числа на 64 класса, чтобы были переходы из любого класса в любой, изменением одного бита. если представить это в виде графа, то надо покрасить вершины так, чтобы из каждой вершины были видны все остальные цвета. дальше пока непонятно, как эти классы строить...
(Ответить) (Thread)
[User Picture]From: janatem
2010-02-11 08:35 am
Я рассуждал так же, и даже довел до конца: http://avva.livejournal.com/2195116.html?thread=68928428#t68928428

Только, кажется, более лобовое решение, представленное другими комментаторами (через xor по правильно выбранным подмножествам), получились и нагляднее, и эффективнее с точки зрения практического применения.

Тем не менее, видится изоморфизм между обоими типами решений. ;)
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: avva
2010-02-10 09:42 pm
Спасибо!
(Ответить) (Parent) (Thread)
From: fanfanfan01
2010-02-10 08:39 pm
А если xor заменить на обычное сложение...
Суммируем все номера клеток, где есть камни, берем остаток от деления на количество клеток. Дальше меняем на поле одну клетку так, чтобы из полученного ранее числа у нас получился номер выбранной тюремщиком клетки.
(Ответить) (Thread)
[User Picture]From: avva
2010-02-10 09:36 pm
Это не работает, потому что представьте, что вам например надо сделать +15, а получается только -15, потому что на этой клетке камень уже стоит.

xor работает, потому что в отличие от сложения является обратной по отношению к себе операцией.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: melkore
2010-02-10 10:07 pm
если эти двое могут вырубить тюремщика и сбежать - то зачем им отвечать на его никому не нужные загадки? ))
(Ответить) (Thread)
From: elfz
2010-02-11 01:50 pm
Красивая задача. По моему, ее можно упростить, не требуя _объязательного_ выбора клетки — если заключённый хочет оставить всё как есть, ну и пусть оставляет, это в результате равносильно манипуляциям клетки 00000, но добавляет чувство свободы и широкого выбора :)
(Ответить) (Thread)
Страница 2 из 2
<<[1] [2] >>