Математические задачки. Морковкин, скучаем :-)

Чаще в задачах фигурируют не кошельки, а взвешивания. Вот простейшее объяснение оптимальных алгоритмов для рычажных весов, наиболее эффективной будет та система счисления, в основе которой лежит знаменатель рекуррентного соотношения, приведенного внизу страницы. При наличии двух весов с нулевой инерцией - троичная система. Однако чаще весы одни, инерция не нулевая, поэтому применяют систему с иррациональным основанием (в позиционных разрядах - р-числа Фибоначчи). Относительно избыточности, если двоичная система четырьмя битами записывает числа от 0 до 15, система Цекендорфа - от 0 до 7, Брауна - от 0 до 11 (т.к. "вычеркивает" варианты со старшим разрядом).

Гений и идиот.

Однажды на выступлениe тов. Лысенко попал Лев Ландау. Лысенко делал
доклад о наследственной обучаемости. Ну он там пытался пшеницу
замораживать и надеялся, что она будет морозоустойчивая потом.
И вот, когда подошла пора вопросов, Ландау спросил:

- Правильно ли я вас понял, тов. Лысенко, если у коровы отрезать ухо и у
ее потомства отрезать ухо, и т.д. и т.д., то в конце концов родится
одноухая корова?
- Да совершенно верно, тов. Ландау! - ответил Лысенко.
- Тогда у меня вопрос, - сказал Ландау: А как вы объясните рождение
девственниц?...
В зале воцарилась гробовая тишина.

Говорят, что аналогичный вопрос задавали по поводу обрезания мальчиков на 8-й день по еврейской традиции.

"Фибоначчиева арифметика - занятная игрушка. Увы, за пределы "Библиотечки "Кванта" не вышла. Автор, конечно, всё сделал правильно: защитился, запатентовался, но ... ложка под подушкой не пригодилась"
Ну почему. Труды Воробьёва по Фиббоначи были важным вкладом в решение 10-ой(?) проблемы Гильберта(Матиясевич)

Настоящий монстр там в последнем абзаце, а это так монстрёнок

Наверное, с листком бумаги такое достижение повторили бы многие, зная алгоритм. Самое сложное - проделать всё это в уме. Надо постоянно держать в памяти полдюжины меняющихся чисел, которые некуда записать. И быстро проводить с ними действия.

Проще извлечения квадратного корня - только корень пятой степени. Это так, к слову пришлось.

Давно искал подходящую задачку для детей по комбинаторике и началам теорвера. Все эти подбрасываемые монеты и вытаскиваемые "со дна глубокого колодца" шары изрядно скучны, да и зачастую не могут дети сопоставить абстрактные задания с реальной жизнью. Сегодня одноклассник привел подходящую задачу - из какого-то школьного пособия. Итак, для тех, кто как и я в свое время не читал ученики.

Злоумышленник проник в винный погреб к римскому патрицию, но был пойман. На допросе негодяй сообщил, что добавил яд в одну бочку, в какую именно - не помнит. Про действие яда он не смог дать четких сведений, но даже самый крепкий человек, выпивший кубок отравленного вина, умрет в течение суток. Есть основания полагать, что показания правдивы.
Через N дней патрицию предстоит поставить вино на пир, до этого момента крайне желательно идентифицировать отравленную бочку. Начальное число рабов, которыми располагает патриций для экспериментов, K (N и K - целые, неотрицательные).

1. Какого максимальное число бочек, которые гарантировано будут проверены в срок? Опишите алгоритм.
2. Посчитайте при макс. числе бочек вероятность того, что патриций к началу пира перестанет быть рабовладельцем. Какова вероятность выжить у отдельно взятого раба?
3. Найти мат. ожидание количества выпитого вина выжившим рабом во время дегустаций (в кубках).

Совершенно верно есть способ очень похожий на деление в столбик, основан на том что (a+b)^2 = a^2+2ab+b^2 . Нашел вот тут http://yourtutor.info/wp-content/uploads/2012/04/kvadratnyj-koren-bez-kalkulatora.jpg подробное описание того как это делается. Меня в детстве, когда готовили к математическим и физическим олимпиадам, тоже учили извлекать корни похожим способом по учебникам 50х годов. Для себя посчитал, потратил порядка 2 минут, так, что ничего сверхъестественного в 14 секундах нету. Хотя здорово.

Мобуту чуть выше уже указал на одно из описаний алгоритма. Конечно, 14 секунд - приличный результат.

В советское время эффектнее всего было, как я уже заметил, извлекать корни пятой степени. Калькуляторы Светлановского завода вмещали на индикаторе до 12 знаков (т.е. слишком больших чисел можно было не опасаться), поэтому ответ назывался в момент произнесения загадывающим последней цифры.

Да, вернемся к бочкам, не к ночи будут помянуты. Задача - гарантировано установить отравленную. Может, патриций хочет пару бутылок для своих коллег захватить. Но тут важно не ошибиться, ответ или-или не годится.

