2014 dxdy logo

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

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




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


04/05/09
4586
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
4586
Пожалуйста:
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
3106
Уфа
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
5480
Нов-ск
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, Супермодераторы



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

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