Степени двойки, как известно, редко начинаются с цифры 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. Результат умножьте на миллион и округлите вниз до целого.

Пусть a(n) – наибольший корень многочлена P(x) = x³ - 3ⁿx² + n, например a(2)=8,97517184...
Пусть t(n,p)=[a(n)^p], где скобки […] означают округление вниз до целого.

Найдите восемь младших десятичных знаков суммы ∑t(i,333333333) для i=1,2,3,...30.

Возьмем натуральное число n и рассмотрим последовательность s(n)={1+n/1, 2+n/2, 3+n/3, …k+n/k,…}. Если эта последовательность не содержит целых составных чисел, будем говорить, что число n не порождает составных.
Легко проверить, что последовательность s(30)={31, 17, 13, 11.5, 11, 11, …} содержит только простые и нецелые числа. Поэтому число 30 не порождает составных.
Найдите количество восьмизначных чисел, которые не порождают составных.

В отеле "Инфинити" бесконечно много этажей, на каждом этаже бесконечно много комнат, а к администратору выстроилась бесконечно длинная очередь. И этажи, и комнаты на каждом этаже, и посетители перенумерованы подряд натуральными числами (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 .

Хозяйка испекла для гостей пирог. К ней может прийти либо 7, либо 8, либо 9 человек. Число N - наименьшее число кусков, на которое ей нужно заранее разрезать пирог так, чтобы его можно было поделить поровну и между семью, и между восемью, и между девятью гостями.

Сколько существует различных разбиений пирога на таких N кусков?

Замечания.

1. Нужно считать только разбиения на куски, кратные 1/(7*8*9) части пирога.

2. Если из какого-то разбиения можно скомпоновать нужные части несколькими способами, то это разбиение всё равно считается только один раз.

Для каждого натурального n определим функцию f(n) как количество хорд параболы y=x², концы которых имеют целочисленные координаты, и квадрат длины которых равен n.

Например, f(4)=1, f(2)=2, f(3)=0 и f(50)=4. На рисунке

изображены 4 хорды с целочисленными координатами концов и квадратом длины равным 50.

Найдите наименьшее число n, для которого f(n)=8.