Альберт выбирает натуральное число 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⁵? Дайте ответ в копейках, округлив его до ближайшего целого.

Рассмотрим метод кодирования черно-белых изображений при помощи квадрадеревьев для квадратного изображения размером 2^N×2^N  однобитовых пикселей. Сгенерируем кодирующую последовательность из нулей и единиц по следующим правилам:

• Первый бит относится ко всему квадрату 2^N ×2^N
• "0" означает ветвление дерева, и текущий квадрат 2ⁿ×2ⁿ разделяется на четыре меньших квадрата размером 2^n-1×2^n-1. Следующие за нулем биты содержат описание этих четырех квадратов, сначала левого верхнего, затем правого верхнего, левого нижнего и правого нижнего (именно в этой последовательности).
• "10" означает, что данный квадрат содержит только черные пиксели;
• "11" означает, что данный квадрат содержит только белые пиксели.

В качестве примера рассмотрим изображение размером 4×4, где цветными крестиками обозначены точки ветвления.

В принципе, изображение может быть закодировано несколькими различными битовыми последовательностями, например, "001010101001011111011010101010" или "0100101111101110". Первая из этих последовательностей содержит 30 битов, а вторая – только 16, и эта длина является минимальной.

Рассмотрим теперь изображения размером 2^N×2^N, построенные следующим образом:

• Пиксель с координатами x=0, y=0 соответствует левому нижнему углу изображения,
• Если  (x-2^N-1)²+(y-2^N-1)² ≤ 2^2N-2 , то соответствующий пиксель черного цвета,
• Остальные пиксели - белые.

Для изображения данного типа с N=24 найдите кодирующую последовательность минимальной длины. Сколько единиц она содержит?

В сильно  упрощенной модели белки можно рассматривать как цепочки гидрофобных (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?

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

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

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

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

При изготовлении микросхемы, состоящей из n транзисторов, образовалось k микродефектов. Дефекты распределены случайным образом, каждый дефект оказался в одном из транзисторов, и в любом транзисторе могло оказаться любое количество дефектов. Если в каком-либо транзисторе оказалось три или более дефектов, такой транзистор не работает, и вся микросхема идет в брак.

Обозначим через E(n,k) математическое ожидание количества транзисторов, содержащих дефекты, в годной микросхеме. Например, E(13,3)≈2.78571...

Найдите E(1000000,20000), умножьте на 100000, а результат округлите до целого.

Рассмотрим игру на прямоугольной клетчатой доске. Одна клетка доски не занята, на остальных стоят фишки. Каждым ходом игрок передвигает на свободную клетку одну из соседних (по вертикали или горизонтали) фишек. В начале игры пустая клетка находится в правом нижнем углу, в левом верхнем углу находится красная фишка, а на остальных клетках стоят синие фишки. Цель игры — переместить красную фишку в правый нижний угол за наименьшее количество ходов. На рисунке ниже показана последовательность ходов для доски 2 х 2.

Пусть S(m,n) -минимальное количество ходов, необходимое для перемещения красной фишки в правый нижний угол для доски m х n. Можно проверить, что S(5,4) = 25.

Существует всего 256 различных досок с сторонами m и n, не превышающими 100, для которых S(m,n) является квадратом натурального числа.

Подсчитайте количество досок со сторонами m и n, не превышающими 10¹⁰, для которых S(m,n) является квадратом натурального числа.

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

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

Например, если взять число 137, индикатор покажет последовательность "137"→"11"→"2", а затем погаснет до прихода нового числа.

Каждая цифра на индикаторе состоит из нескольких отрезков, как показано на рисунке.

Например, цифра "8" использует семь отрезков – четыре вертикальных и три горизонтальных, цифра "1" состоит из двух вертикальных, а именно, правого верхнего и правого нижнего, а цифра "4" – из четырех отрезков: левого верхнего, правого верхнего и правого нижнего вертикальных и горизонтального, лежащего посередине.

Индикатор потребляет электроэнергию, только когда отрезки включаются или выключаются. Так, включение или выключение числа 2 требует пяти единиц энергии, а числа 7 – четырех единиц энергии.

Сэм и Макс предложили разные конструкции прибора.

Работа прибора Сэма показана на картинке слева. Когда  этот прибор получает число 137, оно отображается на индикаторе, затем полностью гаснет, затем прибор показывает число 11, которое также гаснет, и, наконец, загорается число 2, которое тоже гаснет

В таблице приведен расчет энергопотребления прибора Сэма для числа 137.

"137":(2 + 5 + 4) ?× 2 = 22 переключений ("137" включается и выключается).

"11":(2 + 2) × 2 = 8 переключений ("11" включается и выключается).

"2":(5) × 2 = 10 переключений ("2" включается и выключается).

Всего получается 40 переключений и, соответственно, тратится 40 единиц энергии.

Прибор Макса (изображен справа) работает по-другому. Он не выключает каждый раз весь индикатор, а выбирает только те отрезки, которые не понадобятся для следующего числа.

Вот, как он будет работать с числом 137:

"137":2 + 5 + 4 = 11 переключений (включение трех цифр числа "137"), 7 переключений (выключение отрезков, не нужных для числа "11"). 0 переключений (число "11" уже и так горит)

"11":3 переключения (выключение первой единички и нижней части второй единички; верхняя часть остается гореть, поскольку она нужна для цифры "2").

"2":4 переключения (включение оставшихся отрезков цифры "2"), 5 переключений (выключение цифры "2").

Итого: 30 переключений.

Понятно, что прибор Макса тратит меньше энергии. Так, при подсчете однозначной суммы цифр для числа 137 экономия составляет 10 единиц энергии.

Найдите общую экономию энергии при подсчете однозначной суммы цифр для всех простых чисел, не превышающих  2×10⁷.

Обозначим через N(i) наименьшее натуральное число n,  факториал которого n! делится на (i!)^1234567890 .

Сумма N(i) для всех составных натуральных i, не превышающих 1000, равна 520804933959105.

Найдите сумму N(i) для всех составных натуральных i, не превышающих 1 000 000. В качестве ответа укажите 18 младших разрядов результата.

Обозначим через f(n) количество способов, которыми можно построить башню 3×3×n из блоков 2×1×1.

Блоки можно вращать произвольным образом. При этом башни, отличающиеся поворотом или симметрией, считаются различными.

Например, 

f(2) = 229,

f(4) = 117805,

f(6) = 64647289,

f(63) mod 123456789 = 75292539,

f(66) mod 123456789 = 56150940.

Здесь a mod q означает остаток от деления a на q.

Найдите f(6¹²³⁴⁵) mod 123456789.

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

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

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

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

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

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