Обсуждение и разбор марафонских задач

[VAL]

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

Задача 91 утратила статус конкурсной и может свободно обсуждаться.

Результат пpедлагаемой задачи учитываtтся дважды:
В Большом Маpафоне и в конкуpсе задач на поиск закономерности.

ММ91 (З-1) (3 балла)

Продолжить последовательность 2017, 16073, 20089, 26113.


Решение

Следующий член последовательности 40169.
Достаточно заметить, что члены последовательности простые числа, разности между которыми кратны 2008. На основании этих наблюдений легко сделать вывод, что последоваетельность состоит из простых чисел в арифметической прогрессии с первым членом 9 и разностью 2008 (прозрачный намек на месяц и год публикации задачи).

Обсуждение

Задача представлялась мне не слишком сложной. Но... Не все, взявшиеся за нее, нашли приведенное решение.
Из альтернативных вариантов интересным представляется правило построения последовательности, предложенное Евгением Машеровым:
$ a(n) = 9 + 2008*(n^3 mod 17) $


Награды

Андрей Халявин и Виктор Филимоненков получают по 3 призовых балла. Евгений Машеров получает 2 призовых балла, а Владимир Боровских - 1 призовой балл.


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

[VAL]

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

Задача 92 утратила статус конкурсной и может свободно обсуждаться в форуме.

ММ92 (3 балла)

Доказать, что натуральное число n является ненулевой степенью простого числа тогда и только тогда, когда $ n $ кратно $n-\varphi(n) $, где $\varphi(n) $ - функция Эйлера.


Решение

Пусть $ n = p^k$. Тогда $\varphi(n) = p^{k-1}*(p-1)$ и $n/(n-\varphi(n)) = p$.

Обратно, пусть $n = p_1^{k_1}*...*p_s^{k_s}$ и $n = t*(n-\varphi(n))$.
Тогда $ p_1^{k_1}*...*p_s^{k_s} = t*(p_1^{k_1}*...*p_s^{k_s} - p_1^{k_1-1}*...*p_s^{k_s-1}*(p_1-1)*...*(p_s-1))$, т.е. $ p_1*...*p_s = t*(p_1*...*p_s - (p_1-1)*...*(p_s-1))$.
Отсюда $ t/(t-1) = p_1/(p_1-1)*...*p_s/(p_s-1)$ (*)
Пусть $ p_1$ - наибольший из простых делителей n. Тогда он не может ни с чем
сократиться и из (*) следует, что t кратно $ p_1$ и, значит, $t/(t-1) \le p_1/(p_1-1)$, что строго меньше правой части (*) при s > 1.

Награды

За правильное решение задачи 92 Андрей Халявин, Влад Франк, Виктор Филимоненков, Алексей Извалов и Алексей Волошин получают по 6 призовых баллов. Евгений Машеров получает 3 призовых балла, Виктор Михайлов - 1 призовой балл.

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

[VAL]

Текущее положение участников в 10-м туре Марафона
\begin{tabular}{|l|l|r|r|c|} \hline № & Участники & 91 & 92 & \Sigma\\ \hline 1. & Виктор Филимоненков & 3 & 6 & 9\\ \hline 1. & Андрей Халявин & 3 & 6 & 9\\ \hline 3. & Владислав Франк & & 6 & 6\\ \hline 3. & Алексей Извалов & & 6 & 6\\ \hline 3. & Алексей Волошин & & 6 & 6\\ \hline 6. & Евгений Машеров & 2 & 3 & 5\\ \hline 7. & Владимир Боровских & 1 & & 1\\ \hline 7. & Виктор Михайлов & & 1 & 1\\ \hline \end{tabular}

[VAL]

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

Задача 94 утратила статус конкурсной и может свободно обсуждаться в форуме.

Предлагаемая задача не входит в тематический конкурс, но весьма близка к задачам этого конкурса по духу и происхождению. Формулировка задачи (характерная особенность 10-го тура марафона) не является эталоном математической строгости. Эту строгость легко обеспечить, но мне представляется, что в предлагаемом виде задача выглядит поинтереснее.

