k-значное натуральное число называется сбалансированным, если сумма его первых  [k/2]  цифр его равна сумме последних  [k/2] цифр. Здесь  x  обозначает округление вверх, например, [π] = 4 и [5] = 5.
Понятно, что все палиндромы являются сбалансированными, как и число 13722.
Обозначим через T(n) сумму всех сбалансированных чисел, меньших, чем 10ⁿ.
Например, T(1) = 45, T(2) = 540 and T(5) = 334795890.
Найдите остаток от деления T(2000) на 3¹⁵.

Пусть A и B - битовые последовательности,  составленные из нулей и единиц.
Если A состоит из k битов и совпадает с отрезком  длиной k, с которого начинается B (k левых битов), то A называют префиксом B.
Например, 00110 является префиксом последовательности 001101001, но не  является префиксом последовательностей 00111 и 100110.
Префиксным кодом длины n будем называть набор из n битовых последовательностей, ни одна из которых них не является префиксом другой.
Вот, например, префиксный код длины 6:
00, 010,011,100,101,1111

Теперь предположим, что затраты на передачу нуля составляют 1 копейку, а затраты на передачу единицы - 4 копейки. Тогда стоимость вышеприведенного кода составит 2+6+9+6+9+16=48 копеек. Это далеко не самый дешевый код. Самый дешевый код длины 6 стоит 35 копеек и может быть реализован двумя способами:
1,01,00000,001,0001,00001
0000,01,10,001,0001,11

А сколькими способами может быть реализован самый дешевый код длиной 946583626

Будем строить последовательность строк D0, D1,… Dn …следующим образом.
Пусть D0, - двухбуквенная строка "Fa". Для n, больших нуля, построим строку Dn, заменяя все вхождения символов "a" и "b" в строке Dn-1 следующим образом:
"a"  "aRbFR"
"b"  "LFaLb"
Тогда получим, что D0 = "Fa", D1 = "FaRbFR", D2 = "FaRbFRRLFaLbFR", и так далее.
Теперь предположим, что полученная строка является программой для плоттера, в которой символ "F" означает движение пера вперед на единицу, "R" – поворот на 90 градусов направо, а "L" – поворот на 90 градусов влево. Символы "a" и "b" на рисунок не влияют. Начальное положение пера – в начале координат (0,0), а начальное направление движения – вверх (0,1).
Получив на вход строку Dn, плоттер вычертит замысловатую ломаную, называемую "Дракон Хартера – Хейтуэя порядка n". Например, на рисунке ниже показан дракон D10. Если по команде "F" перо сдвигалось на один шаг, то в отмеченную голубым точку оно попало после 500 шагов. Ее координаты – (18,16).

Теперь представим, что плоттер начертил дракона 50-го порядка. На нем отметили точки  L и M, в которые перо попало, соответственно, после 10¹² и 10¹³ шагов. Найдите расстояние |LM|. Результат округлите вниз до целого.

Будем называть натуральное число A александрийским, если есть такие целые p, q, r, что
A = p·q·r и 1/A=1/p+1/q+1/r.
Примером александрийского числа является 630 (p = 5, q = -7, r = -18). Вот семь первых александрийских чисел:
6, 42, 120, 156, 420, 630, 930.
930 – наибольшее александрийское число, не превышающее 1000.
Найдите наибольшее александрийское число, не превышающее 1,5?10¹⁵.

Возьмем вещественное число x.
Наилучшим его приближением со знаменателем, не превышающим d, назовем квадратный корень из несократимой дроби r/s (s≤d), такой, что у любого рационального числа, лежащего ближе к x, чем r/s, знаменатель будет больше, чем d:
|p²/q²-x| < |r²/s²-x| => q>d.
Найдите сумму знаменателей наилучших приближений ³√n со знаменателем, не большим, чем 10¹⁰, для всех простых чисел n, не превышающих 100000.

Пусть S_n – правильный n-угольник, вершины которого v_k (k = 1,2,…,n) имеют координаты:

Как обычно, под многоугольником понимается фигура, включающая и ограничивающую замкнутую ломаную, и внутреннюю область.
Рассмотрим две точки на плоскости с координатами (u,v) и (x,y). Их суммой будем называть точку с координатами (u+x,v+y).
Суммой Минковского, S+T двух плоских фигур S и T будем называть множество всевозможных сумм точек, одна из которых принадлежит S, а другая принадлежит T.
Например, сумма S₃ + S₄ представляет собой шестиугольник, окрашенный на рисунке в пурпурный цвет.

Рассмотрим фигуру S₁₅₀₀ + S₁₅₀₁+ … + S₂₅₀₀, представляющую собой многоугольник. Сколько у этого многоугольника сторон длиннее, чем 1/200?

Рассмотрим число
G(n) = (n²)!/(n!)ⁿ,
где n – натуральное. Несложно показать, что G(n) – тоже натуральное число.
Например, G(3)=1680. Разложим 1680 на простые множители, а затем их сложим:

1680=2⁴×3×5×7=2×2×2×2×3×5×7,
и
2 + 2 + 2 + 2 + 3 + 5 +7 = 23.
Таким образом, сумма простых множителей числа G(3) равна 23.

Найдите сумму простых множителей числа G(4444).

Рассмотрим замкнутые ломаные, каждая из которых
• проходит через центры всех клеток шахматной доски 4×n,
• состоит из вертикальных и горизонтальных отрезков,
• не имеет самопересечений.
На рисунке изображена одна такая ломаная на доске 4×10:
 
Обозначим через T(n) количество таких ломаных для доски 4×n.
Можно показать, что T(10) = 1517.
Найдите остаток T (10¹²) по модулю 10⁸.

Существует несколько определений эллипса. Вот одно из них:
Эллипсом называется множество точек, равноудаленных от некоторой окружности и некоторой точки, лежащей внутри указанной окружности. Рисунок ниже поясняет это определение:

<page-break/>
Пусть задана окружность c с центром M(-2000,1500) и радиусом 15000, а также точка G(8000,1500). Множество точек, равноудаленных от G и c, образует эллипс e, как показано на следующем рисунке.

Рассмотрим теперь точку P с целочисленными координатами, лежащую во внешней области эллипса e, и проведем из нее прямые PS и PR, касающиеся эллипса e в точках S и R.
Подсчитайте, сколько существует на плоскости точек P с целочисленными координатами, для которых угол RPS между касательными к эллипсу  не менее 30 градусов?

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