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

[maxal]

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

Цитата:

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

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

Что значит не является?! Конечное поле из $N=2^n$ элементов существует - его-то здесь и обозначают буквой $F$.
И тот факт, что это поле характеристики 2, еще как используется! См. ниже.

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

Цитата:

Элис и Боб каждой карточке (в порядке их следования) присваивают свой уникальный элемент $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 + X = f_k$ в поле всегда разрешимо - его решение $X=B+f_k$ (напоминаю, что дело происходит в поле характеристики 2: плюс и минус здесь - это одна и та же операция).
Во-вторых, индекс $j$ такой, что $X=f_j$ найдется просто потому, что $f_1,f_2,\dots,f_N$ - это все элементы поля, и $X$ как элемент поля обязан быть одним из них.

Таким образом, Элис выбирает $j$ так, что выполняется соотношение: $B+f_j = f_k$ (как впрочем, и соотношение $B+f_k = f_j$).

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

Цитата:

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

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

Так как перевернута была карточка с номером $j$, то суммы вычисленные Элис и Бобом будут отличаться в точности на $f_j$. Поэтому $B'=B+f_j=f_k$ (согласно выбору $f_j$ - см. выше), где $k$ - это то самое загаданное число.

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

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

Что значит не является?! Конечное поле из $2^N$ элементов существует - его-то здесь и обозначают буквой $F$.
И тот факт, что это поле характеристики 2, еще как используется! См. ниже.

Мнда, мой минус раз. (только, не $2^N$ элементов, а $N=2^n$ элементов)

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

Во-первых, линейное уравнение $B + X = f_k$ в поле всегда разрешимо - его решение $X=B+f_k$ (напоминаю, что дело происходит в поле характеристики 2).
Во-вторых, индекс $j$ такой, что $X=f_j$ найдется просто потому, что $f_1,f_2,\dots,f_N$ - это все элементы поля, и $X$ как элемент поля обязан быть одним из них.

Мой минус два. Постоянно в голове путаются $N=2^n$ и $2^N$

Сознаюсь, наврал.