ММ94 (4 балла)

Чем замечательна пара чисел 568 и 638?
Докажите, что аналогичных пар бесконечно много (т.е. указаннная пара, вовсе и не замечательна)

Решение

У чисел 568 и 638 совпадают значения трех основных теоретико-числовых функций.
А именно: $ \varphi(568) = \varphi(638), \tau(568) = \tau(638), \sigma(568) = \sigma(638)$, где $\varphi(n)$ - функция Эйлера, $\tau(n)$ - количество, а $\sigma(n)$ - сумма натуральных делитей n.
Поскольку все три функции мультипликативны, одновременно умножая 568 и 638 на числа, взаимно простые с каждым из них, получим бесконечно много пар, обладающих аналогичными свойствами.

Обсуждение

Будем называть числа n и m такие, что $ \varphi(n) = \varphi(m), \tau(n) = \tau(m), \sigma(n) = \sigma(m)$, "похожими" (ничего лучше я не придумал, поскольку термины "близнецы" и "дружественные числа" уже заняты).

К моему удивлению, я не смог найти никакой информации о похожих числах, хотя мне представляется маловероятным, что ими никто не интересовался.

Пару похожих чисел назовем "примитивной", если она не получается из другой пары домножением на одно и то же число (это не означает, что числа в примитивной паре обязаны быть взаимно просты). По-видимому, примитивных пар тоже бесконечно много. Вот несколько первых примитивных пар: (568, 638), (1824, 1836), (3051, 3219), (4185, 4389), (4960, 5236), (6368, 6764), (7749, 8151). Пример пары (26355,27962) показывает, что похожие числа могут быть разной четности.

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

Зато мне известны пары не просто похожих, а "очень похожих" чисел. Вот две симпатичные парочки: (54509, 54905); (72703, 72713). $ Sq(54509) = Sq(54905), Sq(72703) = Sq(72713)$, где $ Sq(n)$ - количество квадратов по модулю n. Учитывая еще равенство значений функции Мёбиуса и внешнее (по крайней мере, в десятичной записи) сходство чисел в этих парочках, в пору вслед за поэтом воскликнуть "Не те числа назвали близнецами!" Функция $Sq(n)$ также мультипликативна, поэтому пар очень похожих чисел тоже бесконечно много.

Можно рассмотреть и другие усиления "похожести". Например, у похожих чисел 2840 и 3190 совпадают значения Carmichael's lambda function, т.е. наибольшие возможные порядки по модулям 2840 и 3190 равны.

Никому из участников Марафона не удалость узреть все перечисленные свойства, роднящие числа из условия задачи. Андрей Халявин заметил равенство значений функции Эйлера и кратность этого значения разности данных чисел. Виктор Филимоненков обнаружил равенство сумм делителей, а Андрей Извалов - некое следствие этого равенства. Кроме того, были обнаружены некоторые частности, типа "суммы цифр чисел 568 и 638 являют собой пару простых чисел близнецов".

Награды

За решение задачи 94 Андрей Халявин, Виктор Филимоненков и Алексей Извалов получают по 2 призовых балла, а Александр Расстригин - 1 призовой балл.

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

[VAL]

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

Задача 95 утратила статус конкурсной и может свободно обсуждаться в форуме.

Результат пpедлагаемой задачи учитывается дважды:
В Большом Маpафоне и в конкуpсе задач на поиск закономерности.

ММ95 (З-3) (5 баллов)

Продолжить последовательность 1, 4, 11, 20, 31, 44, 61, 100...

Решение

Это квадраты последовательных натуральных чисел, записанные в восьмиричной системе.
Следующий член последовательности 121.

Обсуждение

С этой последовательностью я промахнулся: она таки присутствует в онлайновой энциклопедии целочисленных последовательностей, причем под относительно малым номером A002441. По-видимому, я ошибся, вколачивая последовательность в поле поиска энциклопедии.

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

Виктор Филимоненков предлжил другой вариант закономерности, порождающей последовательность. Он получился громоздковатым и потому не слишком красивым.

