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

[venco]

1716 сообщений - это 7 бросков в пределах 13 камней. 2508 - это если добавить ещё 6 бросков из ровно 13 камней.

[nikvic]

Это уже было, как и моё возражение.
Разберите "на пальцах" случай 10 или даже 6 камней.

[venco]

Пожалуйста:
6 камней, каждому доступно 3 камня, максимум 2 броска.
У первого - $C^3_2=3$ варианта: (1,1),(1,2),(2,1)
У второго - $C^3_2+C^2_0=4$ варианта: (1,1),(1,2),(2,1),(3)

[EtCetera]

Можно сделать и так, чтобы первый мог выбрать из 4 вариантов, а второй $\text{---}$ из 3:

Но 6 не интересно, лучше 8 рассмотреть. Или 7.

[EtCetera]

Набросал программку по подсчету наибольшего количества передаваемых сообщений ($m$) в зависимости от числа камней ($n$). Вот что она выдала:
\begin{array}{|r|r|l|r|r|} \hline n & m_{\text{I,II}} & \text{Пары (I, II)} & m_{\text{I}} & m_{\text{II}} \\ \hline 1 & 0 & \text{---} & 1 & 0 \\ \hline 2 & 1 & (1, 1) & 2 & 1 \\ \hline 3 & 1 & (2, 1), (1, 2) & 3 & 2 \\ \hline 4 & 2 & (2, 2), (1, 3) & 4 & 3 \\ \hline 5 & 2 & (4, 2), (2, 3) & 7 & 5 \\ \hline 6 & 3 & (4, 3), (3, 4) & 12 & 8 \\ \hline 7 & 4 & (6, 4), (4, 5) & 20 & 13 \\ \hline 8 & 6 & (7, 6), (6, 7) & 33 & 21 \\ \hline 9 & 8 & (10, 8), (7, 9) & 54 & 34 \\ \hline 10 & 12 & (13, 12), (11, 13) & 88 & 55 \\ \hline 11 & 16 & (16, 16), (15, 17) & 143 & 89 \\ \hline 12 & 23 & (24, 23), (22, 24) & 232 & 144 \\ \hline 13 & 31 & (31, 31), (31, 32) & 376 & 233 \\ \hline 14 & 45 & (46, 45), (45, 46) & 609 & 377 \\ \hline 15 & 61 & (61, 61), (59, 62) & 986 & 610 \\ \hline 16 & 87 & (88, 87), (87, 88) & 1596 & 987 \\ \hline 17 & 119 & (119, 119), (118, 120) & 2583 & 1597 \\ \hline 18 & 171 & (171, 171), (171, 172) & 4180 & 2584 \\ \hline 19 & 233 & (234, 233), (233, 234) & 6764 & 4181 \\ \hline 20 & 334 & (334, 334), (334, 335) & 10945 & 6765 \\ \hline 21 & 459 & (460, 459), (458, 460) & 17710 & 10946 \\ \hline 22 & 655 & (656, 655), (655, 656) & 28656 & 17711 \\ \hline 23 & 904 & (906, 904), (904, 905) & 46367 & 28657 \\ \hline 24 & 1288 & (1290, 1288), (1287, 1289) & 75024 & 46368 \\ \hline 25 & 1782 & (1782, 1782), (1781, 1783) & 121392 & 75025 \\ \hline 26 & 2535 & (2537, 2535), (2535, 2536) & 196417 & 121393 \\ \hline 27 & 3517 & (3519, 3517), (3517, 3518) & 317810 & 196418 \\ \hline 28 & 4995 & (4997, 4995), (4994, 4996) & 514228 & 317811 \\ \hline 29 & 6935 & (6936, 6935), (6935, 6936) & 832039 & 514229 \\ \hline 30 & 9848 & (9848, 9848), (9848, 9849) & 1346268 & 832040 \\ \hline \end{array}
Здесь $m_{\text{I,II}}$ $\text{---}$ наибольшее число сообщений, которое могут передать и первый, и второй агенты. $m_{\text{I}}$ и $m_{\text{II}}$ $\text{---}$ максимальное количество сообщений, которое может передать соответствующий агент вообще (к задаче не относится). В среднем столбце приведены пары чисел, дающие $m_{\text{I,II}}$ или близкий к нему результат.

[worm2]

EtCetera, я понял далеко не всё. Но кое к чему уже могу придраться.
$m_I=5$ для $n=4$. Первым ходом можно кинуть от 1 до 4 камней — 4 сообщения. Но если первым кинут один камень, второй кидает также один (он только "слушает"), и вторым ходом возможны два варианта.

-- Пн авг 05, 2013 10:08:23 --

Собственно, как и в $m_{II}$, в $m_I$ должна быть последовательность Фибоначчи.

[nikvic]

worm2 в сообщении #752041 писал(а):

Собственно, как и в $m_{II}$, в $m_I$ должна быть последовательность Фибоначчи.

Не совсем так: они отличаются на один. Если слушает первый, то один камень "пропадает" для перемены первый/второй.

-- Пн авг 05, 2013 10:47:48 --

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

