Задача о шахматной доске, монетках и ключе

[manul91]

Участвующие: ведущий (В) и два друга (А и Б).

Друзья А и Б договариваются заранее о своей (по идее, выигрышной) стратегии.

Правила "игры" таковы:
0. Все трое находятся в комнате, и на столе лежит пустая шахматная доска.
1. Один из друзей - Б - выходит из комнаты.
2. Ведущий В расставляет 64 монетки на каждом из полей шахматной доски, орлом вверх или лицом вниз. После этого он кладет ключ поверх одного из полей. Ведущий размещает монетки на доске любым способом по своему усмотрению (также и выбирает поле, на котором будет находиться ключ).
3. Затем А выбирает ровно одну из 64 монеток, включая возможно ту, под которой находится ключ, и переворачивает ее.
4. Ключ убирается с доски.
5. В комнату возвращается Б и осматривает доску с монетками. Основываясь только на этой информации, он должен однозначно указать на поле, на котором был выставлен ключ.

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

[sergey zhukov]

manul91
64 клетки - это 64-разрядное двоичное число. Нужно заранее разбить все множество этих чисел ($2^{64} вариантов$) на 64 группы (по числу клеток на доске), каждой из этих групп сопоставить определенное положение ключа на доске.

Числа в группы нужно объединить так (это стратегия $A$ и $B$), чтобы перестановкой одного бита любого числа из любой группы его можно было перевести в число любой другой группы.

Ведущий расставляет монетки и ключ случайно. $A$ видит, что монетки образуют число из группы, которая не совпадает с положением ключа (указывает неверное положение ключа). Заменив один бит в этом числе, он переводит его в число из группы, которая указывает верное положение ключа.

Скажем, возьмем простейший случай с двумя клетками. Есть четыре варианта расстановки монет $00, 01, 10, 11$. Можно договориться, что варианты $00, 01$ образуют группу, которая указывает на первую клетку, а варианты $10, 11$ - указывают на вторую. Видно, что $A$ всегда может переставить одну монетку так, чтобы указать на любую нужную клетку независимо от действий ведущего.

[manul91]

sergey zhukov Все это очень мутно.
- Как именно разбивать множество чисел $2^{64}$ на 64 групп?
- Какова конкретно стратегия выбора монетки для перевертыша для А? Какова конкретно стратегия Б определения положения ключа исходя из состояния которое он видит?

sergey zhukov в сообщении #1606450 писал(а):

Ведущий расставляет монетки и ключ случайно. $A$ видит, что монетки образуют число из группы, которое не совпадает с положением ключа (указывает неверное положение ключа).

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

[sergey zhukov]

manul91 в сообщении #1606452 писал(а):

Нельзя этого допускать

Есть возможность так же так поменять монетку, чтобы остаться в исходной группе (как в примере выше). Я согласен, что решение не конструктивное. Даже можно сомневаться, существует ли вообще такое разбиение на группы.

[manul91]

sergey zhukov в сообщении #1606454 писал(а):

Я согласен, что решение не конструктивное. Даже можно сомневаться, существует ли вообще такое разбиение на группы.

Раз "решение не конструктивное", это пока еще не решение - разве что, "размышления по теме": )
Вопрос как раз именно о вполне конкретной, рабочей стратегии.
Но вы правильно переформулировали задачу - вопрос в том как, поменяв ровно одного бита в 64-битном двоичном числе, указать на конкретного числа (позицию ключа) с 1 до 64 - при том тому, кто наперед не знает ни каково было исходное число, ни какой бит был перевернутым - а видит только результат после перевертыша.

-- 25.08.2023, 12:51 --

sergey zhukov в сообщении #1606450 писал(а):

Скажем, возьмем простейший случай с двумя клетками. Есть четыре варианта расстановки монет $00, 01, 10, 11$. Можно договориться, что варианты $00, 01$ образуют группу, которая указывает на первую клетку, а варианты $10, 11$ - указывают на вторую. Видно, что $A$ всегда может переставить одну монетку так, чтобы указать на любую нужную клетку независимо от действий ведущего.