Вздымщик Цыпа (наряду с верным решением) предложил еще один интересный вариант:
последовательные суммы натуральных чисел, взаимно простых с 10. К сожалению, этот вариант спотыкается на последнем приведенном в условии числе.

Награды

Вздымщик Цыпа получает 6 призовых баллов. Андрей Халявин, Алексей Извалов и Алексей Волошин получают по 5 баллов, а Виктор Филимоненков - 3 призовых балла.

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

[VAL]

Истек очередной срок приема решений задачи 93.
А верных решений - $\oslash$
Всвязи с этим я встал перед выбором:
1) продлить срок приема решений еще раз, повысив цену задачи до 10 баллов;
2) опубликовать решение.

Какаие будут предложения?

Решение буду принимать по такому правилу:
Если хотя бы один человек (здесь или в других местах, где публикуются марафонские задачки) попросит отодвинуть deadline - отодвину. В противном случае - опубликую решение. Но в любом случае, после некоторой паузы. Так что, немного времени у участников Марафона есть. Ну не верю я, что эта задачка не берется!

Текущее положение участников конкурса
"Поиск закономерности"
\begin{tabular}{|l|l|r|r|r|r|c|} \hline № & Участники & 91 & 95 & \Sigma\\ \hline 1. & Андрей Халявин & 3 & 5 & 8\\ \hline 2. & Вздымщик Цыпа & & 6 & 6\\ \hline 2. & Виктор Филимоненков & 3 & 3 & 6\\ \hline 4. & Алексей Извалов & & 5 & 5\\ \hline 4. & Алексей Волошин & & 5 & 5\\ \hline 6. & Евгений Машеров & 2 & & 2\\ \hline 7. & Владимир Боровских & 1 & & 1\\ \hline \end{tabular}

[VAL]

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

Результат пpедлагаемой задачи учитывается дважды:
В Большом Маpафоне и в конкуpсе задач на поиск закономерности.

ММ93 (З-2) (8 баллов)

Продолжить последовательность 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 184, 196, 225, 256, 280, 289, 316, 324, 340, 361, 364...

Решение

Это числа, являющиеся квадратами по всем натуральным модулям, не превосходящим 10.
Следующие члены последовательности: 385, 386, 400...

Обсуждение

Это всего третья (или четвертая) задача Марафона, которая так и не была решена. Но если предыдущие, оставшиеся нерешенными, я изначально оценивал как трудные, то отсутствие решений этой задачи меня удивило. Правда, один ответ поступил, но ни приведенного выше, ни другого решения там не было. А попытка угадать ответ успехом не увенчалась.
Я рассчитывал на примерно такое рассуждение:
Последовательность, очевидно, содержит все квадраты натуральных чисел. Но туда входят еще какие-то числа. Значит, что-то роднит их с квадратами... Ну и далее предполагался переход к квадратам по модулю.
По-видимому, последний шаг (первые-то тривиальны) окакзался не столь очевидным,
как это представлялось человеку, знающему решение ;)

Награды

Нет героев, нет и наград :(


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

И оценки тоже нет.

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

Предлагаемая задача не входит в тематический конкурс.
Результат учитывается только в основном Маpафоне.

ММ96 (6 баллов)

Двое играют в такую игру:
С помощью идеального генератора случайных чисел выбирают натуральное число из интервала $1..10^{100}$. Если выпавшее число свободно от квадратов, первый
игрок платит второму 200 рублей, в противном случае второй игрок платит первому 300 рублей. И т.д.
Кому выгодна такая игра?

Примечание:
Приветствуются элементарные решения.


Решение

Приведу решение Владислава Франка. Правда, вывод заменен на противоположный :)

Докажем, что игра выгодна второму игроку.
Для этого достаточно показать, что среди первых $N=10^{100}$ натуральных чисел более 60% свободно от квадратов.

Лемма.
Среди чисел от 1 до N примерно $\frac Na$ кратны a (отличие настоящего количества от этого не больше 1, причем оно может отличаться только в меньшую сторону).

