Определим модифицированную последовательность Коллатца как последовательность натуральных чисел, начинающуюся с числа 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.
В качестве ответа укажите их сумму.

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

Трудолюбивый муравей случайно блуждает по клетчатой доске 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¹⁵.

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

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

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

Трехзначное число 376 в десятичной системе счисления обладает одним интересным свойством: его квадрат заканчивается теми же цифрами 3, 7 и 6, 376² = 141376.Будем называть натуральные числа, обладающие этим свойством, устойчивыми.

Устойчивые числа есть и в других системах счисления. Например, в системе счисления по основанию 14 устойчивым является число c37. Действительно, c37² = aa0c37. Наибольшее 10-значное устойчивое число в 14-ичной системе счисления равно 7337aa0c37. В десятичной записи это число равно 149429406721.

(В 14-ичной системе счисления буквами a, b, c и d мы обозначили цифры 10, 11, 12 и 13, подобно тому, как это делается в 16-ичной системе счисления.)

Найдите наибольшее 10000-значное устойчивое число в 14-ичной системе счисления, переведите его в десятичную систему, а в качестве ответа укажите 8 младших десятичных цифр.

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

Обозначим через C(x,y) окружность, проходящую через точки (x, y), (x,y+1), (x+1,y) и (x+1,y+1).

Обозначим через E(m,n) объединение m×n окружностей C(x,y), где 0≤x<m, 0≤y<n, а x, y, m и n – целые числа.

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

На рисунке показан пример эйлерова цикла без самопересечений на E(3,3).

Обозначим через L(m,n) количество эйлеровых циклов без самопересечений на E(m,n).

Например, L(1,2) = 2, L(2,2) = 37 и L(3,3) = 104290.

Найдите остаток от деления  L(6,13) на 6¹³.

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