Да, это указывает на то что по меньшей мере для двух клеток, решение существует (красота задачки как раз в том, что на первом взгляде кажется что такая стратегия невозможна).
Осталась самая малость, указать как обобщить на 64 (или на произвольного числа) клеток.

[mihaild]

В таких терминах - нам нужно покрасить двоичные числа длины $64$ в $64$ же цвета, так, чтобы у каждого числа были соседи всех цветов.

manul91 в сообщении #1606455 писал(а):

указать как обобщить на 64 (или на произвольного числа) клеток

На произвольное не обобщается, для например трех клеток решения нет - один из цветов встречается максимум два раза, у этих двух вхождений максимум 6 соседей, значит есть два числа, у которых соседа нужного цвета нет.

(Оффтоп)

Это небольшие подсказки решающим, я решение знаю.

[manul91]

mihaild в сообщении #1606460 писал(а):

На произвольное не обобщается, для например трех клеток решения нет - один из цветов встречается максимум два раза, у этих двух вхождений максимум 6 соседей, значит есть два числа, у которых соседа нужного цвета нет.

То, что какая-то известная стратегия для 64 на произвольное количество не обобщается - само по себе не доказывает, что нет (другой) стратегии которая обообщается.

Что такая стратегия не существует для любого $N$ (в частности $N=3$) - нужно отдельно специально доказывать (я не уверен, обобщается ли или нет - хотя стратегия которая я знаю вроде отлична от вашей, но она тоже не обобщается).

Выбор одну из $N$ позиций (для перевертыша) уменьшает неопределенность ровно в $\ln_{2}{\frac{1}{n}}$ бит - вроде бы как раз столько, сколько нужно чтобы передать информацию о числе с 1 до $N$...

[mihaild]

manul91 в сообщении #1606464 писал(а):

То, что какая-то известная стратегия для 64 на произвольное количество не обобщается - само по себе не доказывает, что нет (другой) стратегии которая обообщается

Так я первым предложением написал, как описывается вообще любая стратегия. А именно - покрасим каждую возможную последовательность в цвет, равный номеру, который назовет Б, увидев эту последовательность. Тогда А должен иметь возможность, получив любую последовательность и цвет, сделав ровно одно изменение в этой последовательности, получить последовательность этого цвета. Для этого необходимо, чтобы у каждой последовательности для каждого цвета был хотя бы один сосед каждого цвета.
Но последовательности длины 3 раскрасить в 3 цвета так, чтобы у каждой последовательности были соседи всех трех цветов, невозможно.

И да, из соображений количества информации эта невозможность не получается, нужен чуть более тонкий анализ графа.

[manul91]

mihaild в сообщении #1606466 писал(а):

Но последовательности длины 3 раскрасить в 3 цвета так, чтобы у каждой последовательности были соседи всех трех цветов, невозможно.

(Оффтоп)

Да, теперь все понятно. Вроде легко обобщить на случае если $N$ не делит $2^{N}$ (т.е. например для нечетных). Остаются возможными только случаи когда $N$ - степень двойки. Правильно?

[Null]

manul91 в сообщении #1606452 писал(а):

Как именно разбивать множество чисел $2^{64}$ на 64 групп?

Расставим на клетки числа от 0 до 63 и возьмем "побитовое исключающее или" у тех клеток где лежит орел - получим номер группы.

[manul91]

Null в сообщении #1606473 писал(а):

Расставим на клетки числа от 0 до 63 и возьмем "побитовое исключающее или" у тех клеток где лежит орел - получим номер группы.

Что если ведущий везде расставил решек, каков будет "номер группы"?
Пусть ведущий везде расставил решек, кроме как на 0-вой позиции где лежит орел, и на 63-ей позиции (т.е. "группа = 0 xor 63 = 63"). Ключ выставлен на 37-ой клетке и потом убран.
Какую монетку перевернет А и почему? Как должен рассуждать Б, чтобы определить где был ключ?