Набросал программку

Вижу отличие, начиная с 17 камней. У Вас - 119, у меня - 118.
Да и окончательно - мои 2526 против Ваших 2535...
Как оно возникло?

[EtCetera]

worm2

worm2 в сообщении #752041 писал(а):

$m_I=5$ для $n=4$. Первым ходом можно кинуть от 1 до 4 камней — 4 сообщения. Но если первым кинут один камень, второй кидает также один (он только "слушает"), и вторым ходом возможны два варианта.

Тут нюанс (который на расчеты вроде бы не влияет). В программе я считаю, что 0 брошенных камней соответствует нулю переданных сообщений. Соответственно, если первый кинет 4 камня, то второй $\text{---}$ только 0, поэтому он не будет иметь права кинуть 1 камень в тот момент, когда первый тоже кидает 1 камень. Таким образом, я принудительно выставляю $f_n(0)=n$, где $f_n(s)$ $\text{---}$ зависимость числа наибольшего числа сообщений, передаваемых первым агентом, от числа сообщений, передаваемых вторым агентом в этом же сеансе связи (при наличии $n$ средств связи). Поэтому $\max\limits_s f_4(s)=f_4(1)=4$. Однако в дальнейшем все равно используется на единицу большее значение, т.е. $s_5(1)=5$ (поскольку первый агент свой единственный камень бросает с самого начала, и больше ему не нужно).
Впрочем, к задаче это не имеет практически никакого отношения (вывод последних двух столбцов был явной ошибкой ).

nikvic

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

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

Набросал программку

Вижу отличие, начиная с 17 камней. У Вас - 119, у меня - 118.
Да и окончательно - мои 2526 против Ваших 2535...
Как оно возникло?

Понятия не имею. Поздновато как-то оно возникло. Алгоритм у меня очень простой, возможно, я чего-то не учел.

[nikvic]

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

Тут нюанс (который на расчеты вроде бы не влияет). В программе я считаю, что 0 брошенных камней соответствует нулю переданных сообщений.

Пожалуй, естественнее считать, что по одному сообщению.

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

Понятия не имею. Поздновато как-то оно возникло. Алгоритм у меня очень простой, возможно, я чего-то не учел.

Не могли бы Вы его описать на общедоступном языке?

[EtCetera]

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

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

Тут нюанс (который на расчеты вроде бы не влияет). В программе я считаю, что 0 брошенных камней соответствует нулю переданных сообщений.

Пожалуй, естественнее считать, что по одному сообщению.

Да, разумеется.

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

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

Понятия не имею. Поздновато как-то оно возникло. Алгоритм у меня очень простой, возможно, я чего-то не учел.

Не могли бы Вы его описать на общедоступном языке?

С учетом Вашего замечания его можно изложить невероятно просто.
Положим $f_1(1)=1$. Для любого $n>1$ найдем $f_n(k)$ так: $f_n(k)=f_{n-1}(k)+s_{n-1}(k)$, $1\le k\le \max\limits_s f_{n-1}(s)$. Здесь полагается, что $f_n(s)=0$ при $s>\max\limits_f s_n(f)$. Найти $s_n(f)$, зная $f_n(s)$, несложно. Искомое значение находится так: $m_\text{I,II}(n)=\max\limits_{f_n(s)\ge s}s$.

[TOTAL]

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

Положим $f_1(1)=1$. Для любого $n>1$ найдем $f_n(k)$ так: $f_n(k)=f_{n-1}(k)+s_{n-1}(k)$, $1\le k\le \max\limits_s f_{n-1}(s)$. Здесь полагается, что $f_n(s)=0$ при $s>\max\limits_f s_n(f)$. Найти $s_n(f)$, зная $f_n(s)$, несложно. Искомое значение находится так: $m_\text{I,II}(n)=\max\limits_{f_n(s)\ge s}s$.

Нельзя ли не формулы писать, а рассказать, как они смогли передать по $2500$ сообщений?

[nikvic]

Туповат я стал...
У Вас две функции с индексом и аргументом - итого пара двуместных функций. Каков их "смысл"?

У меня - одна, по числу сообщений Первого и числу сообщений Второго выдаёт минимальное достаточное число камней.
Вот её фрагмент (число сообщений Первого - номер строки) http://www.ljplus.ru/img4/n/i/nik_vic/shifr1.GIF

[EtCetera]

nikvic

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

У Вас две функции с индексом и аргументом - итого пара двуместных функций. Каков их "смысл"?

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

$f_n(s)$ $\text{---}$ зависимость числа наибольшего числа сообщений, передаваемых первым агентом, от числа сообщений, передаваемых вторым агентом в этом же сеансе связи (при наличии $n$ средств связи)

Т.е. это количество сообщений, которое может передать первый агент при наличии $n$ камней, если второй агент обязан передать $s$ сообщений. Соответственно, $s_n(f)$ $\text{---}$ это наибольшее число сообщений, которое может передать второй агент при наличии $n$ камней, если первый агент обязан передать $f$ камней ($f$ $\text{---}$ от first, $s$ $\text{---}$ от second ).

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

