Английский математик Джон Хортон Конвей изобрел множество математических развлечений, доставляющих не только удовольствие, но и пищу для серьезных размышлений. Одно из его изобретений – язык программирования FRACTRAN, о котором пойдет речь в данной задаче.

Память данных виртуальной машины языка FRACTRAN содержит одно единственное целое число, а программа представляет собой упорядоченную последовательность рациональных дробей. На каждом шаге выполнения программы машина просматривает эти дроби одну за другой слева направо и умножает каждую из них на число из памяти, пока произведение не окажется целым. Полученное целое число записывают в память вместо предыдущего. 

Вот, например, FRACTRAN-программа, предложенная Конвеем для получения последовательности простых чисел:

17/91, 78/85, 19/51, 23/38, 29/33, 77/29, 95/23, 77/19, 1/17, 11/13, 13/11, 15/2, 1/7, 55/1.

Записав в память исходное значение 2, получим в памяти ряд чисел в следующей последовательности:

15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, 910, 170, 156, 132, 116, 308, 364, 68, 4, 30, ..., 136, 8, 60, ..., 544, 32, 240, ...

Оказывается, степени двойки в полученной последовательности встречаются только с простыми показателями: 2², 2³, 2⁵, ..., и можно проверить, что данная последовательность будет содержать в порядке возрастания все степени двух с простыми показателями.

Заметим, что для получения 2² из исходного числа 2 потребовалось 19 шагов программы, и при этом три раза происходило умножение на дробь 13/11.

А сколько раз придется выполнить умножение на 13/11 при переходе от исходного числа 2 к 2¹¹¹¹¹⁹?

Широко известна игра, где один из участников задумывает целое число, а другой пытается его угадать, задавая вопросы. В этой задаче исследуется вариант такой игры, когда задумывают натуральное число из промежутка [1,n], а в качестве вопросов разрешается называть натуральные числа из этого же интервала. При этом стоимость каждого вопроса равна названному числу. Допускаются ответы трех видов:

1. Ты назвал число меньше задуманного.
2. Ты угадал!
3. Ты назвал число больше задуманного.

Требуется определить  задуманное число и при этом минимизировать суммарную стоимость вопросов (в дальнейшем – цена игры). Для данного числа n назовем стратегию оптимальной, если она минимизирует цену игры для самого неудачного задуманного числа.

Например, при n=3 наилучшим первым ходом будет число "2". После этого при любом ответе можно будет точно определить задуманное число, поэтому больше вопросов не потребуется, и цена игры будет равна 2.

Если n=8, мы могли бы выбрать в качестве стратегии "бинарный поиск". Если первым ходом мы назовем число "4", а задуманное число будет больше, чем 4, нам потребуется еще два вопроса. Пусть вторым ходом мы называем число "6". Если задуманное число больше, чем 6, нам потребуется еще один ход, скажем, "7", и цена игры составит 4+6+7=17.

Мы можем существенно улучшить нашу стратегию для n=8, если первым ходом назовем число "5". Если задуманное число больше, чем 5, то вторым ходом мы можем назвать число "7", и этого будет достаточно для нахождения задуманного. Тогда цена игры составит 5+7=12. Если же задуманное число меньше, чем 5, то для его определения достаточно  вторым и третьим ходом назвать "3" и "1", а цена игры составит 5+3+1=9. Поскольку 12 > 9, в худшем случае цена игры при этой стратегии будет равна 12. Получается, что данная стратегия более выгодна, чем предыдущая, и оказывается, что она оптимальна, то есть никакая другая стратегия не может гарантировать для n=8 результат меньший, чем 12.

Пусть C(n) – максимальная цена игры, которая может получиться для оптимальной стратегии в худшем случае. 

Тогда C(1) = 0, C(2) = 1, C(3) = 2 и C(8) = 12.

Можно подсчитать, что  C(100) = 400.

Найдите С(500000).

Круглое болото разбито на секторы, перенумерованные по часовой стрелке числами от 1 до 500. Лягушка, сидящая в одном из секторов, может прыгнуть в один из двух соседних секторов с равной вероятностью.

Перед тем, как прыгнуть, лягушка квакает. 

Если номер сектора, в котором сидит лягушка, является простым числом, она с вероятностью 2/3 квакает "P" и с вероятностью 1/3 квакает "N".

Если номер сектора, в котором сидит лягушка, не является простым числом, она с вероятностью 2/3 квакает "N" и с вероятностью 1/3 квакает "P".

Предположим, что в начальный момент лягушка может занимать любой из секторов с равной вероятностью. Подсчитайте вероятность того, что после 15 прыжков лягушачью песнь можно будет закодировать последовательностью PPPPNNPPPNPPNPN. 