[Null]

А переворачивает 26($=37 \operatorname{xor} 63$) монету. Итого 37 группа. Б говорит что ключ в 37 клетке.

[manul91]

Null в сообщении #1606482 писал(а):

А переворачивает 26($=37 \operatorname{xor} 63$) монету. Итого 37 группа. Б говорит что ключ в 37 клетке.

Вроде работает, но не могу допереть какова конкретная стратегия А на выбора монетку для переворачивания в общем случае.
А получает с ведущего доску в "состоянии группы" $(b_1 \land 000000) \oplus (b_2 \land 000001) \oplus (b_3 \land 000010) \oplus ... \oplus (b_{63} \land 111111)$, где $b_1$ - $b_{63}$ соответно состояния орла (1) или решки (0) на данной позиции.
Каким образом А решает какого $b_n$ перевернуть, чтобы получить для данного выражения любой требуемый номер группы с 0 до 63?

[mihaild]

Мысленно заменяет ключ еще одним орлом, считает всю ту же сумму, и переворачивает монетку с получившимся номером.

[manul91]

mihaild Null
Да верно, гениально.
Напишу свое решение, оно не так элегантное, основано на двоичных бисекций (обобщение протокола для двух клеток).
Поясню на случае с 8-ми клеток (восьмибитное число XXXXXXXX).
Введем понятия "четности группы битов" (четность количества единиц, которые входят в этой группе).
Очевидно что переворачивая монетку на какой-то позиции, А меняет четность любой группе битов, в которой эта позиция входит.
Идея в том, чтобы А своим переворачиванием смог передать информацию о любой позиции (с 0 до 7), указывая B: 1) в какой половине битов позиция находится, левой или правой; 2) в какой половине из соответной половины позиция находится, левой или правой... и т.д. 3 раз (для 8 клеток) разбивая двоично, чтобы позиция была однозначно определена.

Для этой цели, А разбивает оригинальное восьмибитное число XXXXXXXX на разных пар групп четырехбитных чисел, а именно:
1) Две четырехбитные числа A и B, из битов соответно AAAABBBB.
2) Две четырехбитные числа A и B, из битов соответно AABBAABB.
3) Две четырехбитные числа A и B, из битов соответно ABABABAB.
Теперь, на первом этапе восьмерка аналогична случаю двух клеток (только вместо решка/орел, смотрим на "четность первых 4 битов", и "четность вторых 4 битов").
Какие бы четности не были (НН, НЧ, ЧН, ЧЧ) очевидно что путем переворачивания либо в левой половине, либо в правой половине - А волен изменить четность любой половины - и аналогично как в случае двух клеток, может передать инфу B в какой из половин битов позиция ключа находилась (левой, или правой).
Допустим, А для этого понадобилось поменять четность в какой-то конкретной половине (например, левой).
Но А здесь имеет возможность выбора - он может поменять любой из 4-х битов в требуемой половине, не меняя итог. Тем самым он может передаст дополнительную инфу (еще один бит), в какой "половине из половины" позиция ключа находилась.
Переходя к разбиении 2 выше (разбиения AABBAABB), видно что (независимо четность какой половины ему нужно поменять) - то он может дополнительно изменить четность групп либо первых двух, либо вторых двух битов (из соответной половины). Тем самым четность этих новых групп из 4 бит А или B, далее укажет в какой "половине половины" (левой или правой) позиция ключа находилась.
Разбиения 1-3 выше для случая восьми ($2^3$) клеток очевидным образом обобщаются на $2^N$ клеток.

Итого путем вычисления четностей соответных пар групп бит (и пользуясь протоколом для двух клеток), выбором позиции переворачиваемой монетки, A может передать любое N-битное число (позицию ключа).