Фокус с монетками и числами.

[вздымщик Цыпа]

Фиксировано натуральное число $N$.

Фокус показывают два фокусника и честный статист из публики. Вначале второй фокусник отсутствует (по-честному). Статист раскладывает на столе в ряд $N$ одинаковых монеток разными сторонами вверх (произвольно). После этого называет число от $1$ до $N$. Первый фокусник переворачивает одну монетку на столе, после чего заходит второй, и глядя на монетки, угадывает названное число.

Вопрос: при каких $N$ такой фокус возможен?

[maxal]

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

[Руст]

Почему только степени двойки. Монеты перевёрнутые или нет представляют случайное N значное число в двоичном исчислении. Переворачивание одной монеты есть изменение одной цифры этого числа. Так как нас интересует число n от 1 до N, то этому числу можно сопоставить 1+остаток полученного числа при делении на N. Если число 2 образующая по модулю N и N простое, то легко закодировать это переворачиванием только одной монеты.

[maxal]

Руст писал(а):

Почему только степени двойки. Монеты перевёрнутые или нет представляют случайное N значное число в двоичном исчислении. Переворачивание одной монеты есть изменение одной цифры этого числа. Так как нас интересует число n от 1 до N, то этому числу можно сопоставить 1+остаток полученного числа при делении на N. Если число 2 образующая по модулю N и N простое, то легко закодировать это переворачиванием только одной монеты.

Нельзя - в случае, когда случайное выложенное число *уже* кодирует загаданное, согласно описанному правилу. В этом случае, перевернув одну монету (любую), фокусник все испортит.

[Руст]

А разве фокусник не кодирует переворачивая именно нужную монету. Например изменив именно ту цифру, чтобы получился нужный остаток при делении на N.

[maxal]

Руст - В указанном выше контрпримере "нужной монеты" нет - какую ни переверни, остаток будет отличаться от требуемого.

[juna]

Задача сводится к тому, чтобы разбить $2^N$ на группы, каждой из которых можно присвоить число от 1 до N, причем с помощью инверсии одного разряда можно перейти из одной группы в любую другую (так первый фокусник будет получать загаданное статистом число). Значит минимальное расстояние Хемминга между кодами одной группы должно быть 1, причем для каждого кода группы должен существовать двойственный с расстоянием Хемминга 1. Также понятно, что коды с максимальным расстоянием Хемминга должны находиться в одной группе (это коды со взаимноинверсными разрядами) иначе мы не сможем перейти из группы в группу инверсируя лишь один разряд. Также мы не можем оставить коды с максимальным расстоянием Хемминга в одной группе в одиночестве, так как в этом случае не сможем перейти в саму эту группу, т.е. группы нужно объединять. Количество групп с максимальным расстоянием Хемминга равно $2^{N-1}$. Для каждой такой пары существует пара, с которой коды из первой пары дают расстояние Хемминга - единица - их нужно объединять в одну группу. Окончательно имеем $N=2^{N-k}$.
Например, при $N=4$ кодируем так:
единица кодируется группой: $0000, 1111, 0100, 1011$
двойка кодируется группой: $0001, 1110, 0110, 1001$
тройка кодируется группой: $0010, 1101, 0101, 1010$
четверка кодируется группой: $0011, 1100, 0111, 1000$.

[Руст]

О кодах Хемминга знал кажется по книге головоломок.
Объяснение, почему $N$ должен быть степенью двойки становится понятным, если разделит весь набор $2^n$ случайных чисел на N групп c условием, что с каждого случайного числа изменив только одну цифру получить некоторое число из любой группы. Поэтому, если группы кодирующие $i,i=1,...N$ содержат $N_i$ элементов, то $N$ разным изменениям одной цифры для каждого элемента группы должны получит все $2^N$ элементов, т.е. $N_i*N>=2^N$, в то же время $N_i$ не пересекающиеся подгруппы элементов $2^N$, т.е. $\sum_iN_i<=2^N$. Отсюда $N|2^N\to N=2^k$.
Однако остается технический вопрос. При $N>10$ не один нормальный человек не может запомнить кодирующие i подмножества $N_i$. Нужен более прозрачный алгоритм построения множеств из $N_i$ элементов и быстрое распознование, а так же алгоритм нахождения нужной цифры для перехода со случайного числа к группе $N_i$.

[maxal]

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

[xaxa3217]

решки и орлы меняем на 1 и 0 соответственно. решаю так:
1) назовем образом последовательность которую видит второй фокусник, а прообразом образа будет последовательность данная статистом. у одного прообраза есть ровно $N$ различных образов получаемых инверсией одного бита образа. предположим существует алгоритм решения поставленной задачи, тогда тк второй фокусник точно определяет число лишь по заданном образу, то образ от прообраза $S(a, i)$ при инверсии i-го бита будет равен другому $S(a, j) <=> i=j$ значит кол-во всех возможных образов равно $2^N$, действительно - если нужно получить битовую строку s, то возьмем в качестве прообраза s' равную s с инверсированным первым битом, тогда найдется такое $1<=l<=N$ что придется переворачивать первую монетку (инверсировать бит).
далее, каждому образу $a_{i}$ соотв. число из промежутка от $1$ до $N$ (это необходимо чтобы второй фокусник мог дать ответ), припишем к каждому $a_{i}$ множество возможных прообразов (их $N$ штук). пусть количество образов соотв. единице равно $k_{1}$, соотв. двойке $k_{2}$ и т.д. поскольку для каждого прообраза, и любого числа $x$ существует образ соответствующий $x$, то $N*k_{i} >= 2^N$. плюс ко всему, поскольку кол-во образов $2^N$, то сумма всех $k_{i}$ так же равна $2^N$.
предположим теперь, что найдется такое $i$, что существует $j$: $k_{i} < k_{j}$ (другими словами не все $k_{i}$ равны). но тогда :
$\sum_{m=1}^{N} N*k_{i} = N^2*k_{i} < N*\sum_{i=1}^{N}k_{i} = N*2^N$
но из $N*k_{i} >= 2^N$ следует противоречие, следовательно все $k_{i}$ равны, но тогда $N*K = 2^N$, а это возможно лишь если $N$ и $K$ не имеют простых делителей кроме 2 $=> N = 2^l$, для некоторого $l$.