Очевидно.

Следствие 1.
Среди чисел от 1 до N не более $\frac N{a_1} + \frac N{a_2} +...+ \frac N{a_k}$ кратны хотя бы одному из чисел $a_i$.

Доказательство. Следует из предыдущей леммы. Для каждого $a_i$ чисел не более, чем $\fracN{a_i}$, и это без учета того, что некоторые числа могут быть посчитаны больше одного раза.

Следствие 2.
Если $a_i$ попарно взаимно просты, то количество чисел, не кратных ни одному из них среди чисел от 1 до N примерно $N(1-\frac1{a_1})...(1-\frac1{a_k})$, причем
отличается от этого выражения не более, чем на $2^k$.

Доказательство.
Применим формулу включения-исключения. Каждое слагаемое после раскрытия скобок как раз дает количество чисел, делящихся на некоторый набор из $a_i$ с ошибкой не больше 1. А слагаемых $2^k$.

Доля чисел, не кратных $2^2, 3^2,..., 19^2$, составляет минимум
$(1-\frac1{4})(1-\frac1{9})...(1-\frac1{361}) \approx 0.614233541$ от всех, причем поправка не превышает $2^8 = 256$.

Непосредственно вычисляем, что доля чисел, кратных одному из квадратов простых между 23 и 239 не превышает $\frac1{23^2} + \frac1{29^2} +...+ \frac1{239^2} \approx 0.00947961700$
Доля чисел, кратных одному из остальных квадратов простых, не превышает суммы остальных обратных к квадратам простых. Она, в свою очередь, не превышает сумму всех обратных квадратов начиная с 240, то есть $\frac{\pi^2}{6}$ минус начальная сумма ряда, что составляет примерно 0.00417535930...

Окончательно, количество свободных от квадратов составит не меньше, чем $(0.6142335409 - 0.00417535931)*10^{100} - 256 > 0.6*10^{100}$, что и требовалось.

Обсуждение

Обоснование оказалось более тонким, чем я полагал изначально.
В связи с этим цена задачи увеличивается до 6 баллов. Пропорционально этому возрастают
и призовые баллы участников, приславших аккуратные обоснования. Участники, приславшие решения близкие к авторскому, остаются с прежними баллами.

Само уточненное решение я приведу чуть позже (когда время выкрою).

Более аккуратный подсчет показывает, что доля чисел, свободных от квадратов, примерно равна 0.6079275.

Награды

За правильное решение задачи 96 Андрей Халявин получает 6 призовых баллов, Виктор Филимоненков и Алексей Извалов получают по 4 призовых балла. Влад Франк (который при правильном ходе решения отдал таки предпочтение не тому игроку) получает 5 призовых баллов.

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

Добавлено спустя 7 минут 18 секунд:

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

Текущее положение участников в 10-м туре Марафона
\begin{tabular}{|l|l|r|r|r|r|r|r|c|} \hline № & Участники & 91 & 92 & 93 & 94 & 95 & 96 & \Sigma\\ \hline 1. & Андрей Халявин & 3 & 6 & & 2 & 5 & 6 & 22\\ \hline 2. & Виктор Филимоненков & 3 & 6 & & 2 & 3 & 4 & 18\\ \hline 3. & Алексей Извалов & & 6 & & 2 & 5 & 4 & 17\\ \hline 4. & Алексей Волошин & & 6 & & & 5 & & 11\\ \hline 4. & Владислав Франк & & 6 & & & & 5 & 11\\ \hline 6. & Вздымщик Цыпа & & & & & 6 & & 6\\ \hline 7. & Евгений Машеров & 2 & 3 & & & & & 5\\ \hline 8. & Владимир Боровских & 1 & & & & & & 1\\ \hline 8. & Виктор Михайлов & & 1 & & & & & 1\\ \hline 8. & Александр Расстригин & & & & 1 & & & 1\\ \hline \end{tabular}

[вздымщик Цыпа]

VAL в сообщении #150351 писал(а):

