Каменные биты.

[TOTAL]

EtCetera в сообщении #752643 писал(а):

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

Что такое "передать сообщение"? Перечислите все сообщения первого и все сообщения второго, которые они (независимо друг от друга) могут передать друг другу.

[nikvic]

TOTAL в сообщении #752809 писал(а):

Что такое "передать сообщение"?

Передать номер сообщения.
Т.е. списки сообщений у каждого есть, и подразумевается известный сюжет, "анекдот номер 5".

[TOTAL]

nikvic в сообщении #752813 писал(а):

TOTAL в сообщении #752809 писал(а):

Что такое "передать сообщение"?

Передать номер сообщения.
Т.е. списки сообщений у каждого есть, и подразумевается известный сюжет, "анекдот номер 5".

Перечислите все сообщения первого и второго.

[nikvic]

TOTAL в сообщении #752816 писал(а):

Перечислите все сообщения первого и второго.

$1,2,.... f$
$1,2,.... s$

(формулы)

Deggial: добавить пару долларов - это так сложно...

[EtCetera]

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

TOTAL

TOTAL в сообщении #752809 писал(а):

Что такое "передать сообщение"?

Пусть серия бросков выглядит так: $a_1,a_2,a_3\dots a_k$ (здесь $a_j$ $\text{---}$ количество камней в $j$-ом броске, $a_j\ge 1$, $\sum\limits_{j=1}^k a_j=n$). Броски с нечетными номерами выполнены первым агентом, броски с четными $\text{---}$ вторым. "Передать сообщение" означает выполнить свои броски таким образом, чтобы по общей серии другой агент мог понять, какая фраза из заранее заготовленного словаря фраз имеется в виду.
Подход venco, насколько я понял, заключается в том, что агенты заранее договариваются о следующей процедуре обмена сообщениями (для четного числа камней $n$): каждый обязуется использовать по $\frac{n}{2}$ камней и реализовать их за некоторое (одинаковое для обоих) число бросков $\frac{k}{2}$: $\sum\limits_{j=1}^{k/2}a_{2j-1}=\sum\limits_{j=1}^{k/2}a_{2j}=\frac{n}{2}$. Для каждого из агентов существует $\binom{n/2}{k/2}$ вариантов реализации своих бросков. Таким образом, каждый из них может однозначно идентифицировать одну из $\binom{n/2}{k/2}$ фраз словаря, которая подразумевалась при передаче его партнером. В таком подходе агенты используют при кодировании только собственные броски, не обращая внимания на то, как именно бросает свои камни партнер. Максимальное число сообщений, которое в принципе можно передать, составляет $\binom{n/2}{\left\lceil n/4\right\rceil}$.
Большее число сообщений можно передавать, заранее договорившись о такой схеме передачи, при которой для идентификации переданного сообщения используются не только броски партнера, но и свои собственные. Именно такой подход использует мой алгоритм передачи сообщений. Картинка из предыдущего моего сообщения в этой теме иллюстрирует тот факт, что при таком подходе наибольшее число сообщений, которое может передавать каждый из агентов, может составлять больше $\binom{n/2}{\left\lceil n/4\right\rceil}$. Правильно ли я понимаю, что картинка требует дополнительных пояснений?

[TOTAL]

EtCetera в сообщении #753034 писал(а):

Правильно ли я понимаю, что картинка требует дополнительных пояснений?

Спасибо, EtCetera, я понял, что набор сообщений, который я ожидаю от партнера, зависит от того, сколько камней я бросил первым броском. И т.д.

[Pavlovsky]

Существует 2^26 способов бросания 26 камней. То есть теоретически можно закодировать числа от 1 до 67108864. То есть каждый мегамозг может передать число от 1 до Y. Где Y+Y^2=67108864.

[nikvic]

EtCetera в сообщении #753034 писал(а):

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

Геометрически каждый сеанс связи может быть представлен как ломаная с шагами вверх и вправо.
Было бы интересно понять, как устроены "траектории" сеансов для заданных объёмов передачи.

[TOTAL]

Pavlovsky в сообщении #753160 писал(а):

Существует 2^26 способов бросания 26 камней.

Сколько существует способов бросания 2 камней?

[Pavlovsky]

Два. (2), (1,1)
Ой ошибся. Существует 2^25=33554432 способов бросания 26 камней.

[EtCetera]

Pavlovsky
По Вашей формуле выходит, что при наличии $n=5$ камней агенты могут передать по 3 сообщения, не так ли? Если так, то не могли бы Вы продемонстрировать, каким образом им это удается?

[worm2]

Наконец-то и до меня дошло, какая здесь зависимость.
Подтверждаю таблицу EtCetera. По крайней мере, для $n=17$ у меня тоже получилось (119, 119), а для $n=26$ — (2537, 2535) и (2535, 2536). Ну и $n=30$ совпало.
Подробности будут позже.