Результат представьте в виде несократимой дроби, а в качестве ответа укажите ее числитель.

На каждую клетку доски N×N положили по шашке, окрашенной в белый цвет с одной стороны и в черный цвет с другой.

Каждым ходом разрешается перевернуть одну шашку, а вместе с нею N-1 шашек, стоящих  на одной с ней вертикали, и N-1 шашек, стоящих  на одной с ней горизонтали. Таким образом, каждым ходом игрок должен перевернуть 2×N-1 шашку. Игра заканчивается, когда все шашки будут стоять белой стороной вверх. Ниже приведен пример игры для доски 5×5.

Несложно проверить, чтобы закончить игру из данной начальной позиции, нужно как минимум 3 хода.

Пусть строки и столбцы перенумерованы целыми числами от 0 до N-1.

Построим на доске N×N начальную конфигурацию C_N. Для этого на клетку с координатами x и y положим шашку черной стороной вверх, если (N-1)²≤x²+y²<N², и белой стороной вверх в противном случае. Конфигурацию C₅ мы видели в приведенном примере.

Пусть T(N) – минимальное количество ходов, необходимых для окончания игры из начального положения C_N (если это невозможно T(N) = 0).

Ясно , что T(1)=T(2)=1. Мы видели, что T(5)=3. Можно проверить, что T(10)=29, а T(1000)=395253.

Найдите сумму T(k!) для 1≤k≤12.

Вагоны поезда обозначены буквами латинского алфавита: A,B,C,D..., и последовательность вагонов в железнодорожном составе можно задать с помощью соответствующей цепочки букв.

В правильно сформированном составе вагоны должны следовать алфавитном порядке. Добиваются этого на сортировочной станции, где установлен большой поворотный круг.

Когда состав въезжает на круг, несколько последних вагонов отцепляют, после чего локомотив с остальными вагонами съезжает с круга. Вагоны, стоящие на круге, поворачивают на 180 градусов и вновь прицепляют в хвост состава, но уже в обратном порядке. Эту операцию повторяют несколько раз, пока не достигают желаемого результата.

В некоторых случаях сформировать состав совсем просто. Например, когда исходный порядок вагонов ADCB, вагоны можно расцепить между A и D, затем развернуть фрагмент DCB, и, наконец, сцепить вагоны в нужном порядке. Результат достигается всего за один шаг, т.е. за один поворот круга на 180 градусов.

Возможно, процесс можно оптимизировать, но машинист пользуется совсем простым алгоритмом. Сначала он стремиться прицепить вагон A следом за паровозом, затем следом за ним вагон B, и так далее.

Машинист выяснил, что для состава из четырех вагонов потребуется не более 5 шагов. Максимальное количество - 5 операций - требуется для двух начальных последовательностей, а именно DACB и DBAC. Последовательности вагонов, требующие наибольшего количества операций для упорядочения, будем называть пессимальными.

Порядок формирования состава для начальной последовательности  DACB показан на рисунке.

Для состава из шести вагонов машинист составил список пессимальных последовательностей. Список содержал 24 последовательности. Последовательности он расположил в алфавитном порядке, и цепочка DFAECB оказалась на десятом месте от начала.

Представьте, что вам поручили составить список пессимальных последовательностей для составов из 11 вагонов и упорядочить получившийся список в алфавитном порядке.

На каком месте в списке окажется последовательность CIAKBGHFJDE?

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

Первоначально каждое стадо состоит из n овец. Каждая овца, независимо от масти, может заблеять в очередной раз. Передур стремится максимизировать количество черных овец. Для этого он может прогонять прочь любое количество белых овец, но делать это он может лишь после того, как заблеяла очередная овца и до того, как овца с противоположного берега вошла в реку.
Пусть E(n) – ожидаемое количество черных овец, которое останется у Передура при оптимальной стратегии. Например, E(5) ≈ 6.871346…
Найдите наименьшее n, для которого E(n)>20000.

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

• Если он находится на черной клетке, он перекрашивает клетку в белый цвет, изменяет направление своего движения на 90 градусов против часовой стрелки и переходит в соседнюю клетку.
• Если он находится на белой клетке, он перекрашивает клетку в черный цвет, изменяет направление своего движения на 90 градусов по часовой стрелке и переходит в соседнюю клетку.

Пусть в начальный момент все клетки доски белые, а муравей находится в точке с координатами x=0 и y=0. Клетки доски ориентированы вдоль координатных осей и имеют единичный размер.
Найдите |x|+|y| после 10¹⁸ шагов.

