задачка, математическое

[avva]

Тюремщик играет с двумя заключенными в следующую игру. Во дворе тюрьмы на земля нарисована доска размером 8x8 клеток, и в центре каждой клетки либо лежит, либо не лежит камешек. Сначала во двор выходит первый заключенный, и тюремщик указывает ему на какую-то клетку доски. Заключенный в ответ должен выбрать какую-то клетку, на свой выбор, и изменить ее состояние: либо убрать камень из центра, если он там был, либо положить в центр, если его там не было.

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

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

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

Comments

[breqwas.livejournal.com]

Хм. Уж нет ли в этом посте пропаганды пыток и издевательств над заключёнными в тюрьмах?

[breqwas.livejournal.com]

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

[alsterellie.livejournal.com]

Первая мысль — не могут. Для того, чтобы зашифровать состояния доски из 8х8 клеток, нужно шесть битов: ln2(8) + ln2(8). Заключённые же своими перекладываниями могут рассчитывать разве что на 1-2 бита. Но посмотрю на ответы остальных, любопытно.

[http://users.livejournal.com/_1313/]

нужно зашифровать координаты клетки, номера рядов указать. это два бита как раз

[flaass.livejournal.com]

Белоснежка и 7*9 гномов :)

[phoonzang.livejournal.com]

Первый заключенный может менять или не менять ту клетку, на которую указал тюремщик? Если нет, то какой смысл в том, что тюремщик ему сперва указывает на какую-то клетку?

[phoonzang.livejournal.com]

а, сорри, понял

[chessplayer.livejournal.com]

он обязан менять или может все так оставить?

[avva.livejournal.com]

Обязан.

[buddha239.livejournal.com]

Мне кажется, что пару лет назад очень похожая задачка уже была (возможно, действительно про Белоснежку).:) И то же решение все так же работает.:)

[avva.livejournal.com]

http://community.livejournal.com/ru_math/28836.html
по-моему, это другая задача.

http://avva.livejournal.com/1743110.html
это тоже другая задача :)

[http://users.livejournal.com/_1313/]

а изначальное положение "нет ни одного камня" валидное?

[avva.livejournal.com]

да.

[dimmik.livejournal.com]

Ну, самое тупое "в лоб" решение - товарищи заранее договариваются о всех возможных соответствиях ("исходное состояние доски", "указанная клетка") <-> ("конечное состояние доски")
И по "конечному состоянию" определяют указанную клетку.

[phoonzang.livejournal.com]

отображение 2^64 x 2^8 -> 2^64 не так уж и легко инвертируется

[fistashkin.livejournal.com]

Я по-чайницки)

Если тюремщик указал на клетку с камнем, то первый заключенный просто берет первую попавшуюся (другую) клетку с камнем и перекладывает этот камень на первую клетку. Второй заключенный элементарно отгадывает клетку, на которой лежит два камня (надеюсь, это не противоречит условиям? ведь там не сказано, что первый заключенный должен убрать камень из центра, но без права перекладывания на другую клетку).

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

[avva.livejournal.com]

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

[burivykh.livejournal.com]

Хм, по информации как раз совпадает: в одну позицию могут переходить максимум 64, значит, максимум 64 разных "классов образов", а класс образов и должен задавать клетку...

[phoonzang.livejournal.com]

по своему отношению к симметриям квадрата? группа как раз 8го порядка

[dimmik.livejournal.com]

Какие-нибудь дополнительные способы передачи информации (например, "подумать x минут") допускается?

[avva.livejournal.com]

нет.

[phoonzang.livejournal.com]

грубая гипотеза: изменив одну клетку, всегда можно добиться, чтобы полученная конфигурация была неподвижна относительно одного (а может и двух?) из элементов группы D4

[kapahel.livejournal.com]

Это неправда.

[shvarz.livejournal.com]

Чем только не развлекаются тюремщики...

[cxielamiko.livejournal.com]

Рассмотрим граф позиций с рёбрами-переходами. Степени всех вершин — 64. Если его вершины можно раскрасить в 64 цвета без наличия одноцветных рёбер, то задача решена. Возможна ли такая раскраска?

[omnibee.livejournal.com]

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

[amarao-san.livejournal.com]

... взять булыжник, говорите, и бросить за пределы доски? В сторону охранника можно?

[alexsles.livejournal.com]

Что то так сложно все пошли.
Доска на ЗЕМЛЕ.Камень оставляет след на земле.А дальше надо просто изначально договориться,что надо делать ОДНО И ТОЖЕ к выбранной тюремщиком клетке.

Сумбурно немного,но Вы меня поняли.Надеюсь.

[avva.livejournal.com]

Следа на земле не остается. Вообще никаких "трюков" нет, решение "честное".

[carpet-god.livejournal.com]

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

что-то я сказал, пойду почерчу на бумажке

[carpet-god.livejournal.com]

не, не то, совсем не то

[plakhov.livejournal.com]

Стратегия: в итоговой xor всех с камнями = указанной
Думал минут на 5 дольше, чем нужно, т.к. не заметил, что клетка (0:0) нас спасает, если уже и так равен.

[avva.livejournal.com]

Да, правильно.

[gambo.livejournal.com]

увидел много знакомых слов
и зачем я сюда полез? ))

как раз Солженицына читаю
почитай Фрида, он какой-то неотрывабельный

[avva.livejournal.com]

Попробую Фрида, да, мне понравилось у тебя описание.

[kapahel.livejournal.com]

Пронумеруем клетки числами от 0 до 63. Первый заключенный может своим ходом добиться любого остатка суммы номеров клеток с камнями от деления на 64.

[avva.livejournal.com]

Точно может?

[avm.myopenid.com (from livejournal.com)]

Клетки доски кодируются двоичными векторами от 000000 до 111111. Состояние доски L₀ вычисляется как сумма всех клеток по модулю два. Когда тюремщик указывает на клетку x, 1-й заключённый изменяет состояние клетки (L₀ ⊕ x). 2-й заключённый вычисляет состояние доски L₁ и указывает на соответствующую клетку.

[avva.livejournal.com]

Ага, все верно. Я заскриню пока ваш ответ.

[unbe.livejournal.com]

пусть указали клетку с порядковым номером X
первый xor-ит порядковые номера клеток, где есть камни в исходной позиции (число S), и меняет клетку с порядковым номером S xor X
второй xor-ит номера клеток в новой позиции и получает X.
вроде так :)

[avva.livejournal.com]

верно, да ;)

[janatem.livejournal.com]

Изложу ход рассуждений. Вначале общие рассуждения.

Геометрия доски значения не имеет; есть просто 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. Восстановить строгое доказательства, думаю, уже несложно.

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

[dibr.livejournal.com]

Нам нужно передать 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, то есть последним шагом разбиения и выбора мы выбираем именно клетку.

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

Хотел записать множества в виде формул, но запутался с "показательством" возможности выбрать такую точку, чтобы все нужные множества были нужной чётности. В словесном виде это более-менее понятно...

[avva.livejournal.com]

Да, это работает. Есть более простой способ описать ровно то же решение, тут в комментах найдете ;)

[omnibee.livejournal.com]

всего состояний доски: 2^64
всего клеток: 64

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

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

[janatem.livejournal.com]

Я рассуждал так же, и даже довел до конца: http://avva.livejournal.com/2195116.html?thread=68928428#t68928428

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

Тем не менее, видится изоморфизм между обоими типами решений. ;)