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

[mihaild]

manul91, это то же самое решение, только иначе описанное:)

[manul91]

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

manul91, это то же самое решение, только иначе описанное:)

Я и подумал - что возможно "по сути" то же самое - но пока они мне кажутся разными:)
(ваше с Null решение - типа "алгебраическое", где сразу "магическим" способом получается требуемый результат; мое якобы "процедурное"/"алгоритмическое" после того как разобрался со случае двух клеток идя по тому же пути как и sergey zhukov).
Покумекаю на досуге чтобы разобраться почему стратегии оказываются "те же самые", спасибо!

[sergey zhukov]

Интересно, что для нечетного $N$ нет решения. Вроде бы кажется, что тут просто подход должен быть немного иной, а на самом деле ничего не помогает. Скажем, для случая $N=3$ есть $8$ элементов, которые должны образовывать три группы, соответствующие информации о положении ключа. $\frac{8}{3}$ не целое, но можно, кажется, образовать три группы, например, так $4+2+2$ или даже вообще так $6+1+1$. Для $B$ это было бы нормально.

Но тогда у $A$ не всегда есть возможность перевести произвольный элемент из одной группы в любую другую заменой одного бита. Если из каждого элемента всех групп можно за один шаг перейти к какому-то элементу данной группы, то это значит, что (в случае, например $4+2+2$) если мы находимся в группе с двумя элементами, то к ним в сумме должно вести шесть путей от элементов других групп (по одному от каждого), что невозможно, т.к. у каждого из наших двух элементов может быть максимум три "соседа", включая одного внутри своей группы. Т.е. число ведущих к ним путей не может быть в сумме больше четырех. Это значит, что при распределении $4+2+2$ не все группы связаны друг с другом одним шагом. Распределение элементов по группам должно быть равномерным, что невозможно в случае, если $\frac{2^N}{N}$ не целое.

[sergey zhukov]

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

Скажем, когда Шеннон описывал алгоритм сжатия данных методом последовательного деления множества элементов на две равновероятные группы, то иногда это можно сделать точно, но чаще - нельзя разделить множество точно на две равновероятные группы. Теория информации как-то эту "дискретность" игнорирует.

[manul91]

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

это выполняется именно только в среднем: часть вариантов требует меньше бита, часть - больше

Что значит "меньше бита", как интерпретировать "количество клеток когда A придется передать B меньше одного бита"? Скажем, существует ли такое количество клеток $N$ когда А сможет перевертываниeм одну из монеток, однозначно "передать число" не с нуля до $2^N-1$ а с нуля до $K$, $K > 2^N -1$?

[sergey zhukov]

manul91
Я имел ввиду, что, скажем, для $N=3$ достаточно в среднем одной монеты. Но в игре есть случаи, когда не нужно делать ничего (ноль монет), и есть случаи, когда для этого нужно перевернуть две монеты. Таким способом тут в среднем достигается одна монета, это оптимальная кодировка. Но мы ограничиваем $A$ использовать одну монету в каждом случае, а не в среднем. Тогда получается, что только в $6$ случаях из $8$ стратегия работает совершенно точно. А в двух случаях $B$ приходиться выбирать ответ наугад.

"Меньше бита" - это я неправильно сказал. Скорее, в случае $N=3$ оптимальная кодировка (в среднем - одна монета) просто несовместима с требованием "в каждом случае - одна монета".

[manul91]

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

Но в игре есть случаи, когда не нужно делать ничего (ноль монет)

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

[sergey zhukov]

manul91
Если расположение ключа случайно совпадает с тем, что дает наш код, то делать ничего не требуется. Если учесть эту возможность, то для $N=3$ в $\frac{1}{3}$ игр не нужно делать ничего, в $\frac{1}{3}$ нужно перевернуть 1 монету, в $\frac{1}{3}$ - нужно перевернуть две монеты. В среднем 1 монета.

[manul91]

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

Если расположение ключа случайно совпадает с тем, что дает наш код, то делать ничего не требуется. Если учесть эту возможность, то в $\frac{1}{3}$ игр не нужно делать ничего, в $\frac{1}{3}$ нужно перевернуть 1 монету, в $\frac{1}{3}$ - нужно перевернуть две монеты. В среднем 1 монета.

