В этой задаче мы будем рассматривать треугольники на плоскости со следующими свойствами:

• Координаты их вершин – целые числа;
• Центр описанной окружности совпадает с началом координат;
• Ортоцентр (точка пересечения высот) имеет координаты (5, 0).

Существует девять таких треугольников с периметром, не превышающим 50. Все они показаны на рисунке

A(-4, 3), B(5, 0), C(4, -3)
A(4, 3), B(5, 0), C(-4, -3)
A(-3, 4), B(5, 0), C(3, -4)

A(3, 4), B(5, 0), C(-3, -4)
A(0, 5), B(5, 0), C(0, -5)
A(1, 8), B(8, -1), C(-4, -7)

A(8, 1), B(1, -8), C(-4, 7)
A(2, 9), B(9, -2), C(-6, -7)
A(9, 2), B(2, -9), C(-6, 7) 
Сумма их площадей равна 445.
Найдите все треугольники, обладающие указанными свойствами, периметр которых не превышает 10⁵.
Легко показать, что сумма их площадей является целым числом. Она и будет ответом к этой задаче.

Корнем многочлена P(x) называют решение уравнения P(x) = 0.
Обозначим через P_n многочлен, коэффициенты которого являются десятичными знаками числа n.
Например, P₅₇₀₃(x) = 5x³ + 7x² + 3.
Ясно, что
• P_n(0) – это последняя цифра числа n,
• P_n(1) – это сумма цифр числа n,
• P_n(10) – это само число n.
Если n оканчивается на ноль, то P_n имеет корень, равный нулю. Обозначим через Y(k) количество таких натуральных n, не превышающих k, для которых соответствующий многочлен P_n имеет хотя бы один целый корень, отличный от нуля. Например, Y(100 000) = 5545.
Чему равно Y(10¹⁶)?

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

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

Даны n натуральных чисел  1 < a₁  < a₂ < ... < a_n. Будем рассматривать их линейные комбинации вида  q₁a₁ + q₂a₂ + ... + q_na_n = b, используя при этом только целые неотрицательные коэффициенты q_k ≥ 0. Заметим, что таким образом можно получить далеко не всякое значение b. Например, при n=2, a₁ = 5 и a₂  = 7 правая часть b может принимать любые натуральные значения кроме двенадцати: 1, 2, 3, 4, 6, 8, 9, 11, 13, 16, 18 и 23. Обозначим количество таких недостижимых чисел через h(a₁, a₂, ..., a_n). Таким образом, h(5,7)=12.
Также можно проверить, что h(6, 10, 15)=15, и h(14, 22, 77) = 98.
Найдите сумму всех h(p*q,p*r,q*r), где p, q и r ? простые числа, и p < q < r < 5000.

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

Функция Аккермана  рекурсивно задается для неотрицательных целых чисел  и  следующим образом:

Например, ,  и .

Чему равен остаток от деления  на 14⁸, где ?

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

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

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

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