[worm2]

Обозначим через $f_n(m)$ ($n\in\mathbb{Z}_+$, $m\in\mathbb{N}$) максимальное количество сообщений, которое бросающий первым может передать с помощью $n$ имеющихся в его распоряжении камней при условии, что второму обеспечивается возможность передачи не менее $m$ сообщений. В обозначениях таблицы EtCetera $f_n(m)=k$ эквивалентно тому, что среди всевозможных пар перечисленных в 3-м столбце $n$-й строки таблицы присутствует пара (k,m).

Я, в отличие от EtCetera, интерпретирую как ноль камней, так и один камень, как возможность передачи не нуля, а одного сообщения (поскольку логарифм от этой единицы даёт правильное значение — ноль бит информации, которое можно передать). Однако если второму бросающему никак нельзя дать возможность передать $m$ сообщений, если первому досталось $n$ камней, то $f_n(m)=0$. Поэтому в моих обозначениях $f_0(1)=1$, $f_1(1)=1$, а для $m>1$ будет $f_0(m)=f_1(m)=0$.

Пусть мы хотим вычислить $f_n(m)$, где $n>1$, для всех $m$. Первый может бросить $i$ камней если и только если $f_{n-i}(k)\geqslant m$ для какого-то $k$ (поскольку, очевидно, $f_n(k)$ не убывает с ростом $k$ при фиксированном $n$, то достаточно потребовать $f_{n-i}(1)\geqslant m$).

Итак, пусть первый кинул $i$ камней (разрешённое количество). Зададимся вопросом: сколько максимально сообщений первый сможет передать после ответного броска второго? Иными словами, какое максимальное количество сообщений второй может позволить передать первому при своём следующем ходе (не забывая при этом о своих $m$ сообщениях)? Ответ на это, по определению функции $f$, таков: максимальное $k$, при котором $f_{n-i}(k)$ всё ещё не меньше $m$, или $\max\limits_{f_{n-i}(k)\geqslant m}k$.

Суммируя варианты передачи по всем разрешённым $i$, имеем полное количество сообщений, которое может передать первый при указанном ограничении:

$$f_n(m)=\sum\limits_{i=1}^n\max\limits_{f_{n-i}(k)\geqslant m}k$$

Этому выражению можно придать другую форму:

$$f_n(m)=\#\{(j,k)|j<n,f_j(k)\geqslant m\}$$

Если к этому добавить, что максимальное $m$, для которого $f_n(m)>0$, мы уже ранее вычислили как $F_n$ ($n$-й член последовательности Фибоначчи), то остаётся только считать. Искомое количество сообщений для $n$ камней будет равно

$$\max\limits_{m=1}^{F_n}\min\{m, f_n(m)\}$$

Вот таблица первых $f_n(m)$:

$$\begin{array}{|l|r|r|r|r|r|r|r|r|r|} \hline m\diagdown n&0&1&2&3&4&5&6&7&8\\ \hline 1&1&1&2&3&5&8&13&21&34\\ \hline 2&&&&1&2&4&7&12&20\\ \hline 3&&&&&1&2&4&8&15\\ \hline 4&&&&&&1&3&6&11\\ \hline 5&&&&&&1&2&4&8\\ \hline 6&&&&&&&1&3&7\\ \hline 7&&&&&&&1&3&6\\ \hline 8&&&&&&&1&2&5\\ \hline 9&&&&&&&&1&3\\ \hline 10&&&&&&&&1&3\\ \hline 11&&&&&&&&1&3\\ \hline 12&&&&&&&&1&3\\ \hline 13&&&&&&&&1&2\\ \hline 14&&&&&&&&&1\\ \hline 15&&&&&&&&&1\\ \hline \dots&\dots&\dots&\dots&\dots&\dots&\dots&\dots&\dots&1\\ \hline 21&&&&&&&&&1\\ \hline \end{array}$$

-- Пт авг 09, 2013 12:41:53 --

EtCetera это всё уже писал, даже обозначения почти те же. Только я его сначала не понял

[nikvic]

EtCetera в сообщении #751959 писал(а):

Вот что она выдала:...

Первое разночтение у нас с Вами - строка 46, столбец 45. Вам хватает 14 камней, мне нужно 15.
Ваша таблица не захватывает это место. На какие слагаемые Первый разбивает свои 46 сообщений?

[Deggial]

Pavlovsky в сообщении #753160 писал(а):

Существует 2^26 способов бросания 26 камней. То есть теоретически можно закодировать числа от 1 до 67108864. То есть каждый мегамозг может передать число от 1 до Y. Где Y+Y^2=67108864.

Pavlovsky, замечание за неоформление формул $\TeX$ом