2) пусть $N = 2^l$, тогда используем следующий алгоритм для второго фокусника:
двоичную строку представляем как число в двоичной системе исчисления, далее считаем остаток от деления на $N$ и прибавляем единицу - называем число залу. докажем, что для любого прообраза и любого числа $1<=l<=N$ первый фокусник может получить образ образующий нужный остаток. пусть ни одной инверсией мы того что нужно не получим, тогда числа $N$ с инверсированным битом под номером $i$, и число с инверсированным битом под номером $j$ ($i>j$) по модулю $N$ равны (принцип дирихле). но это значит, что $N+t1*2^i=N+t2*2^j( mod N)$ при $t1$, $t2$ принимающие значения либо $-1$ либо $1$ (арифметикой заменили инверсию) $=> t1*2^j(2^(i-j)+t2) = 0 (mod N)$, что конечно не возможно, тк число слева делиться на $2^N$ не может => нужный остаток подобрать удается всегда

[вздымщик Цыпа]

xaxa3217 в сообщении #151232 писал(а):

2) пусть $N = 2^l$, тогда используем следующий алгоритм для второго фокусника:
двоичную строку представляем как число в двоичной системе исчисления, далее считаем остаток от деления на $N$ и прибавляем единицу - называем число залу. докажем, что для любого прообраза и любого числа $1<=l<=N$ первый фокусник может получить образ образующий нужный остаток. пусть ни одной инверсией мы того что нужно не получим, тогда числа $N$ с инверсированным битом под номером $i$, и число с инверсированным битом под номером $j$ ($i>j$) по модулю $N$ равны (принцип дирихле). но это значит, что $N+t1*2^i=N+t2*2^j( mod N)$ при $t1$, $t2$ принимающие значения либо $-1$ либо $1$ (арифметикой заменили инверсию) $=> t1*2^j(2^(i-j)+t2) = 0 (mod N)$, что конечно не возможно, тк число слева делиться на $2^N$ не может => нужный остаток подобрать удается всегда

Пусть, $N=8$, на столе лежит $0,0,0,0,0,0,0,0$ и названо число $7$. Метод не работает.

Дело в этом утверждении:

xaxa3217 в сообщении #151232 писал(а):

тк число слева делиться на $2^N$ не может => нужный остаток подобрать удается всегда

Ему и не надо делиться на $2^N$. Достаточно делиться на $N$.

maxal в сообщении #151070 писал(а):

В жж эта задача обсуждалась тут.

Там решения не нашли. Текст белым по белому в этом сообщении, очевидно, решением не является.

То, что $N$ должно быть степенью двойки — это легкая часть. Решение для $N = 4$ тоже легко найти простым подбором. Гораздо труднее найти решение для $N=8$ и тем более доказать, что оно есть для любого $N=2^k$.

Сразу скажу: у меня решения тоже нет, даже для $N=8$.

[maxal]

вздымщик Цыпа писал(а):

maxal в сообщении #151070 писал(а):

В жж эта задача обсуждалась тут.

Там решения не нашли. Текст белым по белому в этом сообщении, очевидно, решением не является.

Выделите его мышкой и прочитайте. Решение очень простое

[вздымщик Цыпа]

maxal в сообщении #151530 писал(а):

Выделите его мышкой и прочитайте. Решение очень простое

Конечно же выделял и читал. Поэтому и заявляю, что это не решение.

[maxal]

вздымщик Цыпа
Что именно вам не понравилось в этом решении?

[вздымщик Цыпа]

maxal в сообщении #151532 писал(а):

Что именно вам не понравилось в этом решении?

Давайте разберем:

Цитата:

Пусть $N=2^n$, рассмотрим $F=F(2^n)$ - поле из $2^n$ элементов. Утвержается, что в этом случае можно взять $M=N$.

То, что $F$ не является полем — это мелкий огрех, в дальнейшем не используется.

Цитата:

Элис и Боб каждой карточке (в порядке их следования) присваивают свой уникальный элемент $F: f_1, ..., f_N$.

Ничего не сказано, о том, что это за элементы, видимо произвольные.

Цитата:

Пусть зрители загадали число $k$ из $[1,N]$ и выложили карточки некоторым образом. Элис вычисляет сумму $B = \sum c(i)*f_i$, где $c(i)=0$ или $1$ - цвет $i$-ой карточки, и затем решает уравнение $B + X = f_k$ относительно $X$. Очевидно, что найдется такой индекс $j$, что $X=f_j$. Элис переворачивай $j$-ю карточку.

Это «очевидно» очевидно неверно. Если $X=f_j$, то $B = f_k - f_j$. Вариантов разностей $f_k - f_j$ не более $N^2$, а вариантов $B$ — $2^N$. Следовательно, решение будет далеко не всегда.

Цитата:

Входит Боб, вычисляет ту же сумму $B' = \sum c'(i)*f_i$ и находит такое $k$, что $B'=f_k$. Это $k$ и есть загаданное зрителями число. Все.

Ну и в довершение такой $k$ вовсе необязательно будет. Хотя уже предыдущего пункта достаточно, чтоб дальше не читать.