2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4  След.
 
 Re: Каменные биты.
Сообщение03.08.2013, 16:40 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Каменные биты.
Сообщение03.08.2013, 16:48 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Каменные биты.
Сообщение03.08.2013, 17:03 
Заслуженный участник


04/05/09
4596
Пожалуйста:
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)

 Профиль  
                  
 
 Re: Каменные биты.
Сообщение03.08.2013, 18:48 
Заслуженный участник


28/04/09
1933
Можно сделать и так, чтобы первый мог выбрать из 4 вариантов, а второй $\text{---}$ из 3:
Изображение
Но 6 не интересно, лучше 8 рассмотреть. Или 7.

 Профиль  
                  
 
 Re: Каменные биты.
Сообщение04.08.2013, 22:51 
Заслуженный участник


28/04/09
1933
Набросал программку по подсчету наибольшего количества передаваемых сообщений ($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}}$ или близкий к нему результат.

 Профиль  
                  
 
 Re: Каменные биты.
Сообщение05.08.2013, 07:54 
Заслуженный участник
Аватара пользователя


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

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

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

 Профиль  
                  
 
 Re: Каменные биты.
Сообщение05.08.2013, 09:43 
Заслуженный участник
Аватара пользователя


06/04/10
3152
worm2 в сообщении #752041 писал(а):
Собственно, как и в $m_{II}$, в $m_I$ должна быть последовательность Фибоначчи.

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

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

EtCetera в сообщении #751959 писал(а):
Набросал программку

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

 Профиль  
                  
 
 Re: Каменные биты.
Сообщение06.08.2013, 00:39 
Заслуженный участник


28/04/09
1933
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...
Как оно возникло?
Понятия не имею. Поздновато как-то оно возникло. Алгоритм у меня очень простой, возможно, я чего-то не учел.

 Профиль  
                  
 
 Re: Каменные биты.
Сообщение06.08.2013, 13:40 
Заслуженный участник
Аватара пользователя


06/04/10
3152
EtCetera в сообщении #752367 писал(а):
Тут нюанс (который на расчеты вроде бы не влияет). В программе я считаю, что 0 брошенных камней соответствует нулю переданных сообщений.

Пожалуй, естественнее считать, что по одному сообщению.
EtCetera в сообщении #752367 писал(а):
Понятия не имею. Поздновато как-то оно возникло. Алгоритм у меня очень простой, возможно, я чего-то не учел.

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

 Профиль  
                  
 
 Re: Каменные биты.
Сообщение06.08.2013, 15:46 
Заслуженный участник


28/04/09
1933
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$.

 Профиль  
                  
 
 Re: Каменные биты.
Сообщение06.08.2013, 16:30 
Заслуженный участник
Аватара пользователя


23/08/07
5502
Нов-ск
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$ сообщений?

 Профиль  
                  
 
 Re: Каменные биты.
Сообщение06.08.2013, 16:52 
Заслуженный участник
Аватара пользователя


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

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

 Профиль  
                  
 
 Re: Каменные биты.
Сообщение06.08.2013, 18:46 
Заслуженный участник


28/04/09
1933
nikvic
nikvic в сообщении #752565 писал(а):
У Вас две функции с индексом и аргументом - итого пара двуместных функций. Каков их "смысл"?
EtCetera в сообщении #752367 писал(а):
$f_n(s)$ $\text{---}$ зависимость числа наибольшего числа сообщений, передаваемых первым агентом, от числа сообщений, передаваемых вторым агентом в этом же сеансе связи (при наличии $n$ средств связи)
Т.е. это количество сообщений, которое может передать первый агент при наличии $n$ камней, если второй агент обязан передать $s$ сообщений. Соответственно, $s_n(f)$ $\text{---}$ это наибольшее число сообщений, которое может передать второй агент при наличии $n$ камней, если первый агент обязан передать $f$ камней ($f$ $\text{---}$ от first, $s$ $\text{---}$ от second :wink: ).
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}$

 Профиль  
                  
 
 Re: Каменные биты.
Сообщение06.08.2013, 20:07 
Заслуженный участник
Аватара пользователя


06/04/10
3152
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.

 Профиль  
                  
 
 Re: Каменные биты.
Сообщение06.08.2013, 20:47 
Заслуженный участник


28/04/09
1933
TOTAL
TOTAL в сообщении #752557 писал(а):
Нельзя ли не формулы писать, а рассказать, как они смогли передать по $2500$ сообщений?
Про 2500 рассказать, наверное, не смогу (там слишком ветвистое дерево возможных вариантов передачи сообщений). Но могу нарисовать пример для $n=10$ камней (для этого числа камней искомое количество сообщений $m_\text{I,II}=12>10=\binom{5}{3}$, получаемых по способу venco):
Изображение
На этой картинке показано, каким образом первый агент может передать 13 сообщений (второй при этом передает 12 сообщений). Конфигурация дерева вариантов на картинке немного не соответствует данным, полученным с помощью моей программы (это сделано для того, чтобы картинка была покомпактнее).
Upd: поправил картинку.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 55 ]  На страницу Пред.  1, 2, 3, 4  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: gris


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group