У меня - одна, по числу сообщений Первого и числу сообщений Второго выдаёт минимальное достаточное число камней.

Т.е. в моих обозначениях у Вас функция $n=n(f,s)$:
$\begin{array}{|r||r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|} \hline & 1& 2& 3& 4& 5& 6& 7& 8& 9&10&11&12&13&14&15&16&17&18&19&20\\ \hline\hline 1& 1& 3& 4& 5& 5& 6& 6& 6& 7& 7& 7& 7& 7& 8& 8& 8& 8& 8& 8& 8\\ \hline 2& 2& 4& 5& 6& 6& 7& 7& 7& 8& 8& 8& 8& 8& 9& 9& 9& 9& 9& 9& 9\\ \hline 3& 3& 5& 6& 6& 7& 7& 7& 8& 8& 8& 8& 8& 9& 9& 9& 9& 9& 9& 9& 9\\ \hline 4& 4& 5& 6& 7& 7& 8& 8& 8& 9& 9& 9& 9& 9& 9& 9&10&10&10&10&10\\ \hline 5& 4& 6& 7& 7& 8& 8& 8& 8& 9& 9& 9& 9& 9&10&10&10&10&10&10&10\\ \hline 6& 5& 6& 7& 7& 8& 8& 8& 9& 9& 9& 9& 9&10&10&10&10&10&10&10&10\\ \hline 7& 5& 6& 7& 8& 8& 8& 9& 9& 9& 9& 9&10&10&10&10&10&10&10&10&11\\ \hline 8& 5& 7& 7& 8& 8& 9& 9& 9&10&10&10&10&10&10&10&10&11&11&11&11\\ \hline 9& 6& 7& 8& 8& 9& 9& 9& 9&10&10&10&10&10&10&10&11&11&11&11&11\\ \hline 10& 6& 7& 8& 8& 9& 9& 9& 9&10&10&10&10&10&10&11&11&11&11&11&11\\ \hline 11& 6& 7& 8& 8& 9& 9& 9&10&10&10&10&10&10&11&11&11&11&11&11&11\\ \hline 12& 6& 7& 8& 9& 9& 9& 9&10&10&10&10&10&11&11&11&11&11&11&11&11\\ \hline 13& 6& 8& 8& 9& 9& 9&10&10&10&10&10&10&11&11&11&11&11&11&11&11\\ \hline 14& 7& 8& 8& 9& 9& 9&10&10&10&10&10&11&11&11&11&11&11&11&11&12\\ \hline 15& 7& 8& 8& 9& 9&10&10&10&10&10&11&11&11&11&11&11&11&11&12&12\\ \hline 16& 7& 8& 9& 9& 9&10&10&10&11&11&11&11&11&11&11&11&12&12&12&12\\ \hline 17& 7& 8& 9& 9&10&10&10&10&11&11&11&11&11&11&11&12&12&12&12&12\\ \hline 18& 7& 8& 9& 9&10&10&10&10&11&11&11&11&11&11&11&12&12&12&12&12\\ \hline 19& 7& 8& 9& 9&10&10&10&11&11&11&11&11&11&11&11&12&12&12&12&12\\ \hline 20& 7& 8& 9&10&10&10&10&11&11&11&11&11&11&11&12&12&12&12&12&12\\ \hline \end{array}$

[nikvic]

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

Нельзя ли не формулы писать, а рассказать, как они смогли передать по 2500 сообщений?

Давайте попробуем на меньшем числе - для 11 камней можно передать 16х16 сообщений. Простая идея, когда каждому даётся равное число камней, явно не проходит.
Смотрите на картинку EtCetera.
Первый делит свои 16 на 5 групп, 16=1+1+3+3+8 кидает 5,4..1 камней: чем больше слагаемое, тем меньше камней. Это разбиение описывается в 16-й строке, которая как бы уже вычислена до 15-го столбца. Роль первого переходит ко второму, и он знает, какие (и сколько) сообщения в выделенной (числом брошенных камней) группе первого.
Пусть Первый бросил два камня. Новый Первый (бывший Второй) оказывается в ситуации "16 моих, 3 чужих" - и делит свои сообщения, используя начало строчки 3: 16=1+1+2+3+5+4.

"База" индукции - минимальность 2-х камней, когда Первому надо передать одно из двух сообщений, а Второму сказать нечего (одно сообщение). Замечу, что одно и одно не используется - отсюда разночтения для такого случая.

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

Если ни то, ни другое условие не выполняются, Первый разбивает свой "блокнот" на подмножества с минимизацией, как у EtCetera.

[EtCetera]

TOTAL

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

Нельзя ли не формулы писать, а рассказать, как они смогли передать по $2500$ сообщений?

Про 2500 рассказать, наверное, не смогу (там слишком ветвистое дерево возможных вариантов передачи сообщений). Но могу нарисовать пример для $n=10$ камней (для этого числа камней искомое количество сообщений $m_\text{I,II}=12>10=\binom{5}{3}$, получаемых по способу venco):

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