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

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

Сколькими способами можно раскрасить полоску из 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.

Пусть ABC – треугольник, внутренние углы которого меньше 120 градусов, и пусть X – некоторая точка внутри треугольника, XA = p, XB = q и XC = r.
Ферма предложил Торричелли найти такое положение X, для которого сумма p + q + r обращается в минимум.
Торричелли удалось доказать, что если на сторонах треугольника ABC построить равносторонние треугольники AOB, BNC и AMC и описать вокруг них окружности, эти окружности пересекутся в общей точке T, лежащей внутри треугольника. Кроме того, он доказал, что точка T (называемая ныне точкой Торричелли-Ферма) минимизирует сумму p + q + r.

Оказывается, что когда сумма p + q + r обращается в минимум, AN = BM = CO = p + q + r, а отрезки AN, BM и CO также пересекаются в точке T.

Если для некоторого треугольника все числа a, b, c, p, q и r оказываются целыми, мы будем называть его треугольником Торричелли. Примером такого треугольника может служить треугольник со сторонами a = 399, b = 455 и c = 511.

Найдите сумму всех различных периметров треугольников Торричелли, не превышающих 300000.

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

Мы рассмотрим такую линию задержки, имеющую форму эллипса с уравнением 4x² + y²= 100.

В верхней части эллипса сделано отверстие −0.01 ≤ x ≤ +0.01 для входа и выхода луча.

В нашей задаче луч направляется из точки с координатами (0,0;10,1) внутрь эллипса, где испытывает первое отражение в точке (1,4;-9,6),

Луч отражается по обычному закону "угол падения равен углу отражения". Иначе говоря, падающий и отраженный луч образуют с нормалью в точке падения равные углы.

На рисунке слева красной линией показана траектория луча к первым двум точкам отражения. Синим обозначена касательная к эллипсу в первой точке отражения. Наклон касательной в точке эллипса с координатами (x,y) можно найти по формуле: m = −4x/y. Нормаль перпендикулярна касательной в точке падения.

На анимированной картинке справа показаны первые 10 отражений луча.

Какой длины путь проделает луч внутри эллиптической системы задержки? Результат округлите до целого.

На рисунке изображена решетка размером 3x2, состоящая из вертикальных, горизонтальных и наклонных отрезков. Для данной решетка существует 37 прямоугольников, вершины которых лежат на узлах решетки.

Есть пять решеток меньшего размера: 1x1, 2x1, 3x1, 1x2 и 2x2 (каждое из измерений этих решеток не превосходит соответствующего измерения нашей решетки 3x2). Подсчитаем, сколько прямоугольников можно разместить на узлах этих решеток:

1x1: 1
2x1: 4
3x1: 8
1x2: 4
2x2: 18

Сложив все эти числа, получим, что 1+4+8+4+18+37=72 различных прямоугольников можно разместить на узлах решеток 3x2 и меньших.

Сколько различных прямоугольников можно разместить на узлах решеток 300x200 и меньших?

Электрическая цепь состоит из одинаковых конденсаторов емкостью 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).

Фигуру, составленную из трех квадратов, имеющих общую сторону, называют тримино. Тримино бывают двух видов: угловое и прямое:

С учетом различных ориентаций можно насчитать шесть видов тримино:

Легко доказать, что при помощи тримино можно покрыть любой прямоугольник m x n, если m x n кратно трем. Например, полоску 2 х 9 можно покрыть 41 способом:

При этом симметричные покрытия мы считали различными.

Сколько существует подобного рода покрытий для прямоугольника 8 х 15?

Рассмотрим равносторонний треугольник с проведенными в нем медианами, такой как треугольник размера 1 на рисунке:

 
В треугольнике размера 1 можно найти 16 треугольников различной величины, формы, положения и ориентации.
Используя треугольники размера 1 в качестве элементов, можно составить из них треугольники большего размера, такие как треугольник размера 2 на рисунке. В треугольнике размера 2 можно насчитать 104 треугольника различной величины, формы, положения и ориентации.
Легко видеть, что треугольник размера 2 состоит из четырех треугольников размера 1, треугольник размера 3 – из 9 треугольников размера 1, а треугольник размера n - из n² треугольников размера 1.
Обозначим через T(n) количество треугольников различной величины, формы, положения и ориентации, которые можно найти в треугольнике размера n.
Получим:
T(1) = 16,
T(2) = 104

Найдите Т(50).

Два отрезка могут не иметь общих точек, могут иметь одну общую точку или бесконечно много общих точек.

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

Положение отрезка на плоскости однозначно определяется координатами его концов. Рассмотрим  три отрезка:

• отрезок L₁ с концами (27, 44) и (12, 32)
• отрезок L₂ с концами (46, 53) и (17, 62)
• отрезок L₃ с концами (46, 70) и (22, 40)

Легко проверить, что отрезки L₂ и L₃ имеют истинную точку пересечения. Один из концов отрезка L₃, а именно точка (22, 40), лежит на отрезке L₁, и поэтому точка пересечения L₁ и L₃ не считается истинной. Отрезки L₁ и L₂ не имеют общих точек. Таким образом, для трех выбранных отрезков мы найдем только одну истинную точку пересечения.

Будем теперь последовательно строить отрезки и подсчитывать их истинные точки пересечения. Чтобы построить n отрезков, нам нужно 4n координат их концов. Будем генерировать эти числа случайным образом с помощью алгоритма Блюма - Блюма – Шуба:

s₀ = 290797
s_n+1 = s_n × s_n (mod 50515093)
t_n = s_n (mod 200)

Чтобы построить отрезок, мы будем брать четыре последовательных числа. Например, координаты концов первого отрезка будут следующими:
(t₁, t₂) и (t₃, t₄)
Четыре первых числа, сгенерированные нашим алгоритмом, будут t₁=127, t₂=144, t₃=112, t₄=132, и концы первого отрезка будут иметь координаты (127,144) и (112,132).

Чтобы количество различных истинных точек пересечения превысило одну тысячу, нужно сгенерировать ровно сто отрезков: действительно, первые 99 отрезков будут иметь 992 различных истинных точек пересечения, а первые 100 отрезков – уже 1003.
Сколько необходимо сгенерировать отрезков, чтобы количество различных истинных точек пересечения превысило миллион?