Мальчику подарили развивающую игру-пазл "числовая змейка", состоящую из 40 фигурных элементов, которые можно собирать цепочкой один за другим и только в определенной последовательности. Элементы перенумерованы в соответствии с этой последовательностью числами от 1 до 40.

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

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

Как видно, наиболее вероятное значение M равно 3, и оно реализуется 1815264 различными способами, а 181526 — это первые шесть значащих цифр данного числа.
Найдите наиболее вероятное значение M для змейки из 40 элементов и количество способов сборки, при которых достигается это число. В качестве ответа укажите первые шесть значащих цифр результата.

Как известно, японцы застилают полы прямоугольными матами-татами, укладывая их без зазоров и перекрытий согласно строгим традиционным правилам. Хотя в разных частях Японии размер татами различается, везде его стороны соотносятся как 2:1. Поэтому стороны японской комнаты соотносятся как целые числа  a и b, а ее площадь можно выразить как s = a × b.
Кроме того, покрытие должно быть таким, чтобы в одной точке не сходилось более трех матов. Взгляните, например, на два покрытия квадратов 4×4:

 
Покрытие слева соответствует всем правилам, а покрытие справа недопустимо, поскольку в точке, отмеченной красным крестиком, сходятся четыре мата.
Ясно, что если площадь комнаты нечетная, ее нельзя застелить. Некоторые комнаты, даже имеющие целые стороны и четную площадь, все-таки нельзя правильным образом застелить татами. Будем называть такие комнаты недопустимыми. Обозначим через T(s) количество недопустимых комнат площади s.
Например, самая маленькая недопустимая комната имеет стороны 7 и 10. Ее площадь равна 70.  Остальные три комнаты площадью 70 (1×70, 2×35, 5×14) могут быть правильно застелены татами. Поэтому T(70)=1.
Аналогично, можно проверить, что T(1320) = 5, поскольку существует ровно пять недопустимых комнат площадью s = 1320:
20×66, 22×60, 24×55, 30×44 и 33×40.
Найдите сумму таких s, не превышающих 100 000 000, для которых T(s) ≥ 200.

Дан треугольник ABC, длины сторон которого выражаются различными целыми числами: |CB|<|AC|<|AB|.
Биссектрисы треугольника пересекают его стороны в точках E, F и G, как показано на рисунке:

Отрезки EF, EG и FG разбивают треугольник ABC на четыре треугольника меньшего размера: AEG, BFE, CGF и EFG.
Можно показать, что отношения площадей этих треугольников всегда выражаются рациональными числами, но иногда это отношение оказывается целым.
Найдите, сколько существует различных треугольников ABC, для которых отношение площадей треугольника ABC и треугольника AEG выражается целым числом, а |CB|<|AC|<|AB|≤50 000 000.

Представьте, что у вас появилась возможность вложить свой трудовой рубль и стать рублевым миллиардером.
Правила такие:
У вас есть один трудовой рубль. Каждый день вы инвестируете некоторую долю своего капитала  f , которую вы должны зафиксировать  раз и навсегда. Известно, что на следующий день ваши инвестиции удваиваются с вероятностью 1/2, но с такою же вероятностью вы их теряете.
Например, если вы выбрали f=1/4, то в первый день вы инвестируете 0,25 руб. Допустим, вам сопутствовала удача. Тогда к вечеру у вас будет 1,5 руб., и назавтра вы инвестируете 0,375 руб. Если фортуна на этот раз от вас отвернется, через два дня у вас останется 1,125 руб., а если повезет — 1,875 руб. Таким образом, при f=1/4 через два дня ваш капитал превысит 1,5 руб. с вероятностью 25%.
Вы решили стать миллиардером с вероятностью не менее 99% за минимальное количество дней. Сколько именно дней вам нужно запланировать на это, если вы выберете оптимальное значение f?

Лист бумаги представляет собой прямоугольник размером M × N, где M и N – натуральные числа. Отметим на его сторонах точки с целочисленными координатами, а затем будем разрезать этот лист, руководствуясь следующими правилами:
1. Каждый разрез представляет собой отрезок, соединяющий отмеченные точки.
2. Разрезы не пересекаются, но могут иметь общие концы, соответствующие отмеченным точкам.
3. Мы будем продолжать делать разрезы, пока не останется кусков, которые можно разрезать, не нарушая правил 1 и 2.
Ясно, что по указанным правилам наш лист можно разрезать несколькими способами. Некоторые из этих способов будут симметричны или отличаться друг от друга только поворотом, но мы будем считать такие способы различными. Пусть F(M,N) – это количество способов, которыми можно разрезать прямоугольный лист размером M × N.
Например, F(1,1)=2, F(1,2)=F(2,1)=6, F(2,2)=30.
Случай M=2, N=2 проиллюстрирован рисунком:

Найдите остаток от деления F(25,35) на 10⁸.

Определим уравновешенную статую как полимино, удовлетворяющее следующим требованиям:

• Статуя порядка n состоит из n единичных квадратов — блоков и еще одного квадрата — постамента (всего — n+1 квадрат).
• Центр постамента находится в начале координат (x = 0, y = 0).
• Центры всех блоков имеют положительные координаты y, так что постамент находится ниже остальных квадратов.
• Центр масс уравновешенной статуи имеет нулевую горизонтальную координату x.

Подсчитаем количество различных уравновешенных статуй порядка n. При этом статуи, симметричные друг другу относительно вертикальной оси, будем считать одинаковыми. На рисунке показаны уравновешенные статуи порядка 6. Объединив симметричные, получим 18 различных уравновешенных статуй.

Пусть Z(n) – количество уравновешенных статуй порядка n. Тогда  Z(6)=18, Z(10)=964, Z(15)= 360505.

Найдите ∑Z(n)  для 1 ≤ n ≤ 18.

Рассмотрим треугольник, длины сторон которого – целые числа a, b и с, удовлетворяющие неравенству a ≤ b ≤ c.
Будем называть такой треугольник примитивным, если наибольший общий делитель длин его сторон равен 1, т.е. gcd(a, gcd(b,c))=1.

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

Рассмотрим треугольник со сторонами 6,8 и 10. Легко подсчитать, что и его периметр, и его площадь равны 24, а отношение площади к периметру равно 1.

У треугольника со сторонами 13,14 и 15 периметр равен 42, а площадь — 84 единицам. Отношение площади этого треугольника к его периметру равно 2.

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

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

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

C₀: x²+y²=25
C₁: (x+4)²+(y-4)²=1
C₂: (x-12)²+(y-4)²=65

Линзы, заключенные между окружностями C₀ и C₁ и между C₀ и C₂, закрашены красным.

Обозначим через L(N) количество различных пар чисел (r1,r2), для которых существует линза с радиусами r1 и r2, и 0<r1≤ r2≤ N.

Можно проверить, что L(10) = 30 и L(100) = 3442.

Найдите Σ L(10^k), где 1 ≤ k ≤ 5.