?

Log in

задачка, математическое - Поклонник деепричастий [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:
Страница 1 из 2
<<[1] [2] >>
[User Picture]From: breqwas
2010-02-10 01:44 pm
Хм. Уж нет ли в этом посте пропаганды пыток и издевательств над заключёнными в тюрьмах?
(Ответить) (Thread)
[User Picture]From: breqwas
2010-02-10 01:46 pm
( всегда было любопытно, почему в такого рода задачах так часто встречаются тюремщики, палачи и прочие людоеды, даже когда сюжетной необходимости в них нет )
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: alsterellie
2010-02-10 01:47 pm
Первая мысль — не могут. Для того, чтобы зашифровать состояния доски из 8х8 клеток, нужно шесть битов: ln2(8) + ln2(8). Заключённые же своими перекладываниями могут рассчитывать разве что на 1-2 бита. Но посмотрю на ответы остальных, любопытно.
(Ответить) (Thread)
[User Picture]From: _1313
2010-02-10 01:59 pm
нужно зашифровать координаты клетки, номера рядов указать. это два бита как раз
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: flaass
2010-02-10 01:49 pm
Белоснежка и 7*9 гномов :)
(Ответить) (Thread)
[User Picture]From: phoonzang
2010-02-10 01:50 pm
Первый заключенный может менять или не менять ту клетку, на которую указал тюремщик? Если нет, то какой смысл в том, что тюремщик ему сперва указывает на какую-то клетку?
(Ответить) (Thread)
[User Picture]From: phoonzang
2010-02-10 01:52 pm
а, сорри, понял
(Ответить) (Parent) (Thread)
[User Picture]From: chessplayer
2010-02-10 01:57 pm
он обязан менять или может все так оставить?
(Ответить) (Thread)
[User Picture]From: avva
2010-02-10 01:58 pm
Обязан.
(Ответить) (Parent) (Thread)
[User Picture]From: buddha239
2010-02-10 01:58 pm
Мне кажется, что пару лет назад очень похожая задачка уже была (возможно, действительно про Белоснежку).:) И то же решение все так же работает.:)
(Ответить) (Thread)
[User Picture]From: avva
2010-02-10 02:03 pm
http://community.livejournal.com/ru_math/28836.html
по-моему, это другая задача.

http://avva.livejournal.com/1743110.html
это тоже другая задача :)
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: _1313
2010-02-10 02:00 pm
а изначальное положение "нет ни одного камня" валидное?
(Ответить) (Thread)
[User Picture]From: avva
2010-02-10 02:03 pm
да.
(Ответить) (Parent) (Thread)
[User Picture]From: dimmik
2010-02-10 02:17 pm
Ну, самое тупое "в лоб" решение - товарищи заранее договариваются о всех возможных соответствиях ("исходное состояние доски", "указанная клетка") <-> ("конечное состояние доски")
И по "конечному состоянию" определяют указанную клетку.
(Ответить) (Thread)
[User Picture]From: phoonzang
2010-02-10 02:22 pm
отображение 2^64 x 2^8 -> 2^64 не так уж и легко инвертируется
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: fistashkin
2010-02-10 02:20 pm
Я по-чайницки)

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

Если же тюремщик указал на клетку без камня, то просто не вижу шансов для первого заключенного переложить камень так, чтоб второй заключенный догадался. Интересно будет узнать правильный ответ.
(Ответить) (Thread)
[User Picture]From: avva
2010-02-10 02:23 pm
противоречит :) заключенный должен убрать камень, не перекладывая его никуда. Или взять камень снаружи доски и положить на клетку, в которой его нет.
(Ответить) (Parent) (Thread)
[User Picture]From: burivykh
2010-02-10 02:30 pm
Хм, по информации как раз совпадает: в одну позицию могут переходить максимум 64, значит, максимум 64 разных "классов образов", а класс образов и должен задавать клетку...
(Ответить) (Thread)
[User Picture]From: phoonzang
2010-02-10 02:34 pm
по своему отношению к симметриям квадрата? группа как раз 8го порядка
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: dimmik
2010-02-10 02:37 pm
Какие-нибудь дополнительные способы передачи информации (например, "подумать x минут") допускается?
(Ответить) (Thread)
[User Picture]From: avva
2010-02-10 02:38 pm
нет.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: phoonzang
2010-02-10 02:40 pm
грубая гипотеза: изменив одну клетку, всегда можно добиться, чтобы полученная конфигурация была неподвижна относительно одного (а может и двух?) из элементов группы D4
(Ответить) (Thread)
[User Picture]From: kapahel
2010-02-10 02:44 pm
Это неправда.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: shvarz
2010-02-10 02:45 pm
Чем только не развлекаются тюремщики...
(Ответить) (Thread)
[User Picture]From: cxielamiko
2010-02-10 02:58 pm
Рассмотрим граф позиций с рёбрами-переходами. Степени всех вершин — 64. Если его вершины можно раскрасить в 64 цвета без наличия одноцветных рёбер, то задача решена. Возможна ли такая раскраска?
(Ответить) (Thread)
[User Picture]From: omnibee
2010-02-10 05:08 pm
одноцветные ребра вроде нужны, поскольку может потребоваться изменить состояние одной клетки доски, не меняя цвета вершины соотв. графа.
(Ответить) (Parent) (Thread)
[User Picture]From: amarao_san
2010-02-10 02:59 pm
... взять булыжник, говорите, и бросить за пределы доски? В сторону охранника можно?
(Ответить) (Thread)
[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) (Развернуть)
Страница 1 из 2
<<[1] [2] >>