Определим для натурального числа n функцию S(n) равной сумме цифр в его десятичной записи. Найдите наименьшее M, такое, что среди простых чисел меньших 1000000, количество чисел для которых S(n)=M максимально.

Посмотрите на таблицу. Легко проверить, что максимальная сумма чисел, стоящих подряд вдоль одного из диагональных направлений, равна 16 (= 8 + 7 + 1).

Давайте теперь рассмотрим ту же задачу для таблицы большего размера. Для этого будем использовать генератор случайных чисел Фибоначчи с запаздываниями:
Для 1≤k≤55, s_k = [100003 - 200003·k + 300007·k³)] (mod 1000000) - 500000.
Для 56≤k≤4000000, s_k = [s_k-24 +s_k-55 + 1000000] (mod 1000000) - 500000.
(Здесь x(mod y) означает остаток от деления x на y).
Например, s₁₀ = -393027 и s₁₀₀ = 86613.

Заполним при помощи первых четырех миллионов чисел этого генератора таблицу 2000×2000. Заполнять таблицу будем последовательно, строка за строкой.
Найдите максимальную сумму чисел, стоящих подряд вдоль какого-либо из диагональных направлений в получившейся таблице.

Володя написал программу, которая складывает в столбик два числа. К сожалению, он не разобрался, как правильно переносить единицу из одного разряда в следующий. Поэтому программа стала выполняться следующим образом. Сначала она складывает последние цифры обоих чисел и записывает результат, как в случае, если он однозначный, так и в случае, если он двузначный. Затем программа складывает предпоследние цифры обоих чисел и результат сложения приписывает слева к результату предыдущего сложения. Далее процесс повторяется для всех разрядов. Если в одном числе цифр меньше, чем в другом, то программа размещает нули в соответствующих разрядах более короткого числа.
Федя хочет доказать Володе, что его способ сложения не обладает свойством ассоциативности. В частности, Федя утверждает, что существуют три числа, для которых важен порядок, в котором их складывают (при этом разрешается складывать числа в любом порядке, например можно сначала сложить первое число и последнее, а затем прибавить к ним среднее). Федя привел даже пример трех таких чисел.
Сколько существует троек чисел a, b, c, таких, что a < b < c < 1000000 и a+(b+c) < (a+b)+c.

Попробуем записать число 1/3 в виде суммы обратных квадратов различных натуральных чисел. Например, используя числа {2, 5, 6, 10, 15, 30}:

Используя числа до 45 включительно, это можно сделать четырьмя способами. Вот соответствующие наборы чисел:
{2, 5, 6, 10, 15, 30}
{2, 5, 7, 10, 14, 15, 21, 30}
{2, 4, 12, 14, 15, 20, 28, 42}
{2, 6, 7, 9, 10, 12, 20, 28, 35, 36, 45}
Сколькими способами можно записать 1/3 в виде суммы обратных квадратов различных натуральных чисел, не превышающих 80?

Была исходная последовательность символов:
AAABBABB

В конец этой последовательности дописали ее копию, но развернутую зеркально (символы взяли в обратном порядке). Получилась строка:
AAABBABBBBABBAAA

Эту операцию повторили еще три раза, каждый раз дописывая в зеркальном отображении всю последовательность, полученную на предыдущем шаге. В результате получилась последовательность из 128 символов. В получившейся последовательности заменили все тройки идущих подряд символов BAB на ABA. Эту операцию повторяли до тех пор, пока тройки идущих подряд символов BAB не перестали встречаться в последовательности. Сколько букв B осталось в результирующей последовательности?

Электрическая цепь состоит из одинаковых конденсаторов емкостью C. Конденсаторы можно соединять последовательно или параллельно в блоки, которые также можно соединять последовательно или параллельно в "суперблоки" большего размера, и так далее.

Используя эту процедуру и не более n одинаковых конденсаторов, мы можем собрать некоторое количество цепей различной суммарной емкости. Например, используя не более 3 конденсаторов с электрической емкостью 60μF каждый, мы можем получить 7 различных значений общей емкости цепи:

(Известно, что, соединяя конденсаторы C₁, C₂ … параллельно, мы получим общую емкость C_T=C₁+C₂+..., а соединяя последовательно – общую емкость )
Если мы обозначим через D(n) количество различных значений емкости электрических цепей, которые можно собрать, используя не более n одинаковых конденсаторов, то получим D(1)=1, D(2)=3, D(3)=7,...
Найдите D(19).

Какое минимальное количество спичек необходимо для того, чтобы выложить на плоскости 1111111 квадратов со стороной в одну спичку? Спички нельзя ломать и класть друг на друга. Вершинами квадратов должны быть точки, где сходятся концы спичек, а сторонами - сами спички.

Посмотрим на десятичную запись первых неотрицательных целых чисел:

0 1 2 3 4 5 6 7 8 9 10 11 12....

Выберем одну из цифр, например единицу (d=1), а затем начнем выписывать наши числа, подсчитывая количество использованных единиц. Обозначим полученное количество через  f(n,1) и запишем его против каждого числа n. Вот что получится:

n    f(n,1)
0    0
1    1
2    1
3    1
4    1
5    1
6    1
7    1
8    1
9    1
10    2
11    4
12    5

Заметьте, что f(n,1) не равно 3 ни при каких n.
Уравнение f(n,1)=n имеет решения n=0 и n=1, а следующее решение - только n=199981.

Аналогично, подсчитаем, сколько раз мы использовали цифру d, и обозначим полученное количество через f(n,d).
Заметим, что для каждой цифры d, кроме нуля, n=0 является первым решением уравнения f(n,d)=n.
Обозначим через s(d) сумму всех решений уравнения f(n,d)=n. Например, s(1)=22786974071.

Найдите ∑ s(d) при 0 ≤ d ≤ 9.

Замечание: Если для какого-то n f(n,d)=n для нескольких значений d, n необходимо учитывать каждый раз для каждой цифры d.

Рассмотрим диофантово уравнение ¹/_a+¹/_b= ^p/_10ⁿ, где a, b, p, n - положительные целые числа, и a ≤ b. При n=1 это уравнение имеет 20 приведенных ниже решений:

А сколько решений будет иметь это уравнение при n=16?

Блоха запрыгнула на круглый стол для игры в "Что? Где? Когда?" незадолго до начала очередной игры. На секторах стола уже были разложены конверты с вопросами. Блоха решила заранее прочитать все вопросы, чтобы у нее было больше времени подумать над ответами.

Круглый игровой стол поделен на 10⁹ секторов, занумерованных по часовой стрелке числами от 1 до 10⁹. Блоха запрыгнула на первый сектор. С него она может либо перебежать на соседний, либо перепрыгнуть через 2 сектора (например, если стол делится на 12 секторов, то с сектора номер 1 блоха может за одно действие попасть на сектора с номерами 2, 4, 10 и 12). Блоха хочет побывать на каждом секторе ровно 1 раз и вернуться обратно на первый сектор, откуда она спрыгнет и убежит думать над вопросами. Определите, сколькими способами она сможет совершить свое путешествие. Выведите в качестве ответа количество способов по модулю 10⁹+9.