Легко видеть, что $S \ge R = N\cdot \prod(1-\frac1{p^2})$, где произведение берется по всем простым p, меньшим $10^{50}$.

Нет, не легко. Поясните пожалуйста, как оценивается влияние игнорирования операции взятия целой части на конечный результат.

[VAL]

вздымщик Цыпа писал(а):

VAL в сообщении #150351 писал(а):

Легко видеть, что $S \ge R = N\cdot \prod(1-\frac1{p^2})$, где произведение берется по всем простым p, меньшим $10^{50}$.

Нет, не легко. Поясните пожалуйста, как оценивается влияние игнорирования операции взятия целой части на конечный результат.

Рассмотрим отдельное конкретное p и начальный отрезок натурального ряда от 1 до n. Если n кратно $p^2$, то на рассматриваемом отрезке количество натуральных чисел, не делящихся на $p^2$ в точности равно $n(1-\frac1{p^2})$. В остальных случаях их чуть больше. И так для каждого p.

[Руст]

Замечание правильное.
Например N=35, число чисел, не делящихся ни на 4, ни на 9 равно 24 (1,2,3,5,...,35), в то время как $N(1-\frac 14 )(1-\frac 19)=\frac{70}{3}<24$.
Кстати здесь уже разбирали аналогичный вопрос, когда считаются простые числа меньше n, аналогичный приём даёт ошибку около 20%

$$n \prod_{p<n}(1-\frac 1p)<\pi(n)<n\prod_{p\le \sqrt n }(1-\frac 1p ).$$

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

[VAL]

Руст писал(а):

Замечание правильное.
Например N=35, число чисел, не делящихся ни на 4, ни на 9 равно 24 (1,2,3,5,...,35), в то время как $N(1-\frac 14 )(1-\frac 19)=\frac{70}{3}<24$.

И как это противоречит неравенству, пприведенному в решении?

Цитата:

Кстати здесь уже разбирали аналогичный вопрос, когда считаются простые числа меньше n, аналогичный приём даёт ошибку около 20%

Во-первых, для квадратов расхождения гораздо меньше. А во-вторых, возможные отклонения всегда дают превышение S над R, а не наоборот.

Цитата:

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

О том, что такая постановка задачи не является математически безупречной, я и сам предупредил перед началом десятого тура.
Делает ли это их дурацкими?
Не знаю. Противников такой постановки оказалось немало. Но есть и сторонники. То же самое касается и других задач. Достаточно посмотреть на полярные эстетические оценки, которые зачастую выставляют тем или иным задачкам участники Марафона. Поэтому оправдаюсь классической фразой: "О вкусах не спорят!". Хотя прекрасно отдаю себе отчет, что еще как спорят

[Руст]

VAL писал(а):

Во-первых, для квадратов расхождения гораздо меньше. А во-вторых, возможные отклонения всегда дают превышение S над R, а не наоборот.

Это по крайней мере надо доказать. Оценка ошибок применительно к $\pi (n)$ подробно разбирается в Прахар "Распределение простых чисел".
Утверждение, что S>R всегда - так же требует доказательства. Я думаю и здесь можно найти контпример.

[VAL]

Руст писал(а):

VAL писал(а):

Во-первых, для квадратов расхождения гораздо меньше. А во-вторых, возможные отклонения всегда дают превышение S над R, а не наоборот.

Это по крайней мере надо доказать. Оценка ошибок применительно к $\pi (n)$ подробно разбирается в Прахар "Распределение простых чисел".
Утверждение, что S>R всегда - так же требует доказательства. Я думаю и здесь можно найти контпример.

Увы! Уже нашел
Не все, что легко видеть, при ближайшем рассмотрении оказывается верным верным
Сейчас поправлю обоснование, позаимствовав аккуратное рассуждение у Влада Франка.
Мне, грешным делом, показалось, что оно избыточно.

[VAL]

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

Результат пpедлагаемой задачи учитывается дважды:\\
В Большом Маpафоне и в конкуpсе задач на поиск закономерности.

ММ95 (З-3) (5 баллов)

Продолжить последовательность 10, 21, 55, 253, 1081,...


