2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу 1, 2, 3, 4  След.
 
 Каменные биты.
Сообщение01.08.2013, 16:08 
Заслуженный участник
Аватара пользователя


06/04/10
3152
Не уверен, что задача не разбиралась.
Каждому из агентов необходимо передать другому "шифр" незаметно для наружки.

На набережной лежит кучка из 26 камней, и строго по очереди они начинают кидать камни в воду.
За раз бросают как минимум один, и расходятся, когда камней больше не остаётся.
Смогут ли мегамозги обменяться информацией, если шифр - любое число от 1 до 1700? А от 1 до 2500?

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


03/12/11
640
Україна
У меня получилось, что смогут, даже если шифр - любое число от $1$ до $2^{12}=4096$.

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


06/04/10
3152
Без как нет ответа.

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


04/05/09
4582
До 1700 - довольно легко, точнее даже до 1716.

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


06/04/10
3152
venco в сообщении #751138 писал(а):
До 1700 - довольно легко, точнее даже до 1716.

Факт.
А что там дальше? :roll:

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


04/05/09
4582
Второй при этом может передать 2508. А первый, по прежнему 1716.

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


06/04/10
3152
Неясно.
Как?

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


04/05/09
4582
Второму можно на один раз меньше бросить.

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


06/04/10
3152
Раскройте карты :lol:

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


04/05/09
4582
Каждый формирует семь бросков используя максимум 13 камней - это $C^{13}_7=1716$ комбинаций. Второй может свои 13 камней использовать за шесть бросков, добавив к своим комбинациям ещё $C^{12}_5=792$, получив в сумме 2508 комбинаций. Первый этого сделать не может, т.к. если второму нужно 7 бросков, то первому придётся бросить лишний камень в 7-ой раз, и второму на последний бросок достанется на один камень меньше.

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


06/04/10
3152
venco в сообщении #751350 писал(а):
Второй может свои 13 камней использовать за шесть бросков, добавив к своим комбинациям ещё ....

Гм, а как первый сможет узнать о таком решении второго?

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


04/05/09
4582
Второй шестым броском использовал свой 13-ый камень.

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


06/04/10
3152
Второй не может бросать 5 раз, если первый делает 7 бросков - он будет знать только сумму 6-го и седьмого у первого.

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


04/05/09
4582
5 не может, а 6 может.

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


06/04/10
3152
Тогда и получается, по схеме 7 и 6 бросков, по 1716 сообщений.
Но это далеко от рекорда 2526...

Реально эта задача либо для искусных комбинаторщиков, либо для алгоритмистов.

Так что поставлю задачу иначе.
Пусть первому нужно передать одно из Х сообщений, второму - одно из У.
Какое минимальное число камней понадобится?

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

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



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

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


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

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