Разбор задачи ММ129 математического марафона

================

ММ129

Будем заполнять бесконечный клетчатый лист бумаги натуральными числами по спирали (каждый следующий виток начинается на вертикали, в которой стоит единица):



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

================

Решение.

Для числа 2 имеем индекс простоты, равный 5. Докажем, что больше чисел с таким индексом быть не может. Для соседей единицы их индексы простоты проверяются непосредственно, а для остальных чисел справедливы следующие рассуждения.

Поскольку от витка к витку количество цифр увеличивается на 4, то т.к. четные/нечётные числа стоят столбцами. Значит, у каждого числа среди восьми разностей шесть будут нечётными.

Поскольку при данном способе заполнения в соседних клетках не будут стоять чисел, различающихся на 2, то и простых разностей не будет больше 6.
Но по правилу построения для большинства чисел две из нечётных разностей будут единицами. Ровно одна разность будет равняться одному для чисел в двух столбцах: идущем вверх от единицы и смежном с ним слева.

Рассмотрим число, стоящее в столбце, идущем вверх от единицы.
Общий вид такого числа (если начинать индекс n с нуля).
Соседями его будут:




Разностями - кандидатами в простые будут:
Северо-запад:
Запад:
Юго-запад:
Северо-восток:
Восток:

Но, перебирая возможные остатки от деления n на 3, увидим, что среди этих чисел хотя бы одно будет делиться на 3. Т.к. ровно трём разность не может равняться, то среди разностей будет не более четырёх простых.

Теперь рассматриваем смежный слева столбец. Числа этого столбца, смежные с , будут иметь вид Соседями их будут:




Северо-запад:
Запад:
Северо-восток:
Восток:
Юго-восток:

И, опять-таки, не больше четырёх из этих разностей будут простыми.

Обсуждение

Задачу про спиральное заполнение гексагональной сетки я решал, участвуя в турнире Эйлера на сайте Диофант.ру. Мне понравилось, что за несколько пугающим построением, заставляющем прикинуть возможность моделирования всего процесса на компьютере, кроется эффектный шаг, устраняющий эту необходимость.

Награды

За правильное решение задачи Виктор Филимоненков, Алексей Волошин, Анатолий Казмерчук, Сергей Половинкин и Пашуткин Дмитрий получают по 5 баллов.

Эстетическая оценка задачи 5

================

Разбор задачи ММ129 подготовил Алексей Извалов

Разбор задачи ММ124 математического марафона

===============

ММ124 (4 балла)

Пусть - сумма n первых простых чисел.
Доказать, что является простым тогда и только тогда, когда существует такое простое число q, что кратно .

================

Решение

Приведу решение Виктора Филимоненкова.

1. Пусть такое число q для существует. Тогда не делится ни на одно из чисел . Действительно, если , где p - одно из первых n простых, и кратно p, то и q кратно p, а поскольку q простое, то q = p. Тогда - делится на , в то время как . То есть сумма n чисел, не меньших 2, лишь на одно слагаемое меньше их произведения, что для суммы первых протсых чисел, очевидно, не верно начиная с (для и утверждение доказывается непосредственно).

Но раз не делится на , то оно простое. Действительно, , а поскольку , то не делится на все простые, меньшие квадратного корня из , то есть простое.

2. Пусть, наоборот, простое. Покажем, что простое q существует. Рассмотрим арифметическую прогрессию с первым членом и разностью . Поскольку простое, то оно взаимно просто с , и значит в этой прогрессии, по теореме Дирихле, есть бесконечное количество простых чисел. Любое из них годится в качестве q.

Обсуждение

Для меня было неожиданностью, что ряд опытных, искушенных марафонцев испытывали некоторые затруднения при решении этой, на мой взгляд, простой задачи. (Конечно, теорема Дирихле о простых числах в арифметической прогрессии - утверждение нетривиальное. Но зато широко известное :)). При желании, я мог придраться к большему числу решений. Читая утверждения типа "составное число, меньшее , не может иметь делителей, больших p", я был близок к "кровопролитию". Но сдержался :)

В OEIS последовательность простых представлена под номером A013918.

Интересно, конечно ли множество n, для которых . Интуиция подсказывает, что:
1) бесконечно;
2) доказательство первого пункта нетривиально :)

Награды

За правильное решение этой задачи Виктор Филимоненков, Эдвард Туркевич, Анатолий Казмерчук, Алексей Волошин и Mathusic получают по 4 призовых балла. Сергей Половинкин, Николай Дерюгин и Евгений Машеров получают по 2 призовых балла.

Эстетическая оценка задачи 4.3

================

Обзор задачи ММ124 подготовлен Владимиром Лецко

Решения задач 5

Задача 16
Перебор даёт множество таких четвёрок, к примеру, 2, 3, 4, 5 или 1758, 1759, 1760, 7161

Задача 17
Поскольку и 3+10+15=28, то тройка (3, 10, 15) будет решением исходного уравнения.

Задача 18
AlexAlkin (nazva.net) предлагает следующее решение:

Пошагово будем отнимать общие целые части дробей слева и соответственно справа от искомой дроби. После дроби переворачиваем и процедуру повторяем.
Итак





























Здесь слева число, большее единицы, а справа – меньшее.
Единственным натуральным числом между числами и будет число 1.

Тогда будет иметь место система уравнений:
41m - 71n = 1
26n - 15m = 1
которая даст нам искомые m=97 n=56 и соответственно дробь с наименьшим знаменателем удовлетворяющая условию

Призовые баллы получают:

Николай (smekalka.pp.ru) - 5
sek140675 (nazva.net) - 5
Семён Знаковян (*ALEX ALKIN*, nazva.net) – 8
Alexisto - 9