23 ноября 2011

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

======= 141 ========

ММ141 (3 балла)

Существуют ли натуральные числа $n>1$ такие, что $\sigma(\sigma(n))<1.000000001n?$ ($\sigma(n)$ - сумма натуральных делителей числа $n$.)

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

Решение

Проще всего найти подходящее число, взяв достаточно большое (больше $10^9$) простое число $p$ так, чтобы $p^2+p+1$ тоже было простым. Тогда в качестве $n$ подойдет $p^2$.
Наименьшее подходящее $p=1000003271$. Тогда $n=1000006542010699441$, $\sigma(\sigma(n))=1000006543010702714$ и $\frac{\sigma(\sigma(n))}n\approx 1.000000000999997$.

Обсуждение

Не обязательно добиваться простоты числа $p^2+p+1$. Достаточно, чтобы оно не имело малых простых делителей.
Например, iPhonograph взял $n=252097801217^2$. Тогда $\sigma(n)=53840489083\cdot 1180399778329$ и $\sigma(\sigma(n))<1.000000001n$.
Эта идея - использовать отсутствие малых множетелей вместо простоты - позволила Андрею Халявину доказать то, что, по сути, было очевидно и остальным участникам. А именно: для любого $M$ найдутся натуральные $n$ такие, что $\sigma(\sigma(n))<n(1+\frac1M)$.
В самом деле, большинству участников (и ведущему) представляется очевидным, что существует бесконечно много простых $p$ таких, что $p^2+p+1$ тоже просто. Но "представляется очевидным" - не доказательство.
Андрей же доказал, что для каждого достаточно большого простого числа $p$ найдется показатель степени $k$ (ну очень большой!) такой, что $\sigma(p^k)$ не имеет малых делителей. И отсюда получить требуемое утвержденеие.

Гораздо более интересной, чем ММ141 является такая задача: Существуют ли натуральные числа $n>1$ такие, что $\sigma(\sigma(\sigma(n)))<1.5n?$
Но эту задачу мне решить не удалось. Ясно, что необходимым (но недостаточным) условием является существование такого натурального $n,$ что числа $n, \ \sigma(n), \ \sigma(\sigma(n))$ - нечетны.
Единственный извесстный мне нетривиальный пример дает число $n=81$.

Награды

За правильное решение задачи ММ141 Алексей Волошин, Сергей Половинкин, Николай Дерюгин, Евгений Гужавин, iPhonograph, Sirion и Анатолий Казмерчук получают по 3 призовых балла. За правильное решение более общей задачи Андрей Халявин получает 5 призовых баллов. За верные идеи (не доведенные до конца) Александр Ларин и Кирилл Веденский получают 2 и 1 балл, соответсвенно.

Эстетическая оценнка задачи 4 балла

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

Комментариев нет:

Отправить комментарий