На рисунке в клетки поля размером 5x5 записаны по спирали последовательно простые числа.

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

Шахматная доска пронумерована "змейкой": нижняя (первая) строка слева-направо числами 1-8, следующая (вторая) справа налево - 9-16, следующая снова слева направа - 17-24 и так далее.

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

На рисунке представлен неориентированный граф, содержащий семь вершин и 12 ребер, суммарный вес которых составляет 243.

Тот же граф можно представить следующей матрицей:

Однако, некоторые ребра можно "сэкономить", не нарушая связности графа. Граф, в котором достигается максимальная экономия, представлен ниже. Его вес - всего 93, а "экономия" по сравнению с исходным графом составляет 243-93 = 150.

Пусть задан граф, содержащий 40 вершин, занумерованных числами от 0 до 39. Вес ребра, соединяющего вершины i и j, выражается формулой
w_ij =  w_ji = (69069(i - j)²(i + j))(mod 1000)

Какой максимальной экономии можно добиться, удаляя лишние ребра без потери связности графа?

В вашем распоряжении n>0 одинаковых сопротивлений и батарейка. При каком минимальном n из них можно собрать электрическую схему, значения силы тока во всех n+1 элементах которой попарно различны? (Элементы схемы — это все сопротивления и батарейка.) В ответе как-нибудь изобразите найденную схему и укажите значения силы тока во всех её элементах.

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

Количество заработанных очков зависит от того, куда дротик воткнулся. Попадание дротика за пределами внешнего красно-зеленого кольца  не приносит очков. Попадание дротика в черный или желтый сектор внутри этого кольца приносит очки в соответствии с номером сектора. Внешнее красно-зеленое кольцо означает удвоение числа сектора, а внутреннее  - утроение. Два концентрических круга в центре мишени образуют "яблочко". Наружный зеленый круг дает 25 очков, а внутренний красный - 50. Он считается двойным (25x2=50).

Существует несколько вариантов игры. В самом распространенном из них игроки в начале игры имеют 301 или 501 очко, а затем последовательно вычитают заработанные очки. Выигрывает тот, у кого останется ровно ноль очков. Однако победа засчитывается только в том случае, если последний бросок, сводящий число очков к нулю, был "двойным", то есть попал во внешнее красно-зеленое кольцо или в красное "яблочко". В противном случае, а также когда после серии из трех бросков получается отрицательная сумма очков или единица, вся серия не засчитывается, и счет остается прежним.

Положение, при котором участник может завершить игру, называют "чекаут" (англ. checkout). Максимальный чекаут возможен при 170 очках: T20 T20 D25 (два попадания с утроением в сектор 20 и одно попадание в красное яблочко).

Есть ровно 11 способов окончить игру при шести очках:

D3   
D1  D2   
S2  D2   
D2  D1   
S4  D1   
S1  S1  D2
S1  T1  D1
S1  S3  D1
D1  D1  D1
D1  S2  D1
S2  S2  D1

Обратите внимание, что серии D1 D2 и D2 D1 считаются различными, поскольку последние броски с удвоением у них различны. Однако комбинации S1 T1 D1 и T1 S1 D1 считаются  одинаковыми. Кроме того, мы не учитываем промахи. D3 считается тем же исходом, что и 0 D3 или 0 0 D3.
Всего существует 42336 различных способов завершить игру. При оставшихся 6 очках можно завершить игру 11 способами, при 8 - 22 способами.
А при каком количестве очков можно завершить игру наибольшим числом способов?

Изучим целые положительные решения уравнения
1/x + 1/y =1/n

при различных натуральных n.
Для  n = 4 уравнение будет иметь ровно три различных решения:
1/5 + 1/20 = 1/4
1/6 + 1/12 = 1/4
1/8 + 1/8 = 1/4

Для какого n, не превышающего 15·10¹⁵, уравнение будет иметь больше всего решений?
Замечание: Эта задача - существенно усложненная версия задачи 197. Решить ее "в лоб" вряд ли удастся.

Рассмотрим четырехзначные простые числа с повторяющимися цифрами. Ясно, что все цифры не могут быть одинаковы: 1111 делится на 11, 2222 делится на 22, и т.д. Но есть девять четырехзначных простых чисел, содержащих три единицы:
1117, 1151, 1171, 1181, 1511, 1811, 2111, 4111, 8111
Обозначим через M(n, d) максимально возможное количество повторяющихся цифр в n-значном простом числе, где d - повторяющаяся цифра. Пусть N(n, d) - количество таких чисел, а S(n, d) - их сумма.
Тогда M(4, 1) = 3 - максимальное количество единиц в четырехзначном простом числе, всего существует N(4, 1) = 9 таких чисел, а их сумма равна S(4, 1) = 22275. Оказывается, что при d = 0 в четырехзначном простом числе может быть не более M(4, 0) = 2 нулей, и N(4, 0) = 13.
Таким образом, мы получим следующие результаты для четырехзначных простых чисел:

Найдите сумму всех S(n, d) для 3 ≤ n ≤ 10 и 0 ≤ d ≤ 9.

Будем называть возрастающим натуральное число, десятичные цифры которого не убывают слева направо, например 134468.
Аналогично, убывающим числом будем называть такое натуральное число, цифры которого не возрастают слева направо, например 864431.
Оказывается, что возрастающие числа встречаются реже, чем убывающие. Так, среди первых ста натуральных чисел имеется 54 возрастающих и 64 убывающих (18 чисел, состоящих из одинаковых цифр, являются сразу же и возрастающими, и убывающими), а в первой тысяче натуральных чисел - 219 возрастающих и 283 убывающих.
Обозначим через R(n) отношение количества убывающих чисел к количеству возрастающих среди первых n натуральных чисел. Например, оказывается, что R(11)=11/10, R(1127)=11/9.
Найти R(n), где n – число, состоящее из 111 единиц (Оказывается, это целое число).

На рисунке изображена прямоугольная полоска из восьми выстроенных в ряд клеток. Идущие подряд клетки одного цвета образуют блоки. При этом красные блоки содержат не менее трех клеток, а черные – не менее двух. Как видно из рисунка, полоску из восьми клеток можно раскрасить таким образом четырнадцатью способами.

Сколькими способами можно раскрасить полоску из 50 клеток, следуя тем же правилам?

Замечание: Это более сложный вариант задачи 114.

Как и в задаче 114, будем рассматривать прямоугольные полоски, состоящие из n выстроенных в ряд клеток. Идущие подряд клетки одного цвета образуют блоки. При этом красные блоки содержат не менее m_r клеток, а черные – не менее m_b.

Обозначим через F(m_r, m_b,n) число способов, которым такая полоска может быть построена, например F(3, 2, 8)=14 (см. рисунок).

Кроме того, F(3, 2, 34)= 856506 и F(3, 2, 35)= 1309554.

Это означает, что n=35 – минимальное значение, при котором функция F(3, 2,n) превосходит миллион.

Аналогично, F(5, 3, 46) = 849735 и F(5, 3, 47)= 1172897, и 47 – первое значение n, при котором F(5, 3, n) больше миллиона.

Найдите минимальное значение n, при котором F(111, 100, n) > 1 000 000.