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

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

Определим модифицированную последовательность Коллатца как последовательность натуральных чисел, начинающуюся с числа a₁, а далее задаваемую рекуррентно по следующим правилам:

• a_n+1 = a_n/3, когда a_n делится на 3. Обозначим такой переход от  a_n к a_n+1 символом "D".
• a_n+1 = (4a_n + 2)/3, если a_n дает остаток 1 при делении на 3. Обозначим этот случай символом "U".
• a_n+1 = (2a_n - 1)/3 , если a_n дает остаток 2 при делении на 3.

Обозначим этот случай символом "d".
Последовательность заканчивается первой встретившейся единицей.
Например, при a₁ =231 получим последовательность чисел {231,77,51,17,11,7,10,14,9,3,1} и соответствующую строку символов - "DdDddUUdDD".
Для a₁ =1004064 получим строку символов DdDddUUdDDDdUDUUUdDdUUDDDUdDD, которая начинается с DdDddUUdDD.

Найдите все a₁<10¹⁵, у которых цепочка символов, соответствующая модифицированной последовательности Коллатца, начинается с dDUddDDUUUUUdDDUdUdDUdDUddUDUd.
В качестве ответа укажите их сумму.

Трудолюбивый муравей случайно блуждает по клетчатой доске 5х5, расположенной вертикально. Он начинает свое движение в центре доски, а его траектория состоит из вертикальных и горизонтальных отрезков, соединяющих центры соседних клеток. Направление каждого следующего отрезка он выбирает случайным образом и с равной вероятностью из 2, 3 или 4 возможных вариантов, в зависимости от своего положения.

В начальный момент в каждой из пяти клеток нижнего ряда расположено по одному зерну. Если муравей свободен от ноши, и он оказывается в клетке нижнего ряда, содержащей зернышко, то он его забирает. Если муравей с зерном оказывается в свободной клетке верхнего ряда, то он оставляет зерно в этой клетке.

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

Какова средняя ожидаемая продолжительность работы муравья, если его путь на одну клетку вниз занимает 1 секунду, на одну клетку вверх – 3 секунды, а на одну клетку вправо или влево по горизонтали – 2 секунды?

Ответ дайте в микросекундах, округлив вниз до целого.

Мы хотим приготовить пиццу круглой формы, состоящую из m?n ломтей-секторов одного размера, но с разной начинкой. У нас есть m≥2 сортов начинки, и каждый сорт мы должны использовать ровно для n ломтей.

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

Например, f(2,1)=1,  f(2,2)=f(3,1)=2 и  f(3,2)=16.

Случай f(3,2) показан на рисунке:

Найдите сумму всех f(k,k), не превышающих 10¹⁵.

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

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

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

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

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

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

Сколько существует 18-значных натуральных чисел n, таких, что сумма цифр n равна сумме цифр числа 137n?

Для натурального числа k обозначим через d(k) сумму его десятичных цифр. Например, d(42) = 4+2 = 6.

Обозначим через S(n) количество натуральных чисел k < 10ⁿ, таких что 

• k делится на 69;
• d(k) = 69. 

Можно подсчитать, что S(9) = 5464, и S(20) = 36035277144875036.

Найдите остаток от деления S(20¹²) на 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.

На плоскости даны четыре точки с целочисленными координатами: A(a, 0), B(b, 0), C(0, c) и D(0, d), где 0 < a < b и 0 < c < d.

Точка P(x,y) с целочисленными координатами выбрана на отрезке AC так, что треугольники ABP, CDP и BDP оказываются подобными.

Легко показать, что при этом a=c=x+y. Поэтому, задав подходящим образом четверку чисел (x,y,b,d), мы однозначно определим размер и положение наших треугольников.

Например, четверки (x,y,b,d)=(1,1,3,4) и (x,y,b,d)=(1,1,4,3) обе удовлетворяют указанным условиям: каждая из них задает три подобных треугольника. Мы будем считать различными такие четверки, отвечающие взаимно симметричным конфигурациям.

При b+d<100 существует 110 различных четверок, задающих три подобных треугольника.

При b+d<100 000 существует 395662 различных четверок, задающих три подобных треугольника.

Сколько существует различных четверок, задающих три подобных треугольника при b+d<100 000 000?