Решение

Это произведения простых чисел pq, где q = 2p+1.\\
Следующее число - 29*59 = 1711.


Обсуждение

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

Некоторые участники не ограничились приведенным выше решением.\\
Алексей Волошин предложил альтернативную трактовку, приводящую к тому же
решению: это последовательность полупростых треугольных чисел k*(k+1)/2,
с четными k. Он предложил еще несколько разновидностей этого же обоснования.

Алексей Извалов нашел другое решение.
Последовательность 2, 3, 5, 11, 23, 47, 97... строится по правилу:
каждое следующее (начиная с третьего) число p есть наименьшее простое число,
не меньшее суммы всех предыдущих. А очередной член последовательности
равен p(2p+1) (при этом 2p+1 уже не обязано быть простым). При таком подходе
следующим членом последовательности будет 47*95 = 4465.
Здесь немного подкачало условие "начиная с третьего".


Награды

Алексей Волошин, предложивший (наряду с приведенным) красивый альтернативный
вариант обоснования закономерности получает 5 призовых баллов. Алексей Извалов
(он тоже не прошел мимо основного варианта) получает 4 призовых балла.
Вздымщик Цыпа, Андрей Халявин, Виктор Филимоненков, Александр Расстригин и
Эдвард Туркевич получают по 3 призовых балла.


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

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

Текущее положение участников в 10-м туре Марафона
\begin{tabular}{|l|l|r|r|r|r|r|r|r|c|} \hline № & Участники & 91 & 92 & 93 & 94 & 95 & 96 & 97 & \Sigma\\ \hline 1. & Андрей Халявин & 3 & 6 & & 2 & 5 & 6 & 3 & 25\\ \hline 2. & Виктор Филимоненков & 3 & 6 & & 2 & 3 & 4 & 3 & 21\\ \hline 2. & Алексей Извалов & & 6 & & 2 & 5 & 4 & 4 & 21\\ \hline 4. & Алексей Волошин & & 6 & & & 5 & & 5 & 16\\ \hline 5. & Владислав Франк & & 6 & & & & 5 & &11\\ \hline 6. & Вздымщик Цыпа & & & & & 6 & & 3 & 9\\ \hline 7. & Евгений Машеров & 2 & 3 & & & & & & 5\\ \hline 8. & Александр Расстригин & & & & 1 & & & 3 & 4\\ \hline 9. & Эдвард Туркевич & & & & & & & 3 & 3\\ \hline 10. & Владимир Боровских & 1 & & & & & & &1\\ \hline 10. & Виктор Михайлов & & 1 & & & & & &1\\ \hline \end{tabular}

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

Текущее положение участников конкурса
"Поиск закономерности"
\begin{tabular}{|l|l|r|r|r|r|r|r|c|} \hline № & Участники & 91 & 93 & 95 & 97 & \Sigma\\ \hline 1. & Андрей Халявин & 3 & & 5 & 3 & 11\\ \hline 2. & Алексей Волошин & & & 5 & 5 & 10\\ \hline 3. & Вздымщик Цыпа & & & 6 & 3 & 9\\ \hline 3. & Виктор Филимоненков & 3 & & 3 & 3 & 9\\ \hline 3. & Алексей Извалов & & & 5 & 4 & 9\\ \hline 6. & Александр Расстригин & & & & 3 & 3\\ \hline 6. & Эдвард Туркевич & & & & 3 & 3\\ \hline 8. & Евгений Машеров & 2 & & & & 2\\ \hline 9. & Владимир Боровских & 1 & & & & 1\\ \hline \end{tabular}

[VAL]

VAL в сообщении #146968 писал(а):

Будем называть числа n и m такие, что $ \varphi(n) = \varphi(m), \tau(n) = \tau(m), \sigma(n) = \sigma(m)$, "похожими" (ничего лучше я не придумал, поскольку термины "близнецы" и "дружественные числа" уже заняты).

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

Уже нашел. Вот две тройки похожих чисел: (106120,115938,122322), (227304, 228000,229500).