Добрый день.
За новогодним столом бывает здорово поиграть в какую-нибудь весёлую игру. Например, можно устроить аукцион, в котором побеждает тот, кто сможет закодировать пару чисел из наибольшего диапазона. Здорово звучит?
Цитата из книги «Что делать, если вас не считают занудой»: «Встретив филологов или историков, расскажите им анекдот про марсианина. Обязательно объясните им, почему это смешно. Убедите их поделиться этим анекдотом с друзьями. Проконтролируйте, чтобы они правильно объяснили своим друзьям, почему этот анекдот смешной».
Но возвращаемся к нашему аукциону. Недавно Константин Кноп напомнил чудесную формулировку (осторожно, там в комментариях сказано уже слишком много!):
Секретный код к любому из сейфов ФБР — это натуральное число от 1 до 1700. Двое шпионов узнали по одному коду каждый и решили обменяться информацией. Согласовав заранее свои действия, они встретились на берегу реки возле кучи из 26 камней. Сначала первый шпион кинул в воду несколько камней, потом - второй, потом опять первый и так далее до тех пор, пока камни не кончились. После этого шпионы разошлись. Каким образом могла быть передана информация? (Шпионы не сказали друг другу ни слова.) (Авторы - Дмитрий Челкак и Константин Кохась, СПбМО 2002, отборочный тур, 10 класс)
Мне в ней не нравятся две вещи:
- наших разведчиков назвали шпионами,
- задана граница 1700.
Поэтому давайте чуть-чуть переформулируем задачу:
- два человека знают целые числа из диапазона от 1 до N,
- они поочерёдно пишут на доске положительные целые числа, пока сумма всех записанных чисел не станет равна 26,
- давным давно они учились в одном классе, поэтому заранее договорились, как кодировать данные.
Вопросы:
1. Как они могли бы обменяться парой чисел при N = 1700?
2. Для какого максимального N вы можете придумать способ кодирования?
Эта задачка хороша тем, что когда кажется, что «ну уж дальше N увеличить невозможно», обязательно находится кто-то, кто опять смог поднять верхнюю границу :)
(Кстати, не так давно мы решали другую забавную школьную задачку, имеющую отношение к теории кодирования)
Хорошего начала предпраздничной недели!
26 дек. 2011 г.
Аукцион с камнями
Темы:
математика
Подписаться на:
Комментарии к сообщению (Atom)
Понравилась заметка? Подпишитесь на
RSS-feed или email-рассылку.
Хотите поделиться ссылкой с другими? Добавьте в закладки:
Есть вопросы или предложения? Пишите письма на адрес mytribune АТ yandex.ru.
С уважением,
Илья Весенний
RSS-feed или email-рассылку.Хотите поделиться ссылкой с другими? Добавьте в закладки:
Есть вопросы или предложения? Пишите письма на адрес mytribune АТ yandex.ru.
С уважением,
Илья Весенний
Они могли бы использовать двоичный код.
ОтветитьУдалитьТогда, если предоставиь каждому равные возможности, т.е. по 13 разрядов, то можно записать числа от 0 до 8191.
Akademic, идея понятна, но у них нет 13 разрядов.
ОтветитьУдалитьСразу попытаюсь вбросить оценку сверх на N во втором вопросе: 5792.
ОтветитьУдалитьВсего возможных _ситуаций_ 2^25 (в каждом из 25 междукамней можно сделать либо не сделать смену хода), а значит совместно они могли закодировать число не более чем 2^25. Так как не должно существовать двух пар чисел, для которых случится одна и та же ситуация, то N <= floor(sqrt(2 ^ 12.5)) = 5792
Daniel Burdakov,
ОтветитьУдалитьверно, различных способов кидать камни у них 2^25=33554432. Так мы посчитали количество информации, которое можно передать таким образом (мы ранее уже делали подобные упражнения). Поэтому теоретический максимум N составляет целая часть корня из этой величины, т.е. 5792.
Разве нету 13 разрядов?
ОтветитьУдалитьПо такой системе: Сначала выписываем младший разряд где выставлен бит, потом номер разряда следующего бита - номер разряда первого выставленного бита.
Для 4160 (1000001000000) будет написано:
6;
6;
Пожалуй, если можно кинуть 0 камней даже 14 бит поместится.
Уважаемый аноним,
ОтветитьУдалитья не в полной мере понимаю, как использовать Ваш способ кодирования в этой задаче.
Пожалуйста, объясните подробнее. Отмечу только пару моментов:
1) По условию кидать можно только положительное количество камней, поэтому 0 нельзя,
2) Число бросков у обоих участников должно быть одинаковым или отличаться на единицу (потому что они кидают камни поочерёдно, пока те не кончатся).
Уважаемый Илья,
ОтветитьУдалитьЯ не осознал влияние второго условия, свое невнятно описанное решение снимаю как неверное.
"Число бросков у обоих участников должно быть одинаковым или отличаться на единицу (потому что они кидают камни поочерёдно, пока те не кончатся). "
ОтветитьУдалитьВы смешали две задачи - оригинальную (где такого условия и близко не было) и свою (возможно, вы свое условие недописали)? Если они поочередно пишут положительные числа, то нет проблемы написать (А и Б - люди) А1, Б3, А7, Б4 ... А если они поочередно кидают камни, то тоже непонятно, откуда ограничение.
Есть способ закодировать числа от 1 до 1716.
ОтветитьУдалитьРазведчики решили поделить камни по-честному и каждый будет бросать половину камней 26/2=13.
Количество способов записать число k в виде суммы n чисел равно binom(k-1,n-1) == количество информации передаваемой за n-ходов.
Доп. ограничение на кол-во ходов: n2 = n1 или n1-1
В итоге:
1. первый кидает 13 камней за 7 или 8 ходов (792+924=1716 вариантов)
2. второй кидает 13 камней за (6 или 7) или (7 или 8) ходов (792+924=1716 вариантов в обоих случаях)
PS binom(13-1,n-1) для n=1..13
1, 12, 66, 220, 495, 792, 924, 792, 495, 220, 66, 12, 1
Дополнение.
ОтветитьУдалитьвыше немного не ясно как они узнают кто сколько ходов хочет сделать.
Более точный вариант:
1. Оба делают по 7 или 8 ходов.
2. Если первый делает 8, то второй 7 или 8, как обычно.
3. Если первый делает 7, а второму нужно 8, то последний ход второго делает первый, те выкидывает оставшиеся камни.
(это не вносит неопределенность, тк первый уже выбросил свои 13 камней)
Eugene Mayevski, Вы спрашиваете «Вы смешали две задачи - оригинальную (где такого условия и близко не было) и свою (возможно, вы свое условие недописали)?», как будто в заметке предложены две разные задачи. Это одна и та же задача, просто сформулированная двумя разными способами (потому что одни людям удобнее и интереснее мыслить в терминах камней, а другим - в терминах чисел на доске).
ОтветитьУдалитьВ оригинальной задаче сказано, что два человека поочерёдно бросают горсти камней в пруд (т.е. бросают как минимум один камень, после чего обязательно передают ход второму человеку). В моей формулировке они пишут числа (количество брошенных камней), тоже обязательно положительные, тоже обязательно поочерёдно.
Я вёл речь именно о количестве чисел, которое каждый из них напишет (эти количества не могут отличаться больше, чем на один). Ну или о количестве бросков, которые они сделают (тоже должны совпадать или отличаться на один).
vayun,
отлично, для N=1716 решение предъявлено.
Но ясно же, что можно больше. Кто улучшит этот результат? :)
Каков шаг аукциона? Если 1, то у меня 1717 :-)
ОтветитьУдалитьДарья
Честно говоря, не понял при чем здесь
ОтветитьУдалить2^25, 5792, 1716. Объясните пожалуйста по подробнее. Желательно на примере.
Заметил что 26=3+5+7+11, а куда дальше идти непонятно. Возможно в направлении китайской теоремы.
Я думаю надо максимально полно использовать предыдущие шаги, сделанные "собеседником", т.е. чтобы шаг 1 собеседника 2 зависел от шага 1 собеседника 1.
Дарья,
ОтветитьУдалитьшаг аукциона не задан, поэтому 1 вполне подходит :)
Уважаемый аноним,
в одном комментарии Вы задали несколько больших вопросов, но не указали, как глубоко не понимаете ответы на них. Лучше задавать конкретные вопросы по поводу отдельных тонкостей, чем просить заново всё объяснить.
Краткие ответы:
1) 2^25 - это количество всех возможных способов бросать камни в пруд (Daniel Burdakov выше показал, почему именно столько). Соответственно, раз мы теоретически можем закодировать столько вариантов, то для максимально возможного N верно N*N <= 2^25. Ну а так как N - натуральное число, то там мы получаем оценку на N.
2) 5792 - это и есть максимальное теоретически возможное N, выше которого заведомо невозможно прыгнуть. Если Вам не ясно, как получены какие-то из этих чисел, то поясните, что именно не можете понять.
3) 1716 - это максимальное N, которое смог закодировать vayun. Он кратко объяснил, как сделал это. Мне кажется, что его ход мысли вполне естественен. Что именно надо пояснить подробнее в его идее? Я буду рад рассказать, но сперва задайте вопрос.
Максимально полно использовать предыдущие шаги - это хорошая идея. Именно так и можно увеличивать N.
Конкретный вопрос такой. Как описанным алгоритмом первый скажет "1658", а второй "118". Быть может на примере станет понятно. Если пример неудачный и не раскрывает сути, дайте на другом примере.
ОтветитьУдалитьЕсли по описанию алгоритма нужны вопросы, то пожалуйста.
ОтветитьУдалитьПрозвучало "Всего возможных _ситуаций_ 2^25 (в каждом из 25 междукамней можно сделать либо не сделать смену хода), ..."
Непонятно каким образом можно делать либо не делать смену хода (и что такое вообще смена хода), если ранее прозвучало что оба должны ходить ПООЧЕРЕДИ. Соответственно, если все остальные выкладки базируются на этом то и они автоматически непонятны.
У меня вопрос собственно не в том как цифры вывели, я это и сам смогу как только осознаю суть алгоритма. Извините что неправильно изначально сформулировал.
ОтветитьУдалитьУважаемый аноним, конкретный пример рассматривать не очень интересно, так как писанины много будет, а смысла мало. Давайте попробуем вникнуть в алгоритмы:
ОтветитьУдалить1) Фраза "Всего возможных _ситуаций_ 2^25 (в каждом из 25 междукамней можно сделать либо не сделать смену хода), ..." надо понимать следующим образом. Бросать группу камней можно так:
- получив ход, игрок бросает один камень (так как он обязан бросить положительное число камней),
- а после этого он несколько раз принимает решение, бросить ещё один камень или передать ход партнёру.
Выходит, после каждого камня могут быть два исхода, поэтому за 25 бросков (после первого, который можно сделать только одним способом) могут возникнуть 2^25 вариантов.
Т.е. по условию игроки поочерёдно бросают группы камней (непустые). Но это же можно описать как "игроки бросают камни один за другим, иногда передавай ход друг другу". И такое описание более удобно для подсчёта всех возможных способов бросить камни.
2) Что касается идеи решения vayun, то я всё ещё не знаю, что здесь стоит прокомментировать. Вроде бы достаточно ясно изложено. Конечно, можно расписать и подробнее, но я не хотел бы это делать по всему тексту, а предпочёл бы ограничиться пояснениями только к непонятным Вам фрагментам. Поэтому жду конкретных вопросов.
1. Вот теперь стало понятно, спасибо. Проще наверно так: Если ходом первого собеседника сказать "1", а ходом второго сказать "0", то всего возможно 2^25 различных фраз, состоящих из "1" и "0", длиной 26. Почему в 25 а не в 26 степени - потомучто фраза всегда начинается с "1" по условию. "Первый собеседник" и "второй собеседник" здесь означают "тот кто начал говорить первым" и "тот кто начал говорить вторым"
ОтветитьУдалитьНо я здесь не согласен с тем, что первым должен начинать говорить всегда "первый" собеседник. Если ввести вариацию - кто первым начинает вести диалог, то можно сообщить дополнительный бит информации, если вести речь о теоретическом пределе, хотя технически это наверно очень сложно, если вообще возможно.
Уважаемый аноним, Вы правы,
ОтветитьУдалитьесли разведчики заранее договорились, в каких ситуациях первый подходит к камням, а в каких второй, то можно упаковать ещё чуть-чуть информации. Это важный, но достаточно тонкий момент.
С переходм хода всё же не очень понятно. Если он добровольный, то это можно осуществить либо паузой, либо жестом. Других вариантов я не вижу. Но тогда возможен и бросок в ноль камней. :)
ОтветитьУдалитьЕсли нет, то имеется скорее обрыв счёта - он бросил камень, когда я бросил уже два.
Дада, я тоже это увидел. Каким образом второй собеседник понимает что уже его очередь ходить? Допустим это некий жест от первого собеседника либо слишком длинная пауза между бросками.
ОтветитьУдалитьНо тогда сразу же напрашивается вывод, что помимо "1" и "0", в тексте могут быть символы "p" - пасс. Т.е. кроме такого сообщения
101100010 возможно и такое
1p11000p0
а это резко увеличивает объем передаваемой информации.
sans17 и аноним, никаких пауз и жестов.
ОтветитьУдалитьПодошёл к кучке камней, набрал в руку несколько штук, бросил их в пруд, отошёл. После этого ход перешёл ко второму разведчику, если камни в кучке ещё остались.
Эта ситуация полностью эквивалентна следующей:
подошёл к доске, написал на ней положительное целое число так, чтобы сумма всех записанных чисел не превзошла 26, отошёл, тем самым передав ход.
Илья, Вы пишете:
ОтветитьУдалитьесли разведчики заранее договорились, в каких ситуациях первый подходит к камням, а в каких второй, то можно упаковать ещё чуть-чуть информации. Это важный, но достаточно тонкий момент.
Важность момента несомненна, но пока что больше беспокоит его тонкость. Одно дело, если они заренее договорились, что первым подходит конкретно Вася. При более сложных договоренностях, при встрече должна состояться какая-то процедура выбора первого, а следовательно, передача информации каким-то способом, не включающим кидание камней. Не противоречит ли это условию задачи?
Если возможно достаточно легитимно провести такую процедуру выбора первого, то 2508 реально.
Ну так подход к кучке (отход) и есть жест.
ОтветитьУдалитьВторой разведчик подходи к кучке, и сразу же отходит - типа передумал.
sans17, сто раз же уже сказали, что бросают камни поочерёдно: сначала один бросил сколько-то, потом второй, потом опять первый, потом опять второй. И в условии это написано, и в комментарии много раз разжевали. Нельзя получить ход, но потом ничего не бросить. Всегда надо бросить хотя бы один камень, а потом передать ход. Что непонятного-то?
ОтветитьУдалить4718
ОтветитьУдалить2535: https://plus.google.com/u/0/116477975871185858002/posts/NehYW4KSbs6
ОтветитьУдалитьМне думается, что все-таки возможно согласовать право первого хода, не нарушая правил. Они могли договориться, кто из них первым приближается к камням. При этом он может сразу начать бросать камни, либо дожидаться, когда приблизится второй и сделает свой первый ход. Во всяком случае, со стороны это будет выглядеть именно так, как описано в условии - сначала один кинул, затем другой, и так далее, не нарушая очередности.
ОтветитьУдалитьПри таком подходе, максимум, что пока удалось выжать - это 2683.
Подошел, отошел, попрыгал на одной ноге. Это все не соответствует задумке условия.
ОтветитьУдалитьЭто разведчики, им вообще не обязательно видеться. Они могут приезжать на берег реки и кидать камни из заранее заготовленной кучи с интервалом от дней до месяцев. Как в таком случае определить, что первый "подошел, но не стал сразу кидать"?
Тут вариант только один - заранее договориться кто кидает первый. В таком случае, приехал, посмотрел, если число камней изменилось - кидай, если нет - вернись через несколько дней.
Вот она разница.
ОтветитьУдалитьЕсли 1716 можно понять и оценить в уме, то чтобы проверить 2535 надо смотреть на программу.
Следующий этап - задача настолько закрученная, что нужна программа проверяющая правильность алгоритма?
Уважаемый Аноним,
ОтветитьУдалитьВ условии задачи сказано: "Согласовав заранее свои действия, они встретились на берегу реки". Впрочем, Вы предлагаете тоже вполне интересную модификацию задачи. При такой постановке я достиг 2092.
Собственно, основную идею решения озвучил vayun. Количество бросков можно увеличить и до 9, и до 10 (на 11 уже камней не хватает). В тех случаях, когда первый делает ход за второго, ему необязательно выбрасывать сразу все оставшиеся камни. Он кидает один камень, а второй разведчик уже сам докидывает остальные камни текущего хода. Только тут уже разбиения не совсем произвольные. При разбиении на 9 частей, 8-я часть должна содержать не менее двух камней. А при разбиении на 10 - и 8-я, и 9-я.
Sophist, а Вы расскажете, как достигли 4718?
Задачка замечательная. Для 1700 хватает и 25 камней, а 26 хватает максимально на 2526 значений 2-х шифров. Число 1700 - частный случай, общий - когда первому надо передать одно из "а" чисел, второму - одно из "в" чисел. Считается рекурсивно -
ОтветитьУдалитьЯсно, что К(1,1)=0.
В случае (1,в) первый кидает один камень - чтобы передать ход второму. Значит, К(1,с)=1+К(с,1).
Хитрее, когда а>1. Число а можно по-разному представить в виде суммы натуральных слагаемых, а=а1+а2+а3... Для каждого такого разбиения есть максимум среди 1+К(в,а1),2+К(в,а2),3+К(в,а3)... - и нужно выбрать разбиение, минимизирующее такой максимум. Ну и здесь нужно исхитриться обойтись без перебора ;)
nik_vic из ЖЖ.
В предположении, что один участник, после того как у другого уже кончились камни, может несколько раз подряд вставать со скамейки, подходить к кучке, делать броски, возвращаться назад на скамейку, получается сказать обоим любое число в диапазоне от 1 до 8191.
ОтветитьУдалитьЭто соответствует тому, что если на доске идут подряд числа и первые несколько нечетных чисел составляют сумму 13, то все остальные числа считаются четными и тоже составляют сумму 13, и наоборот с точностью до слов "четное", "нечетное".
По-моему данное предположение не противоречит условию задачи, поправьте если не так.
Уважаемый аноним,
ОтветитьУдалитьэто предположение противоречит условию (ведь каждый должен бросить хотя бы один камень перед тем, как передаст ход партнёру).
Да и вообще, что значит "у одного уже кончились камни", а "второй ещё бросает". Кучка-то одна. Поэтому, если в ней что-то есть, то очередной игрок должен что-то бросить (перед передачей хода). А если в ней уже ничего нет, то игра закончилась.
nik_vic,
можете подробнее расписать вычисления для случая a>1? (речь о том, как именно там можно исхитриться) Думаю, многим было бы интересно.
Sophist,
было бы интересно увидеть пояснения к Вашему решению.
Кто-нибудь сможет привести формальное описание методики обмена? Алгоритм или код на С, Pascal или VB?
ОтветитьУдалитьНи в одном описании решения не удалось разобраться.
chukchatel,
ОтветитьУдалитьВот, например. Сначала, для простоты, без оптимизации:
1. Каждый из разведчиков (назовем их А и В) представляет число 13 в виде суммы 6, 7 или 8 ненулевых слагаемых. Таких представлений 792+924+792=2508.
2. А подходит к куче камней. Если у него 7 или 8 ходов, он сразу делает свой первый ход. Иначе просто стоит. Поскольку еще не было ни одного броска, это не будет являться пустой передачей хода.
3. Подходит B. По количеству камней в куче определяет, сделал ли A ход, и если да, то какой именно. B делает свой первый ход.
4. Далее они бросают по очереди.
5. Если количество ходов у них оказалось одинаковым, то это очевидный случай.
6. Если у X (тот, кто бросал первым) ходов на один больше, чем у Y (который бросал вторым), то это тоже очевидный случай.
7. Если у X на два хода больше, то это 6 и 8. Тогда X делает свой 7-й ход, а 8-й за него делает Y, т.к. ситуация уже однозначна.
8. Если у Y на один ход больше, то это 7 и 8 (в силу правила 2). В этом случае Y сам делает свой 7-й ход, а 8-й за него делает X.
9. На два хода больше у Y быть не может.
Таким образом достигается 2508. Но можно немного оптимизировать. Разбиение производится на 6, 7, 8, 9 или 10 ходов. В случае 9 ходов, 8-й состоит из не менее двух камней. В случае 10 - и 8-й, и 9-й, оба не менее двух. Тогда тот, кому приходится делать чужой ход, бросает один камень, а его коллега завершает свой ход. На последний ход можно оставлять и один камень, т.к. уже не возникнет неопределенности.
Так получается 2683. Этот результат мне пока улучшить не удается.
Полагаю, многим этот комментарий будет очень полезен. Благодарю, что нашли силы и время на него!
УдалитьА как влияет число камней у какого-то из игроков на количество слагаемых, которые они выбирают для представления числа 13?
УдалитьДмитрий К., спасибо за разъяснения.
ОтветитьУдалитьКак я понимаю такой алгоритм не противоречит условию первой (оригинальной) задачи про шпионов:
ОтветитьУдалитьКинул левой рукой=0, кинул правой рукой =1. Если у каждого по 13 камней бинарное кодирование дает 2^13=8192. Для второй задачи (про цифры на доске) очевидно не совсем подходит.
С уважением Андрей.
Уважаемый Андрей,
ОтветитьУдалитьэто не две разных задачи, а одна задача, которую можно сформулировать разными способами (кому как удобнее). Конечно, все эти игры в кидание разными руками, подмигивание глазами, метание камней на разные расстояния (или в разные секторы пруда) не могут быть интересны, так как позволяют совсем маленьким усилием головы достичь якобы больших результатов.
... Сейчас посмотрел на доску в кабинете, она вся она исписана маркерами 4-х различных цветов...
ОтветитьУдалитьЕсли каждый из участников 13 раз напишет число 1 различными цветами маркера, то 4^13=67108864
С уважением Андрей.
PS:
Пришел как-то в Комитет по науке Государственной думы РФ человек с разработкой супероружия. Предъявляет официальную бумагу, что он направлен ФСБ. Комитет, конечно, был жутко заинтригован. Спрашивают, а где чертежи? Тот удивляется: а зачем? Я, говорит, изобрел красную кнопку. Ее нажимаешь - и все ядерное оружие противника взрывается. Его спрашивают: а как это сделать? Гость, подбоченясь, изрекает: «Я вам принес идею. А ваша задача - ее реализовать»
nik_vic ЖЖ
ОтветитьУдалить==Дмитрий К.Jan 11, 2012 03:29
==Если у него 7 или 8 ходов, он сразу делает свой первый ход. Иначе просто стоит.==
Гм, и что мешает каждому из них стоять по 9999 раз? Около 2-х камней ;)
nik_vic ЖЖ:
ОтветитьУдалитьГм, и что мешает каждому из них стоять по 9999 раз? Около 2-х камней ;)
Нацеленность на результат ;)
Или Вы имели в виду, как это отражено в алгоритме? См. п.3: B делает свой первый ход. Безусловно. А также п.4: Далее они бросают по очереди.
Дмитрий К.Jan 12, 2012 03:33 AM
ОтветитьУдалитьnik_vic ЖЖ:
Вы решаете другую задачу. В оригинале первый непременно бросает хоть один камень (не имеет права написать на доске 0 или пустое слово).
В оригинальном условии никак не оговаривается такое требование, чтобы первым кидал именно тот, кто первым подошел. По формулировке условия, "первым" называется тот, кто первым кинул камни. Вот чего действительно нельзя - это не бросить хотя бы один камень после того, как другой бросил. Ну естественно, если еще камни остаются.
ОтветитьУдалить== Сначала первый шпион кинул в воду несколько камней, потом - второй, потом опять...==
ОтветитьУдалить== Сначала первый шпион кинул в воду несколько камней, потом - второй, потом опять...==
ОтветитьУдалитьНу да, Вы абсолютно правильно цитируете. Вот тот, который первым кинул - это и есть первый. А другой - это второй. Но подойти он мог и раньше.
Вот представьте себе, что Вы за ними наблюдаете - осуществляете надзор за соблюдением процедуры. Вот подошел один и стоит. Потом подходит другой и бросает камни. Дальше по очереди. Какое нарушение Вы сможете им вменить? Заметьте, они заранее согласовывают свои действия между собой, но не с Вами и не с кем-либо еще. Они совершенно запросто Вам ответят, что именно так они и договорились - первым бросает именно этот. Просто он немного опоздал (в пробке застрял).
Или возможно такое согласование действий. Разведчик B подходит ровно в 12:00 и делает свой ход. А разведчик A, по ситуации, подходит либо в 11:59 либо в 12:01. В 12:00 B видит либо 26 камней, либо меньше.
"Изюминка" исходной формулировки в том, что они не имеют права встречаться. Петров обязан 1-го апреля (далее - по нечётным) выкинуть несколько камней, Иванов делает то же по чётным дням.
ОтветитьУдалить"Изюминка" исходной формулировки в том, что они не имеют права встречаться.
ОтветитьУдалитьЭ-э-э... А мы точно одну и ту же исходную формулировку обсуждаем?
"Согласовав заранее свои действия, они встретились на берегу реки возле кучи из 26 камней."
Дмитрий К,
ОтветитьУдалитьмне тоже кажется, что они вполне могли договориться, что Андрей приходит первого или третьего апреля, а Борис заведомо второго. Т.е. Андрей принимает решение будет он первым или вторым. Процедуру это не нарушает (так как абстрактный проверяющий не знает заранее, кто первый, а кто второй).
Встретились они на берегу или нет - это уже не так важно, так как не влияет на решение.
В то же время, я согласен, что имеет смысл и другая версия этой задачи: Андрей всегда бросает камни первым, а Борис - вторым. Этот вариант проще, поэтому начинать решать задачу стоит именно с него. Но потом, конечно, интересно разобраться и с более заковыристым.
== Т.е. Андрей принимает решение будет он первым или вторым. Процедуру это не нарушает ===
ОтветитьУдалитьДело не в том, кто первый - это должно быть определено в "задании". Дело в появлении права подойти к доске и написать в качестве очередного слагаемого ноль.
nik_vic ЖЖ
> Дело в появлении права подойти к доске и написать в качестве очередного слагаемого ноль.
ОтветитьУдалитьВроде бы уже несколько раз обсуждали, что нет такого права.
Согласен с тем, что условие встречи - не принципиальное. Также согласен с тем, что и альтернативные постановки задачи имеют полное право на жизнь. В частности, и с таким условием: кто первым подошел (а это как повезет), тому первому и ходить. Для такого случая могу предложить решение, совершенно аналогичное приведенному ранее.
ОтветитьУдалить13 камней делятся на от 6 до 10 ходов. Для 6 и 7 ходов разбиения произвольные (уже разобрано выше, это дает 1716). Если ходов больше 7, то с 7 по предпоследний включительно содержат не менее двух камней. Способ взаимодействия такой же, как описано выше. Это дает дополнительно 376. Получается 2092.
Этот алгоритм вполне годится и в том случае, когда выбор первого бросающего фиксирован. Но в таком случае у меня есть смутное подозрение, что можно и в алгоритм внести некоторую асимметрию, при этом немного улучшив результат. Но конструктивного решения по этому поводу у меня нет.
== можно и в алгоритм внести некоторую асимметрию, при этом немного улучшив результат==
ОтветитьУдалитьПопробуйте передать 23х23 кода, располагая 12-ю камнями.
nik_vic ЖЖ
Дмитрий К., Илья Весенний,
ОтветитьУдалитьпрошу прощения, что сразу не ответил.
Сейчас уже, если честно, не могу привести точные расчеты.
Но рассуждал я так. Я вспомнил другую задачу, про два яйца и многоэтажную башню.
А именно: есть два одинаковых яйца, которые разбиваются, будучи брошенными с определенного этажа и выше. Нужно найти номер этого этажа, минимизировав число бросаний.
Если бы яйцо было одно, его бы оставалось только бросать по очереди с каждого этажа снизу вверх. С двумя яйцами интереснее.
В свое время я нашел решение, которое казалось мне правильным: бросать первое яйцо с интервалом, равным корню квадратному из числа этажей. (То есть, если этажей 100, как было в одной из формулировок, то бросать с каждого десятого. Тогда потребуется максимум 19 бросаний: в худшем случае первое яйцо разобьется на сотом этаже, а второе -- на 99-ом).
Но оказалось, что это не самый оптимальный вариант. Его можно улучшить, варьируя интервал бросания первого яйца в зависимости от того, сколько попыток уже было потрачено. (Для 100 этажей суммарное число бросаний не больше 14: первое бросание первого яйца -- с 14-го этажа, второе -- с 14+13=27-го, третье -- с 27+12=39-го и так далее. Каждый раз остается ровно такой интервал, чтобы его можно было добить вторым яйцом за оставшееся число бросаний).
Так вот, мне и подумалось, что таким образом можно кодировать информацию. Номеру этажа можно поставить в соответствие пару чисел -- номера этажей, на которых разбилось первое и второе яйцо соответственно.
Дальше совершенно естественно выйти за рамки двух яиц и кодировать несколькими. Опять-таки, уже ничего не помню, но я составил программку на Python'е и выяснил, что для данной задачи (с камнями, отображая их на яйца :)) оптимальное число яиц -- шесть или семь, и при каждом из них максимальное число этажей -- 4718. (При большем числе яиц для них начинает не хватать попыток).
Итак, каждому шпиону/разведчику отводится по 13 камней (которые соответствуют попыткам бросания яиц). За шесть ходов он передает шесть чисел, каждое из которых соответствует номеру попытки, с которой разбилось n-ное яйцо. По этим данным можно восстановить номер критического для яиц этажа (= передать число в пределах общего числа этажей).
Вот. :)
Спасибо, что нашли время так подробно описать ход мысли. Последние годы мне гораздо интереснее понять, как человек шёл к решению, чем увидеть ответ :)
Удалитьnik_vic ЖЖ
ОтветитьУдалить==== Вот вариант для Экселя без оптимизации представления таблицы и других мелочей и визуализацией для малых NN.
=========================
Const NN = 256
Dim K(1 To NN, 1 To NN) As Byte
Sub sifr()
For a = 1 To NN: For b = 1 To NN: K(a, b) = 99: Next b, a: K(1, 1) = 0
For d = 3 To 2 * NN 'по диагоналям
For b = 1 To NN: a = d - b: If a <= NN And a > 0 Then K(a, b) = Ff(a, b) 'внутри квадрата
Next b
Next d
For y = 1 To NN: For x = 1 To NN: Cells(y, x) = K(y, x): Next x, y
End Sub
Function Ff(a, b) As Byte
If a = 1 Then Ff = K(b, 1) + 1: Exit Function
h1 = K(a - 1, b) 'pristrelka
AAA: h = h1: s = 0
For x = a - 1 To 1 Step -1
If K(b, x) < K(b, x + 1) And h > K(b, x) Then s = s + (h - K(b, x)) * x: h = K(b, x)
Next x
If s >= a Then Ff = h1 Else h1 = h1 + 1: GoTo AAA
End Function
А вот так быстрее. Результат - 2535.
ОтветитьУдалить==============
Const NN = 2555
Dim K(1 To NN, 1 To NN) As Byte
Sub sifr(): 'Dim a As Integer, b As Integer, d As Integer
For a = 1 To NN: For b = 1 To NN: K(a, b) = 99: Next b, a: K(1, 1) = 0
For d = 3 To 2 * NN 'diagonl'
Cells(1, 2) = d 'chtobi videt' stadiu
For b = 1 To NN
a = d - b
If a > NN Then GoTo Nextb 'vne кvadrata
If a < 1 Then GoTo Nextb 'vne кvadrata
If K(a, b) < 99 Then GoTo Nextb 'ужe soschitano
Call Ff(a, b)
Nextb: Next b
Next d
For y = 1 To NN: Cells(y, 1) = K(y, y): Next y 'raspechatka
End Sub
Sub Ff(a, b)
If a = 1 Then K(a, b) = K(b, a) + 1: Exit Sub
h1 = K(a - 1, b) 'pristrelka
AAA: h = h1: s = 0
For x = a - 1 To 1 Step -1
If h > K(b, x) Then s = s + (h - K(b, x)) * x: h = K(b, x)
Next x
If s < a Then h1 = h1 + 1: GoTo AAA
If s > NN Then s = NN
For i = a To s: K(i, b) = h1: Next i
End Sub
======================
НикВик
А-а, не понимаю, почему именно так! :-(
УдалитьКакая логика? Что вообще делает этот код? Почему именно это?
А можно вот еще как подойти к решению этой задачи.
ОтветитьУдалитьСначала рассмотрим как подзадачу одностороннюю передачу кода. Условимся так, что Андрей бросает первым, при этом он должен передать код, а Борис принимает код, при этом ассистируя: бросает по одному камню между ходами Андрея. Имея k камней, можно передать значение T(k). Очевидно, T(0)=T(1)=1. Несложно доказать, что T(k)=Ф[k] (число Фибоначчи).
Применительно к нашей задаче, нас интересует Ф[17]=2584 (итоговый ответ будет поменьше).
Еще одна подзадача - двусторонняя передача неодинаковых значений. Пусть камней k1+k2 (имеется в виду, что Андрей стремится передать значение Ф[k1]). Обменяться значениями Ф[k1] и Ф[k2] можно очевидным образом. Но хочется побольше принять взамен с минимальными потерями. Андрей отказывается применять ход, которым выбрасывается сразу k1 камней. Тогда Борис обязательно бросит один из тех k1 камней. К нему он может присоединить один или ни одного из k2 камней. К моменту, когда число Андрея будет полностью передано, у Бориса останется от 0 до k2 камней. Соответственно, Андрей сможет принять от Бориса
sum[i=0..k2](Ф[i])=Ф[k2+2]-1 возможных значений.
Возвращаемся к нашей задаче. Каждый ход несет в себе информацию. И чем больше камней в броске, тем меньше должен быть диапазон соответствующих ему значений, чтобы было реально передать его оставшимися камнями. Каким может быть максимальный первый ход? Если бросить 9 камней, то останется 26-9=17. Этого достаточно, чтобы передать 2584, при этом не принимая информации. Значит, первому ходу 9 соответствует некоторое единственное значение. Если бросить 8 камней, то останется 18 и можно будет в ответ передать 2583, приняв 2. 7 - соответственно 2583 и 4.
Продолжение следует
Поправка: К тому одному из k1 камней Борис может присоединить любое (в т.ч. нулевое) количество камней из числа k2.
УдалитьЕще одну неточность заметил. Чтобы принять Ф[k2+2]-1 значений, надо отказаться не только от хода в k1 камней, но и (k1-1) за один раз. Т.е. цена вопроса - минус 2 передаваемых значения. Но это несущественно, т.к. максимальные итоговые потери все равно больше.
УдалитьИтак, первый ход может содержать от 1 до 9 камней. Каждому варианту сопоставим диапазон значений D[i]=Ф[2*[n-i]]. Т.е. D[9]=Ф[0]=1, D[8]=Ф[2]=2, ..., D[1]=Ф[16]=1597. В сумме Ф[17]. Легко видеть, что если первый ход одного из участников окажется 9,8 или 7 камней, то граница Ф[17]-1 достигается. Если же, например, Андрей сделает первый ход 6 камней, то камней останется 20, а передать еще останется D[6]=Ф[6]=13. Борис же, исходя из 17+3 камней, может принять только Ф[5]-1=7, передав свои 2583. С потерей в 6 единиц еще можно мириться (в смысле, пойти на то, что итоговый ответ будет на 6 меньше), но чем дальше, тем больше. В случае хода в один камень при такой стратегии потери уже слишком большие.
ОтветитьУдалитьНо тогда мы применим такой прием. После того, как первый ход сделан, массив D пересчитывается, исходя из текущей ситуации. Например, если Андрей первым ходом бросил один камень, то на следующий ход его массив D может состоять уже из 8 элементов, т.к. ему остается передать одно из Ф[16] значений. В этом случае массив заполняется числами Фибоначчи с нечетными номерами от 1 до 15, что в сумме дает Ф[16]-1. Еще одна системная потеря.
Попробуем прикинуть, сколько мы можем в итоге потерять от значения Ф[17]. При благоприятном ходе (достаточно много камней), остаточный обмен происходит с потерей максимум единицы, и игра заканчивается. А иначе мы пересчитываем D. Максимальное количество раз пересчета массива D - в том случае, если они будут все время ходить по одному камню. Больше 13 раз это невозможно. А больше 12 не нужно. А пожалуй, что и больше 10 не нужно, т.к. для 6 камней уже все достаточно очевидно. Но ведь при этом будут чередоваться четные и нечетные номера соответствующих чисел Фибоначчи (а сумма чисел с четными номерами равна в точности следующему). Получается, что больше 6 единиц потерять не должны. Выходит 2577.
А пожалуй, что от второй подзадачи (с k1+k2 камнями) можно и вовсе отказаться. Решение станет красивее. Если один из игроков делает максимальный ход, то второй применяет алгоритм односторонней передачи. В противном случае, по результатам пары ходов (А+Б) каждый пересчитывает свой массив D.
ОтветитьУдалитьДмитрий К,
Удалитьспасибо за такое подробное описание!
Я уверен, многим будет интересно его прочитать.
nik_vic ЖЖ
ОтветитьУдалитьДмитрий К ==Выходит 2577==
Многовато...
Попробуйте с Вашими идеями получить 23х23 для 12 камней или 31х31 для 13 камней.
http://www.ljplus.ru/img4/n/i/nik_vic/Shifr13-13.GIF
Ну конечно, я мог где-то и ошибиться. В процессе размышлений не раз ловил себя на ошибках. Если заметите ошибку - сообщите, пожалуйста.
УдалитьА что в Вашей таблице означают красные числа?
Попробую. А скажите сразу, у Вас это получилось?
nik_vic ЖЖ
ОтветитьУдалитьКрасные - на диагонали, в максимальном положении для данного количества камней.
Вот главная часть программы -
=====
h1 = K(a - 1, b) 'pristrelka
AAA: h = h1: s = 0
For x = a - 1 To 1 Step -1
If h > K(b, x) Then s = s + (h - K(b, x)) * x: h = K(b, x)
Next x
If s < a Then h1 = h1 + 1: GoTo AAA
If s > NN Then s = NN
For i = a To s: K(i, b) = h1: Next i
=====
В самом деле, многовато получилось. Нашел-таки у себя ошибку. Не всегда корректен такой способ пересчета массива D. Надо найти какой-то более корректный вариант. Соответственно, результат окажется поскромнее. Но вроде бы, не должно быть намного.
ОтветитьУдалитьА вот 23х23 для 12 камней - это, на мой взгляд, многовато. Поэтому и спрашиваю, получилось ли это у Вас. Не рассчитать количество (в чем можно и ошибиться), а именно указать, как каждый из участников зашифрует свое значение и как расшифрует значение партнера.
nik_vic ЖЖ
ОтветитьУдалитьДмитрий К.==А вот 23х23 для 12 камней - это, на мой взгляд, многовато.==
12 камней хватает даже для 24х23 - смотрите мою таблицу, строка 23.
Первое разбиение - 24=13+7+3+1, бросается 1, 2, 3 либо 4 камня.
А вот немножко оптимизированный вариант. И заодно уж, наряду с таблицей K, заполняется и таблица P, содержащая правила разбиения для каждого ключа. При практическом применении такой таблицей пользоваться удобнее.
ОтветитьУдалитьvar N = 32; // максимальный ключ
var pebblesLimit = 12; // не считать больше, чем интересует
var fibCount;
var fib = new Array();
calcFib();
function calcFib()
{
fib[1] = fib[0] = 1; fibCount = 2;
do fib[fibCount] = fib[fibCount-2] + fib[fibCount-1]; while (fib[fibCount++] < N);
}
var K = new Array(); for (var i = 0; i < N; i++) { K[i] = new Array(); }
var rFilled = new Array(), rFilling = new Array(), cFilled = new Array();
rFilled[0] = cFilled[0] = 1;
for (var i = 1; i < N; i++) rFilled[i] = cFilled[i] = 0;
var P = new Array(); for (var i = 0; i < N; i++) { P[i] = new Array(); }
var pFilled = new Array();
P[0][0] = 1; pFilled[0] = 1;
for (var i = 1; i < N; i++) pFilled[i] = 0;
var cCompleted = 0;
calcPebbles();
function calcPebbles()
{
var currPebbles = 2;
while ((currPebbles <= pebblesLimit) && (cCompleted < N))
{
var n = currPebbles < fibCount ? fib[currPebbles-1] : N;
for (var c = cCompleted; c < n; c++) rFilling[c] = 0;
for (var c = cCompleted; c < n; c++)
{
var r = cFilled[c];
var count = c == 0 ? fib[currPebbles-2] : rFilled[c]-rFilling[c];
var x = r+count;
if (x <= N) P[c][pFilled[c]++] = count;
if (x >= N) cCompleted++;
cFilled[c] += count;
while ((count-- > 0) && (r < N)) { K[r][c] = currPebbles; ++rFilling[r]; ++rFilled[r++]; }
}
currPebbles++;
}
}
Для визуализации создал pebbles.html:
Удалить<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<title>pebbles</title>
<style type="text/css">
table { margin-top: 2mm; border-collapse: collapse; }
td { border: solid 1px black; text-align: center; }
td.key { font-weight: bold; background-color: #cccccc; padding-left: 0.5ex; padding-right: 0.5ex; }
td.diag { color: #aa0000; font-weight: bold; }
td.count { width: 3ex; }
td.portion { width: 6ex; border: none; }
</style>
</head>
<script type="text/javascript" src="pebbles.js"></script>
<body onload="showK(); showP();">
</body>
</html>
Функции showK и showP включил в pebbles.js:
var viewportOrig = 0, viewportSize = 34;
function showK()
{
var tbl = document.createElement("table");
tbl.cellSpacing = 0;
document.getElementsByTagName("body")[0].appendChild(tbl);
var tbd = document.createElement("tbody");
tbl.appendChild(tbd);
var tr = document.createElement("tr");
tbd.appendChild(tr);
for (var i = 0; i <= viewportSize; i++)
{
var td = document.createElement("td");
tr.appendChild(td);
td.className = "key";
td.innerHTML = i == 0 ? " " : viewportOrig + i;
}
for (var i = 0; i < viewportSize; i++)
{
var r = viewportOrig + i;
tr = document.createElement("tr");
tbd.appendChild(tr);
var td = document.createElement("td");
td.className = "key";
tr.appendChild(td);
td.innerHTML = r+1;
for (var j = 0; j < viewportSize; j++)
{
td = document.createElement("td");
td.className = "count";
if (j == i) td.className += " diag";
tr.appendChild(td);
var c = viewportOrig + j;
td.innerHTML = (r < N) && (c < N) ? (K[r][c] ? K[r][c] : " ") : " ";
}
}
}
function showP()
{
var tbl = document.createElement("table");
tbl.cellSpacing = 0;
document.getElementsByTagName("body")[0].appendChild(tbl);
var tbd = document.createElement("tbody");
tbl.appendChild(tbd);
for (var i = 0; i < viewportSize; i++)
{
var r = viewportOrig + i;
if (r >= N) break;
tr = document.createElement("tr");
tbd.appendChild(tr);
var td = document.createElement("td");
td.className = "key";
tr.appendChild(td);
td.innerHTML = r+1;
for (var j = 0; j < P[r].length; j++)
{
td = document.createElement("td");
td.className = "portion";
tr.appendChild(td);
td.innerHTML = P[r][j];
}
}
}
nik_vic ЖЖ
ОтветитьУдалитьДмитрий К.==А вот немножко оптимизированный вариант.==
А в чём оптимизация?
Ваш pebbles.html не пошёл, пытаюсь разобраться...
Ну не знаю... Я вот только что прямо отсюда на другой компьютер скопировал. И прекрасно сразу все пошло. Жаль только, что при вставке сюда программного кода форматирование пропало, это пришлось вручную восстанавливать, а то некрасиво. Надо в одну директорию поместить файлы pebbles.html и pebbles.js (здесь приведен в двух фрагментах).
УдалитьА оптимизация в том, что вся таблица заполняется одной тупой арифметикой, практически без логики - вся логика только в том, чтобы за границы не выйти. Ну и обход таблицы без повторного захода в просчитанные клетки.
Дмитрий К., каким браузером пользуетесь?
Удалитьnik_vic, смогли разобраться?
У меня ни в FF, ни в Chrome не заработало (т.е. выводит только шапку таблицы, а данные не отображаются). Есть идеи, как поправить?
Илья,
УдалитьЯ запускал в IE и FF. Проблем не наблюдал. Раз выводит шапку и на этом останавливается, вероятен какой-то exception в функции showK, т.к. она должна выводить квадратную таблицу размером viewportSize. Эти границы для нее определены безусловным образом. А FF что-нибудь пишет в консоль ошибок?
Дмитрий К,
Удалитьда, ошибка в 40 строке файла pebbles.js (не определены N и K, речь о строке «td.innerHTML = (r < N) && (c < N) ? (K[r][c] ? K[r][c] : " ") : " ";»). И я глазами тоже не вижу их объявления.
40? Понятно. Это я невнятно изложил. Файл pebbles.js начинается с предыдущего сообщения, т.е. с
Удалитьvar N = 32; // максимальный ключ
var pebblesLimit = 12; // не считать больше, чем интересует
...
А в следующем сообщении, начиная с
var viewportOrig = 0, viewportSize = 34;
...
- это его продолжение
Спасибо, теперь всё работает.
Удалитьnik_vic ЖЖ
ОтветитьУдалитьВижу, что отдельно считается К(1,в) - фибоначчи. Зачем?
Не вижу варианта типа моего
For x = a - 1 To 1 Step -1
If h > K(b, x) Then s = s + (h - K(b, x)) * x: h = K(b, x)
Next x
Повторного захода нет и у меня.
И есть сильно ускоряющее (используется монотонность) -
If s > NN Then s = NN
For i = a To s: K(i, b) = h1: Next i
До какого числа камней Вам удалось добраться?
Там возможна ещё и экономия памяти - за счёт времени, разумеется.
Вижу, что отдельно считается К(1,в) - фибоначчи. Зачем?
УдалитьВернее, так считается K(a,1). Затем, что каждый последующий шаг использует результат предыдущего. Но при этом где-то же должна быть и база.
Не вижу варианта типа моего...
Ну да, у меня нет пристрелки.
И есть сильно ускоряющее
If s > NN Then s = NN
For i = a To s: K(i, b) = h1: Next i
А вот этому и у меня есть аналог:
while ((count-- > 0) && (r < N)) { K[r][c] = currPebbles; ++rFilling[r]; ++rFilled[r++]; }
До какого числа камней Вам удалось добраться?
Так можно задавать разные значения N и pebblesLimit. Ну я подставил N=2540, pebblesLimit=27. Получил K(26,26)=2535.
Пардон, наоборот. K(2535,2535)=26.
Удалить==Но при этом где-то же должна быть и база==
ОтветитьУдалитьДык куда ж без неё: K(1,1)=0. И хватает ;)
Насчёт 2535 - верно.
Настоящие комбинаторщики, небось, могут и производящую функцию сварганить...
nik_vic ЖЖ
K(1,1)=0 - это да, это самая базовая база. Но если в качестве базы служит целый столбец таблицы - это весьма существенное подспорье. В результате целый внутренний цикл заменяется разностью двух значений. Таблица заполняется слоями - вот этими вот дугами, которые образуют семейства одинаковых значений. Поэтому я не вычисляю h1 - оно на единицу больше предыдущего.
УдалитьНадеюсь я не очень отстал от остальных решающих эту задачу. :-)
ОтветитьУдалитьСам по себе я ленивый, и поэтому ждал когда же кто-нибудь понятно разжуёт решение для ответа 2535, вникать в код не очень-то хотелось. Не дождавшись, решил порешать сам. Получились всё те же 2535, но теперь я хоть понимаю откуда.
Да, кстати выше предлагали дать возможность одному из шпионов выбрать кто будет ходить первым. Я считаю что этот дополнительный канал информации условию не соответствует.
Решал так, можно сказать по индукции:
Если осталось 0 камней:
Тот, чья очередь кидать, может передать второму 1 различных чисел.
Втотой первому - тоже 1 различных чисел.
Обозначу это 1:1
Если остался 1 камень:
У первого только один вариант выкинуть этот камень, поэтому никакой дополнительной информации он передать не может.
1:1
Если осталось 2 камня:
У игрока 2 варианта:
1) кинуть один камень, тогда второй остаётся с одним камнем (и возможностями 1:1)
2) кинуть два камня, тогда второй остаётся с нулём камней (1:1)
Таким образом у игрока есть 1+1=2 способа оставить второго игрока с 1 вариантом, поэтому это ситуация 2:1
Если осталось 3 камня:
1) можно кинуть один камень, оставив второго в ситуации 2:1
2) кинув 2 камня, можно оставить второго в ситуации 1:1
2) кинув 3 камня, можно оставить второго в ситуации 1:1
Находясь перед кучей из трёх камней игрок может либо предоставить второму возможность выбрать число из двух выкинув один камень и не передав никакой информации, это ситуация 1:2,
Либо передать информацию кинув 1, 2 или 3 камня, но не получив ничего взамен, 3:1.
Обращаю внимание, что хотя в последней ситуации может так оказаться что передавая информацию первый кидает 1 камень и вроде бы у второго появляется возможность тоже что-то передать, это не ситуаций 3:2, потому что мы не можем гарантировать что при любом из 3х вариантов для первого, у второго будет 2 варианта.
Таким образом, с тремя камнями ситуации может быть две: 1:2 и 3:1.
Ситуация с 4 камнями:
С 4 камнями я надеюсь что всё будет понятнее.
1) кидаем один, оставляем коллегу в ситуации 1:2 или 3:1 на выбор
2) кидаем два, оставляем в 2:1
3) кидаем три, оставляем в 1:1
4) кидаем четыре, оставляем в 1:1
Если мы хотим предоставить коллеге возможность передать одно из 3х чисел, мы кидаем один камень, это 1:3
У нас есть два способа дать ему возможность передать один из 2х чисел (кинув два камня, и кинув один, в последнем случае у него даже избыток возможности), получается 2:2
И самое интересное: если мы не хотим от второго игрока никакой информации, у нас есть 4 способа кинуть камень сейчас, но если мы кинем 1 камень, то позже мы можем воспользоваться ситуацией 1:2, и передать ещё один из двух вариантов. Таким образом, это 5:1.
То есть с четырьмя камнями ситуации 5:1 2:2 1:3.
Напоминаю, что это значит, что по предварительной договорённости с 4 камнями шпионы могут:
* первый второму может передать число от 1 до 5, не получив информации взамен
* каждый каждому может передать число от 1 до 2
* первый может информацию не передавать, но принять от второго число от 1 до 3
Допустим мы просчитали возможности для всех ситуаций с количеством камней от 0 до N:
(пример для N=4)
S[0] = {1:1}
S[1] = {1:1}
S[2] = {2:1}
S[3] = {1:2, 3:1}
S[4] = {1:3, 2:2, 5:1}
Для того, чтобы посчитать возможности для N+1, мы
для каждого d (из множества натуральных чисел :-) ) {
sum := 0
для каждого n из 0..N {
ищем в S[0] пару a:b, с максимальной b, при условии что a>=d;
sum := sum + b
}
добавляем в S[N+1] пару sum:d
}
S[5] = {1:5, 2:3, 4:2, 8:1}
И т д.
Из S[26] выбираем пару a:b с наибольшим min(a,b) и это оказывается 2535:2536, это и есть наш ответ.
Для того чтобы из полученных данных построить алгоритм выбора количества камней, надо идти по нему в обратном порядке.
Написал на джаваскрипте обратный ход алгоритма, можете поиграться:
http://crem.dyndns-home.com/files/sponges.html (только я решал в терминах мочалок а не камней)
http://crem.dyndns-home.com/files/sponges.html
УдалитьПеренёс ссылку в место позаметнее, чтоб те которые любят играться но не любят читать скучные тексты её не пропустили. :)
crem,
Удалитьспасибо за такое подробное описание!
Здорово, что Вы пояснили, каким образом думали. Ведь многим часто хочется не столько узнать ответ, сколько понять, как дойти до ответа. Поэтому Ваш текст обладает повышенной ценностью :)