?

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:
[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: buddha239
2010-02-10 02:13 pm
Ну, может, не было такой задачи.:) Все равно - каждая клетка кодируется своим восьмимерным вектором над Z/2Z, и первый может добиться любой суммы - в том числе той, которая покажет на нужную клетку.
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2010-02-10 02:14 pm
это верно, да :) я заскриню пока.
(Ответить) (Parent) (Thread)
[User Picture]From: avzel
2010-02-10 09:34 pm
Прошу прощения за тупость. Почему клетка кодируется восьмимерным двоичным вектором, если клеток 64 = 2^6?
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2010-02-10 09:38 pm
шестиричным, конечно, думаю, buddha39 просто описался; впрочем, он сам сможет подтвердить :)
(Ответить) (Parent) (Thread)
[User Picture]From: avzel
2010-02-10 09:45 pm
Спасибо. Да, конечно, шестимерным, до меня уже тоже дошло.
(Ответить) (Parent) (Thread)
[User Picture]From: buddha239
2010-02-10 10:25 pm
Описался, да - и, кстати, я из 239 школы.:)
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2010-02-10 10:32 pm
sorry :)
(Ответить) (Parent) (Thread)
[User Picture]From: buddha239
2010-02-10 10:21 pm
Это я прошу прощения за маразм - шестиричным, конечно.:)
(Ответить) (Parent) (Thread)
[User Picture]From: avzel
2010-02-11 02:21 pm
Спасибо, я уже разобрался. Я даже сочинил вариант задачи, где не нужно требовать, чтобы число объектов угадывания было степенью двойки. У фокусника есть две одинаковых колоды карт (количество карт в колоде произвольно). Он предлагает зрителю загадать карту и сообщить её своему ассистенту. После этого ассистент предлагает другому зрителю выбрать несколько карт из одной колоды (ни одной или всю колоду тоже разрешается), добавляет к ним одну карту из другой колоды, возвращает это множество карт фокуснику, и тот отгадывает задуманную первым зрителем карту.

Решение: карты кодируются элементами произвольной абелевой группы данного порядка (например, циклической), и ассистент добавляет такой элемент, чтобы общая сумма равнялась значению задуманной карты.
(Ответить) (Parent) (Thread)
[User Picture]From: knop
2010-02-10 09:29 pm
О, да. А вот это - все-таки почти та же самая задача:
http://knop.livejournal.com/141511.html
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2010-02-10 09:32 pm
Да, действительно :)
(Ответить) (Parent) (Thread)