?

Log in

No account? Create an account
задачка, математическое - Поклонник деепричастий [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)
Страница 1 из 2
<<[1] [2] >>