Понятно, вы фиксируете определенный "код" (стратегию) и полей ($N$=3), и варьируете к-во перевертываемых монет.
А такое же "среднее" - получается при любом фиксированном "коде", и при любом фиксированным количестве полей $N$?

[sergey zhukov]

manul91
Будем рассматривать случай, когда нужно обязательно перевернуть монету (нет варианта "ничего не делать"). Вот примерно как я понимаю.

1. Если $N$ - число клеток, то полное число элементов равно $2^N$, число групп равно $N$, число элементов в группе равно $\frac{2^N}{N}$;

2. У каждого элемента $N$ "точек связи", которыми он соединен с каким-то одним элементом из каждой группы (включая одного соседа из своей группы);

3. Если $\frac{2^N}{N}$ целое, то оно всегда так же и четное. Тогда элементы в группе разбиваются на пары "соседей", любой из элементов в группе является "соседом" ровно одного элемента этой группы, все элементы группы поэтому имеют $N-1$ "точек внешних связей" с другими $N-1$ группами. Другие группы устроены аналогично, поэтому за один шаг всегда можно перейти из данной группы в любую другую, а так же остаться в данной группе;

4. Если $\frac{2^N}{N}$ не целое (остаток от деления равен $k$), то это значит, что $k$ групп имеют на единицу большее число элементов, чем остальные $N-k$ групп (если распределить элементы по группам максимально равномерно). Тогда либо $k$, либо $N-k$ групп имеют нечетное число элементов. Нечетное число элементов в группе означает, что один элемент не имеет соседа в этой группе, либо один элемент должен иметь двух соседей (и поэтому не имеет связи с одной из внешних групп). Начав с одного из таких элементов, невозможно за один шаг либо остаться внутри группы, либо перейти в одну из внешних групп. Число таких элементов $A$ есть число групп с нечетным числом элементов, т.е. это либо $k$ (если целая часть $\frac{2^N}{N}$ четная), либо $N-k$ (если не четная). Т.е. для любого $N$ есть такое разбиение элементов по группам, что только для $A$ элементов потребуется сделать два шага. Для остальных элементов достаточно одного шага.

5. Если подсчитать $A$ для разных $N$, то получим такое:

$N~~~~~A$

$2~~~~~0$

$3~~~~~2$

$4~~~~~0$

$5~~~~~2$

$6~~~~~4$

$7~~~~~2$

$8~~~~~0$

$9~~~~~8$

$10~~~~~4$

$11~~~~~2$

$12~~~~~8$

$13~~~~~2$

$14~~~~~4$

$15~~~~~8$

$16~~~~~0$

$17~~~~~2$

$18~~~~~8$

$19~~~~~2$

$20~~~~~16$

Процент таких элементов в общем числе элементов падает с ростом $N$.

[mihaild]

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

число элементов в группе равно $\frac{2^N}{N}$

А как задаются группы?

[sergey zhukov]

mihaild
Не знаю точно. Но это как-то возможно

[mihaild]

sergey zhukov, я просто не очень понимаю, что Вы хотите доказать или получить - можете сформулировать?

[sergey zhukov]

mihaild
Доказать, что при любом заранее оговоренном между $A$ и $B$ отображении "расстановка монет на доске - положение ключа" (стратегия $A$ и $B$) существует минимум $S=A$ случаев (расстановки монет и ключа ведущим), когда стратегия $A$ и $B$ не срабатывает ($A$ требуется перевернуть не одну, а две монеты).

[manul91]

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

ри любом заранее оговоренном между $A$ и $B$ отображении "расстановка монет на доске - положение ключа" (стратегия $A$ и $B$)

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

$A$ требуется перевернуть не одну, а две монеты

Нетрудно увидеть, что существуют "неудачные" разбиения на группы при которых чтобы перейти с какую-то группу X к другую группу Y нужно более чем 2 перевертыша. Правда они "сильно неравномерные" (у групп не-почти-одинаковое к-во елементов) но не совсем очевидно почему такое нельзя получиться с "почти-равномерным по к-ва элементов" разбиениям