| Страница 1 из 2 | | << | [1] [2] | >> |
Хм. Уж нет ли в этом посте пропаганды пыток и издевательств над заключёнными в тюрьмах?
( всегда было любопытно, почему в такого рода задачах так часто встречаются тюремщики, палачи и прочие людоеды, даже когда сюжетной необходимости в них нет )
Первая мысль — не могут. Для того, чтобы зашифровать состояния доски из 8х8 клеток, нужно шесть битов: ln2(8) + ln2(8). Заключённые же своими перекладываниями могут рассчитывать разве что на 1-2 бита. Но посмотрю на ответы остальных, любопытно.
нужно зашифровать координаты клетки, номера рядов указать. это два бита как раз
Белоснежка и 7*9 гномов :)
Первый заключенный может менять или не менять ту клетку, на которую указал тюремщик? Если нет, то какой смысл в том, что тюремщик ему сперва указывает на какую-то клетку?
он обязан менять или может все так оставить?
Мне кажется, что пару лет назад очень похожая задачка уже была (возможно, действительно про Белоснежку).:) И то же решение все так же работает.:)
а изначальное положение "нет ни одного камня" валидное?
Ну, самое тупое "в лоб" решение - товарищи заранее договариваются о всех возможных соответствиях ("исходное состояние доски", "указанная клетка") <-> ("конечное состояние доски")
И по "конечному состоянию" определяют указанную клетку.
отображение 2^64 x 2^8 -> 2^64 не так уж и легко инвертируется
Я по-чайницки)
Если тюремщик указал на клетку с камнем, то первый заключенный просто берет первую попавшуюся (другую) клетку с камнем и перекладывает этот камень на первую клетку. Второй заключенный элементарно отгадывает клетку, на которой лежит два камня (надеюсь, это не противоречит условиям? ведь там не сказано, что первый заключенный должен убрать камень из центра, но без права перекладывания на другую клетку).
Если же тюремщик указал на клетку без камня, то просто не вижу шансов для первого заключенного переложить камень так, чтоб второй заключенный догадался. Интересно будет узнать правильный ответ.
противоречит :) заключенный должен убрать камень, не перекладывая его никуда. Или взять камень снаружи доски и положить на клетку, в которой его нет.
Хм, по информации как раз совпадает: в одну позицию могут переходить максимум 64, значит, максимум 64 разных "классов образов", а класс образов и должен задавать клетку...
по своему отношению к симметриям квадрата? группа как раз 8го порядка
Какие-нибудь дополнительные способы передачи информации (например, "подумать x минут") допускается?
грубая гипотеза: изменив одну клетку, всегда можно добиться, чтобы полученная конфигурация была неподвижна относительно одного (а может и двух?) из элементов группы D4
Чем только не развлекаются тюремщики...
Рассмотрим граф позиций с рёбрами-переходами. Степени всех вершин — 64. Если его вершины можно раскрасить в 64 цвета без наличия одноцветных рёбер, то задача решена. Возможна ли такая раскраска?
одноцветные ребра вроде нужны, поскольку может потребоваться изменить состояние одной клетки доски, не меняя цвета вершины соотв. графа.
... взять булыжник, говорите, и бросить за пределы доски? В сторону охранника можно?
| Страница 1 из 2 | | << | [1] [2] | >> |
| 