Степени двойки, как известно, редко начинаются с цифры 9 (см. задачу 316). Так, первый раз это случается только для 53-й степени (2⁵³ = 9007199254740992). С двух девяток подряд начинается 93-я степень, а с трех девяток - только 2621-я.

Найдите минимальный показатель степени n такой, что десятичная запись числа 2ⁿ начинается с десяти девяток подряд.

Известно, что некий вирус поражает 2% овец. Ветеринару нужно выявить зараженных животных в стаде из 25 голов. При этом в его распоряжении имеется достаточно дорогой, но очень чувствительный метод анализа, позволяющий обнаруживать инфекцию в крови при крайне низких ее концентрациях.

Чтобы сэкономить дорогостоящие реактивы, ветеринар решил не проверять каждую овцу, а разработал следующую программу действий:
Он разбил стадо на 5 групп по 5 овец в каждой. Пробы крови для каждой группы были объединены и проанализированы. Затем, если в объединенной пробе вирус не обнаружен, все овцы из данной группы считаются здоровыми. В противном случае анализируются пробы крови для каждого из пяти животных группы.
Поскольку вероятность заражения отдельной овцы равна 0,02, первый тест для каждой группы даст
• Отрицательный результат с вероятностью 0,98⁵ = 0,9039207968. Для такой группы дополнительные тесты не понадобятся.
• Положительный результат с вероятностью 1 - 0,9039207968 = 0,0960792032. Для такой группы потребуется проанализировать еще 5 отдельных проб.
Тогда ожидаемое количество анализов для каждой группы составит 1 + 0,0960792032 × 5 = 1,480396016, а для всего стада – 1,480396016 × 5 = 7,40198008 тестов, то есть экономия составит более 70%!
Однако это не предел. Алгоритм можно еще усовершенствовать следующим образом:
• Сначала можно проанализировать объединенную пробу для всех 25 овец. Легко проверить, что примерно в 60,35% случаев результат будет отрицательный, и дальнейшее исследование не потребуется.
• Если групповая проба для 5 овец была положительной, и первые четыре овцы из группы оказались здоровы, то пятую можно не проверять – она наверняка инфицирована.
• Можно попробовать поварьировать размер и количество групп. Это позволит минимизировать ожидаемое количество анализов.
Чтобы не усложнять задачу, мы несколько ограничим круг рассматриваемых алгоритмов. Мы примем следующее дополнительное правило: если проанализирована объединенная проба для группы овец, то овцы, не входящие в данную группу, не исследуются, пока не поставлен окончательный диагноз каждой овце из данной группы.
Оставаясь в рамках данного правила, мы можем найти оптимальную стратегию, позволяющую ограничиться всего 4,155452 тестами в среднем для стада из 25 овец и вероятности заражения 0,02.
Обозначим через T(s,p) ожидаемое количество тестов при использовании оптимальной стратегии, когда стадо состоит из s овец, а вероятность заражения отдельной овцы равна p.
Тогда T(25, 0,02) ≈ 4,155452 и T(25, 0,10) ≈ 12,702124.
Найдите p, для которого T(10000, p)=5000. Результат умножьте на миллион и округлите вниз до целого.

В отеле "Инфинити" бесконечно много этажей, на каждом этаже бесконечно много комнат, а к администратору выстроилась бесконечно длинная очередь. И этажи, и комнаты на каждом этаже, и посетители перенумерованы подряд натуральными числами (1, 2, 3, …).
В начальный момент все комнаты отеля свободны. Чтобы поселить очередного гостя с номером n,  администратор выбирает самый нижний этаж, на котором либо пока никто не живет, либо последний поселившийся имеет такой номер m, что m+n является квадратом целого числа. Новый гость получает первый свободный номер на выбранном этаже.
 Гость №1 получает комнату №1 на первом этаже, поскольку на нем еще никто не живет.
 Гостя №2 нельзя поселить в комнате №2 на первом этаже, поскольку сумма 1+2=3 не является квадратом. Этого гостя можно поселить на втором, пока еще пустом этаже, в комнате №1.
 Гость №3 получает комнату №2 на первом этаже, поскольку сумма 1+3=4 является квадратом.
Таким образом, каждый гость получит свою комнату в отеле.
Обозначим через P(f, r) номер посетителя, живущего в комнате r на этаже f.
Тогда:
P(1, 1) = 1
P(1, 2) = 3
P(2, 1) = 2
P(10, 20) = 440
P(25, 75) = 4863
P(99, 100) = 19454
Найдите сумму P(f, r) для всех f и r, таких что f² + r² = 14234886498625 .