Как известно, японцы застилают полы прямоугольными матами-татами, укладывая их без зазоров и перекрытий согласно строгим традиционным правилам. Хотя в разных частях Японии размер татами различается, везде его стороны соотносятся как 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.

Лист бумаги представляет собой прямоугольник размером 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.

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

Рассмотрим построение последовательности графов Серпинского:

• Граф Серпинского первого порядка S1 представляет собой равносторонний треугольник (три вершины и три соединяющих их ребра).
• Граф Серпинского  S_n+1 порядка n+1 представляет собой объединение трех графов S_n, имеющих попарно общую вершину, как показано на рисунке:

Пусть C(n) — количество циклов, проходящих через каждую вершину  S_n ровно один раз. Например, C(3)=8, поскольку граф  S₃ позволяет построить ровно 8 подобных циклов, как показано на рисунке: 

Легко проверить, что 

C(1) = C(2) = 1

C(5) = 71328803586048

C(10 000) mod 10⁸ = 37652224

C(10 000) mod 7¹⁰ = 221100305

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

Найдите C(C(C(10 000))) mod 7¹⁰.

Обозначим через 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.

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

Пусть C(r) – сфера с центром в начале координат (0,0,0) и радиусом r.

Пусть Z(r) – множество точек сферы C(r) с целыми координатами.

Пусть T(r) – множество сферических треугольников с вершинами, принадлежащими Z(r). Вырожденные сферические треугольники с вершинами, принадлежащими одному большому кругу, не включаются в T(r).

Пусть A(r) – наименьшая площадь треугольника из T(r), а B(r) =(4πr²)/A(r) – величина, обратная доле площади сферы, которую занимает наименьший сферический треугольник.

Например, A(14) ≈3,294040, а B(14) ≈ 748.

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

Будем вырезать из бумаги в клетку прямоугольники размером w × h клеток, где w и h – натуральные числа. Некоторые из них можно разрезать по клеточкам на две части так, что из этих частей составится новый прямоугольник другого размера.
Например, прямоугольник размером 9 × 4 клетки можно превратить в прямоугольники 18 × 2, 12 × 3 или 6 × 6, как показано на рисунке:

Аналогично, из прямоугольника 9 × 8 можно сделать прямоугольники размером 18 × 4 и 12 × 6 клеток.
Обозначим через F(w, h) количество различных прямоугольников, которые можно получить из прямоугольника размером w × h клеток. При этом прямоугольники с размерами a × b и b × a считаются одинаковыми, а прямоугольники, конгруэнтные исходному, не учитываются.
Тогда получим: F(2,1) = 0, F(2,2) = 1, F(9,4) = 3 и F(9,8) = 2.
Пусть G(N)=Σ F(w, h) для всех 0 < h ≤ w ≤ N.
Можно проверить, что G(10) = 55, G(10³) = 971745, а G(10⁵) = 9992617687.
Найдите ΣG(10^k), где 1≤k≤12. В качестве ответа укажите 8 младших цифр результата.

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

Одну из ячеек занимает пчелиная матка.
Обозначим через B(L) количество ячеек, удаленных от матки на расстояние L (в этой задаче мы будем измерять расстояния между центрами ячеек).
Считая соты достаточно большими, получим  B(√3) = 6, B(√21) = 12 и B(111 111 111) = 54.

Найдите количество таких L ≤ 3•10¹¹, для которых B(L) = 378.

Ответ: