alexer

Так, пока выдалась еще свободная минутка, публикую решение задачи про заключенных. Я не знаю, то ли это решение, которое Димыч нашел в сети: я его по дороге с работы придумал. Пусть Димыч напишет, совпадает ли: интересно.

Прежде всего, рассмотрим ту же задачу, когда есть всего две клетки. Я буду писать "0", когда монета повернута аверсом или "1" когда она повернута реверсом для простоты. Возможные варианты выкладывания монет следующие:
00, 01, 10, 11
Предлагается следующий код: когда обе монеты повернуты аверсом либо реверсом (т.е. выкладка 00 или 11), то "магическая" монета находится в первой клетке. В противном случае (т.е. когда выкладка была 01 или 10), то "магическая" монета лежит во второй клетке. Понятно, что перевернув любую монету, либо оставив все без изменений всегда можно закодировать правильное положение "магической" монеты.
Пример 1: выкладка 11, "магическая" монета во второй клетке. Можно попросить надзирателя перевернуть любую из монет.
Пример 2: выкладка 10, "магическая" монета в первой клетке. Снова можно попросить перевернуть любую, что приведет к выкладке 00 или 11, что является опять правильным кодом.
Важно: в предлагаемом коде принципиальным является то, что переворачивать можно любую монету или ни одну, это дает возможность масштабировать решение на бОльшие размерности.

Теперь, перейдем к размерности доски 2х2. Выпишим выкладку монет построчно, строка за строкой. Например 0111 будет означать, что в первой строке доски лежали монеты, развернутые аверсом и реверсом, а во второй обе повернуты реверсом. Я разобью строчку пополам, вот так: 01|11. В каждой из строчек посчитаю количество единиц. Если их четное число, вместо соответствующей половины нарисую 0. Если нечетное — рисую 1. Понятно, что, перевернув любую монету в любой из "половинок", я изменю четность этой "половинки". Переворачивать буду в той "половинке", в которой находится "магическая" монета если код в ней требует корректировки. В противном случае — в другой "половинке", чтобы ничего не испортить. Помимо прочего, воспользуюсь кодом, приведенным выше для двух монет, чтобы закодировать, но уже с помощью четностей, в какой именно "половинке" находится монета. Одновременно, пользуясь этим же кодом, буду кодировать где именно в этой "половинке" она находится. Например, для раскладки выше предположим, что "магическая" монета была в положении (1,2), т.е. находилась в первой строке второго столбца. Считаю четности 01|11->1|0. Это кодирует положение "магическая монета во второй строке", что неверно. Т.е. мне нужно перевернуть любую из монет в первой или во второй "половинке", чтобы прийти к правильному коду. Первая половинка содержит 01, что означает "второй столбец". Это правильно и я не хочу это портить, поэтому прошу надзирателя перевернуть любую из монет из "половинки" 11, что приведет к правильному коду.

Аналогичные рассуждения обобщаются на 8, 16, 32 и, в конечном итоге, 64 монеты.

Например, для восьми монет. Предположим, что выкладка была: 10010110. И искомая монета - четвертая. Считаем четности:
1001|0110->0|0. Это правильно, пока ничего не переворачиваем. Далее по этому коду монета находится в группе 1001.
Считаем четности: 1|1. Это неверно, надо менять четность. Четность будем менять в группе 10, т.к. группа 01 уже правильно кодирует
положение монеты и мы не хотим его портить. Т.е. просим надзирателя перевернуть любую из первых двух монет. Это ведет к правильному коду.

Если вдруг найдутся ошибки, буду признателен.