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

[nikvic]

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

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

[Dave]

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

[nikvic]

Без как нет ответа.

[venco]

До 1700 - довольно легко, точнее даже до 1716.

[nikvic]

venco в сообщении #751138 писал(а):

До 1700 - довольно легко, точнее даже до 1716.

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

[venco]

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

[nikvic]

Неясно.
Как?

[venco]

Второму можно на один раз меньше бросить.

[nikvic]

Раскройте карты

[venco]

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

[nikvic]

venco в сообщении #751350 писал(а):

Второй может свои 13 камней использовать за шесть бросков, добавив к своим комбинациям ещё ....

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

[venco]

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

[nikvic]

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

[venco]

5 не может, а 6 может.

[nikvic]

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

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

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