Альберт выбирает натуральное число k и два случайных вещественных числа, a и b, равномерно распределенных на промежутке [0,1]. Затем он вычисляет квадратный корень из суммы (k·a + 1)² + (k·b + 1)² и округляет его вниз до целого. Если результат оказывается равным k, Альберт получает k очков, в противном случае он не получает ничего.
По окончании игры Альберт получает 1000 руб. за каждое очко.
Можно подсчитать, что после 10 туров с k=1, k=2,: k=10 математическое ожидание выигрыша составит примерно 12059 руб. 48 коп.
Каково будет математическое ожидание выигрыша после 10⁵ туров с k=1, k=2, k=3, ..., k=10⁵? Дайте ответ в копейках, округлив его до ближайшего целого.

В сильно  упрощенной модели белки можно рассматривать как цепочки гидрофобных (H) и полярных (P) элементов, например HHPPHHHPHHPH.

В этой задаче мы будем считать, что ориентация белка существенна, то есть белки HPP и PPH мы будем считать различными, а количество белков из n элементов будет равно 2ⁿ.

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

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

На рисунке показаны две конфигурации одного белка (связи H-H отмечены красными точками)

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

Правая конфигурация имеет девять связей H-H, и это максимальное значение для такой цепочки. Будем называть оптимальными те конфигурации, которые обеспечивают максимальное количество связей H-H для данной цепочки.

77 из 256 восьмиэлементных цепочек в оптимальной конфигурации имеют более 4 связей H-H.

Сколько цепочек, состоящих из 15 элементов, в оптимальной конфигурации будут иметь более 9 связей H-H?

Как известно, последовательность Фибоначчи определяется рекуррентно:

f(0)=0 , f(1)=1, и f(n)=f(n-1)+f(n-2) при n>1.

Найдите Σf(p_i), где p_i – простые числа, и 10¹⁴< p_i <10¹⁴+5*10⁶.

Остаток от деления полученной суммы на 1234567891011 будет ответом к этой задаче.

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

• При n=1 первый игрок автоматически проигрывает, поскольку не может сделать ни одного хода.
• При n=2 есть только один ход, который автоматически ведет к победе.
• При n=3 первый игрок может выбрать один из двух различных ходов, и оба они ведут к немедленной победе.
• При n=4 есть три варианта хода. Среди них есть один выигрышный ход, когда игрок закрашивает две средние клетки.
• При n=5 есть четыре варианта хода (они показаны на рисунке красным цветом), но все они ведут к поражению: второй игрок (показан синим цветом) всегда может выиграть.

Таким образом, первые три значения n, при которых первый игрок выигрывает – это 2,3 и 4, а первые два проигрышных значения – это 1 и 5. Третье проигрышное значение n=9, десятое: n=43.

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

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

Проигрывает тот, кто не может сделать очередной ход.

Позиция в Простом Ниме характеризуется тройкой неотрицательных целых чисел (a,b,c).

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

Можно подсчитать, что при 0≤a≤b≤c≤29 существует 651 проигрышная позиция.

Найдите, сколько существует проигрышных позиций при 0≤a≤b≤c≤20000.

Обозначим через U(n,m) количество биномиальных коэффициентов C^k_m, которые не делятся ни на 2, ни на 5, где натуральные числа m,n и k удовлетворяют неравенству m≤k<n.

Например, U( 1234567890, 10⁷-10) = 24.

Найдите U(1234567890987654321, 10¹²-10).

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

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

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

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

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

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

Возьмем натуральное число k, и будем выписывать последовательность рациональных чисел a_i = x_i/y_i следующим образом:
a₁ = 1/k
a_i = (x_i-1+1)/(y_i-1-1) при i>1.
При этом все дроби x_i/y_i будем приводить к несократимому виду.
Мы будем продолжать последовательность до тех пор, пока нам не встретится целое число n.
Определим функцию  f(k)  как f(k) = n.
Например, при k = 20:

1/20 → 2/19 → 3/18 = 1/6 → 2/5 → 3/4 → 4/3 → 5/2 → 6/1 = 6

Поэтому f(20) = 6.

Можно проверить, что f(2) = 2, f(3) = 1 и Σf(k³) = 18764 для простых k, не превышающих 100.

Найдите Σf(k³) для простых k, не превышающих 5×10⁶.

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

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

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