Да, если N=K=1, то можно разобраться с двумя бочками. Вероятность выживания раба - 1/2, мат. ожидание - один кубок.

А если сразу вылетит виртуальный, тогда придётся добавлять ещё одного виртуального? То есть общее число реальных и виртуальных может быть и больше, чем K+1. И (K+1)! не максимум. Пример: в первый день реальным рабам по K! бочек, виртуальному (K+1)! бочек. Дальше будет либо (K+1)! с K рабами, либо K! с K-1 рабом.

Как раз посчитать выпитое выжившим рабом при столь наивном алгоритме ничего не стоит, сумма факториалов. Однако, во-первых, что делать рабам при больших N, во-вторых, это оценка винного погреба снизу. Из одной бочки могут пить группы рабов, так что советую воспользоваться картами Карно.

Например, 2 раба могут определить из четырех бочек отравленную за 1 день. Вроде, это максимум..

to onedrey: Первый правильный шаг в верном направлении.
to MS: В вашей формуле нет зависимости от N. Но также не бывает, ведь это лишний день для плодотворных экспериментов! Причем рабы, может, и выживут, а день пролетит при любом раскладе. Так что N важнее К.

P.S. to MS: За один день - конечно, не побить. К рабов могут дать за раз лишь 2**К информации.

Я так и прочел. Зависимость от N есть всегда, за исключением случая К=0. При положительном числе рабов - монотонно возрастающая функция. Впрочем, тоже можно сказать и о зависимости от К: если число дней не равно нулю, то мы имеем монотонно возрастающую функцию.

P.S. Дам подсказку: к этой задаче (выбор стратегии) как нельзя лучше подходят слова, которые Коровьев адресует буфетчику в соответствующем романе.

Каждый раб может либо вообще не умереть, либо умереть в какой-то из N дней. Для K рабов получится (N+1)^K вариантов, каждому из которых может соответствовать не больше 1 бочки. То есть бочек не может быть больше (N+1)^K.Запишем все числа от 0 до (N+1)^K-1 в N+1 - ричной системе. Будем считать, что у каждого числа будет K знаков, если меньше, то начальные будем считать нулями. Каждое число соответствует бочке. Каждый знак соответствует рабу, 0 означает, что раб не пил эту бочку, другое число - номер дня, в котором соответствующий раб пил бочку. То есть для каждой из (N+1)^K бочек составляется график распития её рабами.

Вероятность остаться без рабов равна вероятности, что число будет без нулей. То есть (N/(N+1))^K.

СюгировФан совершенно прав. Но меня скорее заинтересовало, как будет проходить распитие халявного вина рабами.

Всего бочек (1+N)**K. Это бином Ньютона, который раскрывается в сумму C(i,K)*N**i, где C - биномиальный коэффициент (число сочетаний в комбинаторике), i - число выживших на данном этапе рабов. Кстати, если бы onedrey продолжил свои рассуждения, он бы по индукции получил именно эту формулу. Ее бытовой смысл предельно прост - каждое слагаемое показывает сколько бочек будет распиваться ровно K-i рабами. Т.е. все рабы пригубят из C(0,K)*N**0=1 бочки, а C(К,K)*N**К=N**К бочек пока останутся нетронутыми.

Пожалуй, самое наглядное применение биномиальных коэффициентов.

Мне вчера почему-то навскидку показалось, что бочек=N^K+K
Уже даже и не помню, почему. Поздно было)

Алгоритм таков: нумеруем бочки в системе счисления с основанием N+1, для нумерации отводим K разрядов; также нумеруем рабов. В j-ый день до пира рабы обходят погреб и пьют из тех бочек, в номере которых j стоит в присвоенном данному рабу разряде. Из этого следует, в частности, что если отрава в бочке, которая получила "большой" номер (скажем, все цифры больше семи), то патриций закончит проверку досрочно (на неделю раньше часа Х). Своя прелесть есть и в случае, когда номер искомой бочки содержит нули - тогда наш патриций сохранит гордый титул рабовладельца. Вероятность этого события - единица минус вероятность, которую привел СюгировФан.

P.S. А тему "Треугольник", может стоит перенести сюда в полном объеме?
P.P.S. Ну и, конечно, извиняюсь за преувеличение важности количества дней. Это надо понимать иносказательно: рабы, вино - приходят и уходят, а бег времени... Впрочем, мы отвлеклись.

Осталось разобраться с мат. ожиданием. В предложенной СюгировФан'ом стратегии, при всем удобстве ее реализации, выжившие рабы рискуют спиться, ведь они употребляют в итоге N*(N+1) кубков. Не знаю, сколько кубков вмещает бочка, но может оказаться, что рабы нанесут запасам больший урон, чем злоумышленник. Это происходит из-за того, что рабы продолжают пить из уже проверенных бочек или из заведомо безопасных (при условии, что яд уже обнаружен одним из членов бригады).