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

[VAL]

Текущее положение участников в XVI туре Математического марафона
\begin{tabular}{|l|l|r|r|r|r|r|r|r|r|r|r|r|} \hline №& Участники& 151 & 152 &153 & 154 & 155 & 156 & 157 & 158 & \Sigma \\ \hline 1.& Олег Полубасов & 5 & 9 & 4 & 5 & 4 & 5 & 6 & 7 & 45 \\ \hline 2.& Сергей Половинкин & 4 & 7 & 4 & 5 & 4 & 5 & 6 & 8 & 43 \\ \hline 3.& Виктор Филимоненков & 4 & 6 & 4 & 4 & 4 & 5 & 6 & 7 & 40 \\ \hline 4.& Анатолий Казмерчук & - & 9 & 2 & 5 & 4 & 5 & 6 & 7 & 38 \\ \hline 4.& Алексей Волошин & 4 & 4 & 2 & 5 & 4 & 5 & 6 & 8 & 38 \\ \hline 6.& Николай Дерюгин & 4 & 7 & 4 & - & 4 & 5 & 6 & 6 & 36 \\ \hline 7.& Дмитрий Пашуткин & - & - & 4 & 5 & 4 & 5 & 6 & - & 24 \\ \hline 8.& Евгений Машеров & - & - & - & 5 & -& 5 & - & - & 10 \\ \hline 9.& Евгений Гужавин & 4 & - & - & - & - & 5 & - & - & 9 \\ \hline 10.& Александр Князев & 1 & 2 & 3 & 1 & - & - & - & - & 7 \\ \hline 11.& nnosipov & - & - & - & - & - & - & 6 & - & 6 \\ \hline 12.& Елизавета Евдокимова & - & 2 & - & - & - & - & - & - & 2 \\ \hline 13.& Екатерина Шарпанова & - & 1 & - & - & - & - & - & - & 1 \\ \hline \end{tabular}

[VAL]

========= 159 ==========

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

Для натурального числа n, большего 1, обозначим через $qu(n)$ отношение суммы количеств единиц во всех записях числа n в системах счисления с натуральными основаниями, большими 1, к самому числу n.
Найти наибольшее и наименьшее значение $qu(n)$ и предел $qu(n)$ при n, стремящимся к бесконечности.
Конечны ли множества чисел, для которых $qu(n)$: меньше 1; больше 1; равно 1?

Решение

Пусть $g$ - основание системы счисления. При $g>n$ число $n$ будет записываться одной цифрой, отличной от 1. Поэтому суммарное число единиц во всех записях $n$ конечно.
Очевидно, что при $\frac{n}{2} < g \le n$ $n$ будет двухзначным, причем первая цифра будет 1. При $g=n-1$ единицами будут обе цифры в записи $n$. Поэтому при $n>2 \ \ qu(n)>{\frac{1}{2}}$. В то же время, $qu(2)={\frac{1}{2}}$. Значит, наименьшее значение $qu(n)$ равно $\frac{1}{2}$.
Для $\sqrt(n)<g \le {\frac{n}{2}}$ $n$ по-прежнему двузначно, но первая цифра отлична от единицы, а вторая не может быть единицей часто. Суммарное количество всех цифр (и, тем более, всех единиц) во всех записях $n$ с основаниями $2\le g \le \sqrt n$ с ростом $n$ растет медленнее, чем $\frac{n}{2}$.
Из этих соображений следует простой план решения задачи: показать, что $\lim \limits_{n\to\infty}qu(n)=\frac{1}{2}$; найти какое-то $n_0$, что для всех $n>n_0 \ \ qu(n)<1$, и перебрать значения $qu(n)$ для $n$, не превосходящих $n_0$.
Наименьшим количеством перебираемых $n$ удалось обойтись Олегу Полубасову (см. приложение).

Ответ:
наименьшее значение $qu(2)={\frac{1}{2}}$;
наибольшее значение $qu(7)={\frac{9}{7}}$;
$\lim \limits_{n\to\infty}qu(n)=\frac{1}{2}$;
при $n \in \{5,7,9,11,13,31\}$ значение $qu(n)$ больше 1;
при $n \in \{3,4,6,10,15,21\}$ значение $qu(n)$ равно 1;
при остальных $n$ значение $qu(n)$ меньше 1.

Обсуждение

Я ожидал, что кто-либо из участников по традиции обобщит задачу ММ159. Тем более, что естественные обобщения напрашиваются. Однако, не дождался. Придется самому.

Обозначим через $qu_c(n)$ отношение суммарного количества цифр "$c$" в записях натурального числа $n$ ($n>c$) во всех системах счисления с натуральными основаниями $g$ ($g>1$) к самому числу $n$.
Легко видеть, что при $c>1$ $qu_c(n)=0$, для всех $n\in \{c+1,c+2,\dots,2c\}$.
Не сложно доказывается и то, что $\lim \limits_{n\to\infty}qu_c(n)=\frac1{c(c-1)}$. Причем при достаточно больших $n$ значение $qu_c(n)$ всегда больше этого предела.
Особняком стоит случай $c=0$. $\lim \limits_{n\to\infty}qu_0(n)=0$. Однако стремление к нулю очень неравномерное, с резкими всплесками на числах, имеющих много мелких делителей.

Более содержательным представляется вопрос о наибольших значениях $qu_c(n)$ при различных $c$.
Обозначим через $mqu( c )$ наибольшее значение функции $qu_c(n)$. Ниже приведена таблица значений $mqu( c )$ для небольших $c$ (во втором столбце указаны $n$, при которых достигается наибольшее значение; в третьем - суммарное количество цифр "$c$" в записях этого $n$).

$$\begin{array}{|l|l|l|l|} \hline c & n & \Sigma & mq( c )\\ \hline 0 & 4 & 3 & \frac34\\ \hline 1 & 7 & 9 & \frac97\\ \hline 2 & 26 & 14 & \frac7{13}\\ \hline 3 & 15 & 5 & \frac13\\ \hline 4 & 28 & 6 & \frac3{14}\\ \hline 5 & 35 & 6 & \frac6{35}\\ \hline 6 & 54 & 7 & \frac7{54}\\ \hline 7 & 79 & 9 & \frac9{79}\\ \hline 8 & 80 & 8 & \frac1{10}\\ \hline 9 & 69 & 6 & \frac2{23}\\ \hline 10 & 130 & 10 & \frac1{13}\\ \hline 11 & 71 & 5 & \frac5{71}\\ \hline 12 & 192 & 11 & \frac{11}{192}\\ \hline 13 & 73 & 4 & \frac4{73}\\ \hline 14 & 74 & 4 & \frac2{37}\\ \hline 15 & 63 & 3 & \frac1{21}\\ \hline \end{array}$$

Полагаю второй и третий столбцы этой таблицы - достойные кандидаты в OEIS.

Гипотеза 1. При $c>0$ $mqu( c )$ строго монотонна.
Гипотеза 2. При каждом $c$ существует единственное значение $n$, при котором достигается наибольшее значение $qu_c(n)$.
Гипотеза 3. Значения $n$, для которых $qu_c(n)$ достигает $mqu( c )$ уникальны (не повторятся при других $c$).

Для больших $c$ $mqu(c)$ существуют целые участки, где $mqu(c)$ ведет себя закономерно. Вот пример такого поведения:

$$\begin{array}{|l|l|l|} \hline c & n & \Sigma\\ \hline 54 & 474 & 7\\ \hline 55 & 475 & 7\\ \hline 56 & 476 & 7\\ \hline 57 & 477 & 7\\ \hline 58 & 478 & 7\\ \hline 59 & 479 & 7\\ \hline \end{array}$$

По-видимому, с ростом $c$ такие участки будут встречаться все чаще и иметь все большую длину.

Награды
За правильное (и наименее зависящее от компьютерного перебора) решение задачи ММ159 Олег Полубасов получает 7 призовых баллов. За верное решение Виктор Филимоненков, Алексей Волошин, Сергей Половинкин и Анатолий Казмерчук получают по 6 призовых баллов.

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

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

[VAL]

Текущее положение участников в XVI туре Математического марафона
\begin{tabular}{|l|l|r|r|r|r|r|r|r|r|r|r|r|r|} \hline №& Участники& 151 & 152 &153 & 154 & 155 & 156 & 157 & 158 & 159 & \Sigma \\ \hline 1.& Олег Полубасов & 5 & 9 & 4 & 5 & 4 & 5 & 6 & 7 & 7 & 52 \\ \hline 2.& Сергей Половинкин & 4 & 7 & 4 & 5 & 4 & 5 & 6 & 8 & 6 & 49 \\ \hline 3.& Виктор Филимоненков & 4 & 6 & 4 & 4 & 4 & 5 & 6 & 7 & 6 & 46 \\ \hline 4.& Анатолий Казмерчук & - & 9 & 2 & 5 & 4 & 5 & 6 & 7 & 6 & 44 \\ \hline 4.& Алексей Волошин & 4 & 4 & 2 & 5 & 4 & 5 & 6 & 8 & 6 & 44 \\ \hline 6.& Николай Дерюгин & 4 & 7 & 4 & - & 4 & 5 & 6 & 6 & - & 36 \\ \hline 7.& Дмитрий Пашуткин & - & - & 4 & 5 & 4 & 5 & 6 & - & - & 24 \\ \hline 8.& Евгений Машеров & - & - & - & 5 & -& 5 & - & - & - & 10 \\ \hline 9.& Евгений Гужавин & 4 & - & - & - & - & 5 & - & - & - & 9 \\ \hline 10.& Александр Князев & 1 & 2 & 3 & 1 & - & - & - & - & - & 7 \\ \hline 11.& nnosipov & - & - & - & - & - & - & 6 & - & - & 6 \\ \hline 12.& Елизавета Евдокимова & - & 2 & - & - & - & - & - & - & - & 2 \\ \hline 13.& Екатерина Шарпанова & - & 1 & - & - & - & - & - & - & - & 1 \\ \hline \end{tabular}

[VAL]

Тем, кто до сих пор по какому-то недоразумению не прислал решений ММ160, предоставляется уникальная возможность исправиться.
Тем, кто прислал решения - тоже есть что исправлять.
В общем, срок приема решений ММ160 продлен.
Следите за объявлениями.

[VAL]

========= 160 ==========

ММ160 (ТГ-5) (10 баллов)

На множестве натуральных чисел от 1 до 10460353203 структура графа $G$ задается так:
вершины $a$ и $b$ смежны тогда и только тогда, когда множества цифр в $g$-ичной записи чисел $a$ и $b$ различны при любом натуральном $g \ge 2$.
Является ли $G$:
a) двудольным;
b) связным;
с) ациклическим?
d) Чему равна степень вершины 3?
e) Есть ли $G$ вершины, степень которых больше чем 10000000000?


Решение

Положим $n = 10460353203=3^{21}$.

Обозначим $U_1=\{2^k-1|k \in \{1,2,\dots,33\}\}, \ U_2=V \backslash U_1$. Очевидно, что числа из $U_1$ и только они записываются в двоичной системе с помощью одних единиц. Поэтому эти 33 вершины попарно не смежны.
Вершины из $U_2$ в двоичной записи имеют нули и единицы. Соответственно и эти вершины попарно не смежны. Таким образом, граф двудольный.

Не сложно найти в $G$ изолированные вершины. Их имеет смысл искать среди чисел из $U_2$, в троичную запись которых входят все троичные цифры. Такая вершина будет заведомо не смежна всем вершинам из $U_2$ и большинству вершин из $U_1$. Дело в том, что в троичную запись большинства вершин из $U_1$ входят все троичные цифры. Исключение составляют вершины 1, 3, 7, 31, 255 и 32767.
Однако вершина 1, очевидно, не смежна никакой вершине, кроме 2.
Для того чтобы искомая вершина $a$ была не смежна 3, достаточно взять число $a$, кратное 3 и большее 12. Тогда запись этого числа в системе счисления c основанием $g = a-3$ будет состоять из двух троек (*).
аналогично можно обеспечить отсутствие смежности вершинам 7, 31, 255 и 32767.
Впрочем, поскольку подходящих вершин много, можно найти одну из них подбором.
Легко проверяется, что наименьшей изолированной вершиной будет 87.

Ясно, что в силу двудольности в графе не может быть цикла, длина которого меньше 4. В то же время цикл длины 4 (в виду огромного числа таких циклов) найти легко. Такими циклами будут, например, $(2,3,4,7)$ или $(31,88,255,70)$;

Подсчитаем число вершин, не смежных 3.
Такими будут все, кратные 3, за исключением 6. В самом деле, в троичной записи множества цифр чисел 3, 9, и 12 совпадают. А начиная с 15, числа кратные 3 не смежны вершине 3 на основании рассуждения аналогичного (*). Таким образом, у нас уже есть $3^{20}-1$ подходящих вершин.
Среди чисел, не кратных 3, отсутствие смежности вершины a вершине 3 может быть обусловлено одной из двух причин:
1) множество цифр в троичной записи a равно $\{0,1\}$;
2) $a \in U_1$.
Легко видеть, что число вершин, удовлетворяющих условию (1) равно $2^{20}-21$. В самом деле, числа, не превосходящие $n$ будем записывать упорядоченный набор из 21-й троичной цифры, возможно, с нулями старших разрядах (набор из одних нулей сопоставим числу $3^{21}$). Тогда в каждой позиции можно поставить либо 0, либо 1. Но в младшем разряде должна быть 1, что обеспечит отсутствие кратности 3. Это дает $2^{20}$. Остается заметить, что ровно 21 из этих чисел записывается с помощью одних единиц.
Вершина $2^i-1$ из $U_1$ кратна 3 тогда и только тогда, когда i четно. Поэтому ровно 17 вершин из $U_1$ не кратны 3. Но одна из них (31) учтена в предыдущем пункте.
Окончательно получаем: $deg(3)=3^{21}-(3^{20}-1)-(2^{20}-21)-16=6972520232$.

Покажем, что степень вершины 31 больше 10000000000. Для упрощения оценки пренебрежем возможными пересечениями множеств вершин не смежных 31.
Не смежными с вершиной 31 будут вершины кратные 31, начиная $31^2+62$. Таких менее чем $\lfloor\frac{3^{21}}{31}\rfloor$.
Для дальнейших оценок заметим, что в системах с основаниями 2, 5 и 30 число 31 записывается одними единицами. Других вершин, имеющих подобную запись в нашем графе соответственно 32, 13 и 4.
В остальных системах с основаниями, меньшими 32, множества цифр в записи числа 31 двухэлементы. Пусть $g$ - одно из таких оснований. Тогда количество чисел, не превосходящих $n$ и записываемых теми же цифрами, что и 31, заведомо не превосходит $2^k$, где $k$ - наименьшее натуральное такое, что $g^k>n$.
Из приведенных соображений получаем оценку

$$deg(31)>\lfloor\frac{30}{31}3^{21}\rfloor-(32+13+4+2^{21}+2^{18}+2^{14}+2\cdot2^{13}+3\cdot2^{12}+2\cdot2^{11}+5\cdot2^{10}+9\cdot2^9+3\cdot2^8+2^7)>10000000000$$

Ответ: Граф $G$:
двудолен;
не связен;
имеет циклы;
степень вершины 3 равна 6972520232;
в $G$ есть вершины степень которых больше 10000000000.

Обсуждение

Вершина 31 не единственная вершина, степень которой превышает 10000000000. Рассуждениями, аналогичными приведенным, можно показать, что еще большую степень имеет вершина 255.
"Третье место" занимает вершина 32767. Но ее степень уже меньше 10000000000 (подвело основание 7).

Ясно, что 87, далеко не единственная изолированная вершина. Таковыми будут, например, 375, 501, 885, 1407, 1527, 1533, 1917, 3573, 3927, 3933, 6015, 6135, 7551, 7677, 8031...
Остальные вершины образуют одну большую компоненту связности диаметра 4.

С подробным обоснованием вышеперечисленных и некоторых других свойств графа G можно познакомиться в решении Олега Полубасова (см. приложение).
Замечу, что по ходу решения Олег "изобрел велосипед". Его теорема 9 - это известная формула для подсчета числа сюръективных отображений (в нашем случае из $m$-элементного множества позиций в $k$-элементное множество цифр).
Внеся первое слагаемое под знак суммы, можно записать ее проще: $L(m,k) = \sum_{i=0}^{k-1}(-1^i)C_k^i(k-i)^m$. Или даже так: $L(m,k)=k!S(m,k)$, где $S(m,k)$ - соответствующее число Стирлинга второго рода.
Впрочем, "велосипед функционирует исправно". И это главное! К тому же, не мне судить Олега. В свое время, я "наступил на те же грабли" - вывел формулу для числа сюръекций и был очень доволен собой, пока не заглянул в книжку.

Число $3^{21}$ в качестве количества вершин было выбрано по следующим соображениям:
1) оно достаточно велико, чтобы избежать исследования графа полным перебором;
2) чтобы легче вычислялась степень вершины 3;
3) чтобы проходила красивая оценка для максимума степеней вершин.
Отмечу, что второе соображение сработало лишь частично. Практически никто из участников (включая автора задачи) не вычислил степень вершины 3 с первого раза. Тем самым, подтвердилось предположение Алексея Волошина, что с первого раза такое не вычисляется

Если уйти от частного случая $n=3^{21}$, появится много новых интересных вопросов:
Будет ли граф иметь изолированные вершины при любых больших $n$?
Если "да", то какова асимптотика их количества по отношению к $n$?
Будет ли вершина 255 оставаться самой высоковалентной при любых больших $n$?
Если нет, то какие вершины ее "победят"?

Замечу, что вершина 87 остается изолированной при $n \le 10^{2000}$. Не исключаю. что так будет и при любых больших $n$. Но боюсь, что доказать эту гипотезу настолько трудно, что проще опровергнуть

Награды

За правильное решение и некоторое обобщение задачи ММ160 Олег Полубасов получает 12 призовых баллов. Алексей Волошин получает 10 призовых баллов, Сергей Половинкин, Виктор Филимоненков и Анатолий Казмерчук - по 9 призовых баллов а Николай Дерюгин - 7 призовых баллов.

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

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

[VAL]

XVI тур Математического марафона завершен.
Поздравляю победителя, Олега Полубасова, призеров, Сергея Половинкина и Виктора Филимоненкова,
и их достойных конкурентов с успешным выступлением!

Итоговое положение участников в XVI туре Математического марафона
\begin{tabular}{|l|l|r|r|r|r|r|r|r|r|r|r|r|r|r|} \hline №& Участники& 151 & 152 &153 & 154 & 155 & 156 & 157 & 158 & 159 & 160 & \Sigma \\ \hline 1.& Олег Полубасов & 5 & 9 & 4 & 5 & 4 & 5 & 6 & 7 & 7 & 12 & 64 \\ \hline 2.& Сергей Половинкин & 4 & 7 & 4 & 5 & 4 & 5 & 6 & 8 & 6 & 9 & 58 \\ \hline 3.& Виктор Филимоненков & 4 & 6 & 4 & 4 & 4 & 5 & 6 & 7 & 6 & 9 & 55 \\ \hline 4.& Алексей Волошин & 4 & 4 & 2 & 5 & 4 & 5 & 6 & 8 & 6 & 10 & 54 \\ \hline 5.& Анатолий Казмерчук & - & 9 & 2 & 5 & 4 & 5 & 6 & 7 & 6 & 9 & 53 \\ \hline 6.& Николай Дерюгин & 4 & 7 & 4 & - & 4 & 5 & 6 & 6 & - & 7 & 43 \\ \hline 7.& Дмитрий Пашуткин & - & - & 4 & 5 & 4 & 5 & 6 & - & - & - & 24 \\ \hline 8.& Евгений Машеров & - & - & - & 5 & -& 5 & - & - & - & - & 10 \\ \hline 9.& Евгений Гужавин & 4 & - & - & - & - & 5 & - & - & - & - & 9 \\ \hline 10.& Александр Князев & 1 & 2 & 3 & 1 & - & - & - & - & - & - & 7 \\ \hline 11.& nnosipov & - & - & - & - & - & - & 6 & - & - & - & 6 \\ \hline 12.& Елизавета Евдокимова & - & 2 & - & - & - & - & - & - & - & - & 2 \\ \hline 13.& Екатерина Шарпанова & - & 1 & - & - & - & - & - & - & - & - & 1 \\ \hline \end{tabular}

Итоговое положение участников в тематическом конкурсе
XVI тура Математического марафона
\begin{tabular}{|l|l|r|r|r|r|r|r|r|r|} \hline №& Участники& ТГ1 & ТГ2 &ТГ3 & ТГ4 & ТГ5 & \Sigma \\ \hline 1.& Олег Полубасов & 5 & 4 & 5 & 7 & 12 & 33 \\ \hline 2.& Сергей Половинкин & 4 & 4 & 5 & 8 & 9 & 30 \\ \hline 3.& Виктор Филимоненков & 4 & 4 & 5 & 7 & 9 & 29 \\ \hline 3.& Алексей Волошин & 4 & 2 & 5 & 8 & 10 & 29 \\ \hline 5.& Николай Дерюгин & 4 & 4 & 5 & 6 & 7 & 26 \\ \hline 6.& Анатолий Казмерчук & - & 2 & 5 & 7 & 9 & 23 \\ \hline 7.& Дмитрий Пашуткин & - & 4 & 5 & - & - & 9 \\ \hline 7.& Евгений Гужавин & 4 & - & 5 & - & - & 9 \\ \hline 9.& Евгений Машеров & - & - & 5 & - & - & 5 \\ \hline 10.& Александр Князев & 1 & 3 & - & - & - & 4 \\ \hline \end{tabular}

[VAL]

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

16-й тур внес коррективы в общий зачет Марафона. На второе место вышел Виктор Филимоненков. В целом же десятка лидеров осталась неизменной.

Положение лидирующей группы после 16-и туров Марафона
\begin{tabular}{|l|l|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|c|} \hline Участники &I-VI&VII&VIII&IX&X&XI&XII&XIII&XIV&XV&XVI&\Sigma\\ \hline 1. А.Казмерчук &-&-&55&67&-&61&74&61&45&54&53&470\\ \hline 2. В.Филимоненков &77&64&60&7&21&32&32&22&-&48&55&418\\ \hline 3. В.Франк &217&59&47&23&33&-&6&-&26&-&-&411\\ \hline 4. А.Волошин &-&-&-&-&45&20&72&61&47&52&54&351\\ \hline 5. О.Полубасов &77&65&45&81&-&-&-&-&-&-&64&332\\ \hline 6. С.Половинкин &-&-&-&-&-&-&80&57&64&56&58&315\\ \hline 7. Н.Дерюгин &-&-&-&18&3&30&49&21&20&19&43&203\\ \hline 8. Д.Пашуткин &-&-&-&-&-&-&41&16&48&43&24&166\\ \hline 9. А.Халявин &-&-&-&-&49&17&6&-&-&43&-&115\\ \hline 10. А.Богданов &45&52&15&-&-&-&-&-&-&-&-&112\\ \hline \end{tabular}

[Mathusic]

Цитата:

ММ166 (3 балла)

Решения принимаются, по крайней мере, до 15.10.12

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

Какой смысл здесь имеет взятие знакочередующейся суммы?

[VAL]

========= 161 ==========

ММ161 (РК-1) (3 балла)

По мотивам задачи ММ132 (и ряда других)

Граф $G=<V,E>$ задан на множестве $V = \{1, 2, ..., 1000000000000\}$ по правилу: $\{a,b\} \in E$ тогда и только тогда, когда сумма чисел $a$ и $b$ равна некоторой четной натуральной степени их разности.
Найти число связных компонент $G$ и диаметр наибольшей компоненты.

Решение

Приведу Дмитрия Пашуткина (см. ссылку)

Обсуждение

Соседние вершины цепочки длиной 1414212 - это, конечно же, последовательные треугольные числа.

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

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


Награды

за правильное решение задачи ММ161 Сергей Половинкин, Олег Полубасов, Евгений Гужавин и Дмитрий Пашуткин получают по 3 призовых балла. Алексей Волошин, Виктор Филимоненков, Николай Дерюгин и Анатолий Казмерчук получают по 2 призовых балла.

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

[VAL]

========= 162 ==========

ММ162 (РК-2) (4 балла)

По мотивам задачи ММ94

Пару различных натуральных чисел a и b назовем похожими, если $\varphi(a)=\varphi(b), \ \sigma(a)=\sigma(b), \ \tau(a)=\tau(b)$, где $\varphi(n), \ \sigma(n)$ и $\tau(n)$, соответственно функция Эйлера, сумма и число натуральных делителей числа $n$ (см. разбор ММ94).
Существуют ли похожие числа a и b такие, что $\tau(a)=\tau(b)=4$?

Решение

Значение функции $\tau(n)$ может равняться 4 в двух случаях: когда $n$ - есть произведение двух различных простых чисел; когда $n$ - куб простого числа.
Ясно, что два различных похожих числа не могут одновременно быть кубами простых чисел.
Пусть $a,b$ - похожие числа и $a=pq, \ b=rs$, где $p,q,r,s$ - различные простые числа. Тогда $\sigma(a)=\sigma(b) \Rightarrow pq+p+q=rs+r+s$ и $\varphi(a)=\varphi(b) \Rightarrow pq-p-q=rs-r-s$. Следовательно, $pq=rs$ и $p+q=r+s$. Т.е. пары чисел $p,q$ и $r,s$ должны быть корнями одного и того же квадратного уравнеия, откуда следует, что $a$ и $b$ совпадают.
Наиболее содержателен случай, когда $a=pq, \ b=r^3$. Имеем: $pq+p+q=r^3+r^2+r$ и $pq-p-q=r^3-r^2-1$. Остюда $4pq=4r^3+2r-2, \ 2(p+q)=2r^2+r+1$, то есть $2p$ и $2q$ должны быть корнями уравнения $x^2-(2r^2+r+1)x+4r^3+2r-2=0$.
Дискриминант этого уравнения $D=4r^4-12r^3+5r^2-6r+9$ должен быть полным квадратом. Но при $r>4$ имеем $(2r^2-3r-2)^2<D<(2r^2-3r-1)^2$ и не может быть полным квадратом. Остается проверить случаи $r=2, \ r=3$. В первом случае уравнение не имеет натуральных корней. Во втором в качестве пары $(p, q)$ получаем пару $(4,7)$. которая, естественно, тоже не подходит, поскольку одно из чисел не простое.

Таким образом, подходящих пар похожих чисел нет.

Обсуждение

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

Награды

За правильное решение задачи ММ162 Алексей Волошин, Виктор Филимоненков, Олег Полубасов, Сергей Половинкин, Евгений Гужавин и Анатолий Казмерчук получают по 4 призовых балла.

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

[VAL]

========= 163 ==========

ММ163 (РК-3) (5 баллов)

По мотивам задачи ММ94 (и ММ162)

Пару похожих чисел a и b назовем s-парой, если $a = spq, \ b=s^3r$, где $p, q, r, s$ - попарно различные простые числа. Проверить истинность каждого из следующих утверждений:
1. Для каждого простого s найдется хотя бы одна s-пара.
2. Для некоторых простых s существует более одной s-пары.
3. Для каждого простого s число s-пар конечно.

Решение

Из условий $\varphi(a)=\varphi(b)$ и $\sigma(a)=\sigma(b)$ получаем

$$\left\{ \begin{array}{lcl} pq-p-q&=&s^2r-s^2-1\\ pq+p+q&=&(s^2+1)r+s^2\end{array}\right.$$

Откуда

$$\left\{ \begin{array}{lcl} 2qp&=&(2s^2+1)r-1\\ 2(p+q)&=&r+2s^2+1\end{array}\right.$$

Обозначим $c=2s^2+1.$ Тогда $r=2(p+q)-c$, а $p=c+\frac{c^2-1}{2(q-c)}.$
Из последнего соотношения сразу следует конечность числа s-пар для фиксированного $s$.
Кроме того, у нас получился эффективный способ нахождения всех s-пар для данного $s$. Достаточно рассмотреть разложения числа $\frac{c^2-1}2$ на два четных множителя и проверить на простоту возникающие $p,q,r$.
Легко убедиться, что при многих значениях $s$ (наименьшее из них 11) не существует ни одной s-пары.
В тоже время, при $s=593$ имеется сразу 2 s-пары $(593\cdot381187517\cdot703949,593^3\cdot763079633)$ и $(593\cdot3911429\cdot780389,593^3\cdot8680337)$.

Таким образом, первое из утверждений ложно, а остальные два истинны.

Обсуждение

При $s=2$ получаем s-пару (638,568). Эта пара (рассмотренная в ММ94) - наименьшая пара похожих чисел.
Я нашел все s-пары, в которых $s$ не превышает миллиона. Их оказалось 1381. Для 34-х значений $s$ нашлось по две s-пары, а для $s=853693$ - целых три s-пары.

Из приведенной статистики видно, что для большинства проверенных простых $s$ s-пар не существует. В тоже время, я полагаю, что существует бесконечно много s-пар. Я, собственно, и затевал рассмотрение s-пар в надежде доказать, что их бесконечно много и, тем самым, доказать бесконечность множества примитивных пар похожих чисел. Но пока вопрос о бесконечности числа примитивных пар остается открытым.

Отмечу, похожие числа - совсем не редкость. При обсуждении задачи ММ94 я писал, что мне не известно ни одной тройки похожих чисел. А затем радовался, найдя пару таких троек.
На самом деле достаточно легко отыскать (или все же сконструировать?) не только тройки, но и четверки, пятерки etc похожих чисел.
В прилагаемом файле приведено 1096 похожих чисел. Мне почему-то кажется, что и это не предел

Награды

За правильное решение задачи ММ163 Алексей Волошин,Олег Полубасов и Анатолий Казмерчук получают по 5 призовых баллов. Виктор Филимоненков и Евгений Гужавин получают по 4 призовых балла, Сергей Половинкин - 3 призовых балла.

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

[VAL]

========= 164 ==========

ММ164 (РК-4) (6 баллов)

По мотивам задачи ММ135

В задаче ММ135 приведено несколько рекуррентных последовательной вида $a_{i+1}=da_i-a_{i-1}$ соседние члены которых дают бесконечные множества пар натуральных чисел $(a,b)$ таких, что остатки от деления $a^2$ на $b$ и $b^2$ на $a$ равны 2011.
Существует ли натуральное число $c<2000000$, для которого найдется не менее 100 последовательностей с попарно различными $d$, соседние члены которых дают бесконечные множества пар натуральных чисел $(a,b)$ таких, что остатки от деления $a^2$ на $b$ и $b^2$ на $a$ равны $c$?

Решение

Пусть $c=ef+1$, где натуральные $e$ и $f$ удовлетворяют условию $e+2<f$. Положим $d=f-e$, $a_0=1, a_1=f, a_{i+1}=da_i-a_{i-1}$.
Легко проверяется, что для членов этой возрастающей последовательности выполняется соотношение $a_i^2-a_{i-1}a_{i+1}=c$. Поэтому, любые два соседних члена, больших $c$, дают подходящую пару.
Остается найти $c<2000000$ такое, что $с-1$ будет иметь достаточно делителей.
Таким будет, например, число $c=665281=2^6\cdot3^3\cdot5\cdot7+1$. Поскольку $\tau(c-1)=224$, для него найдется более 100 подходящих $d$.

Обсуждение

Существует совершенно тривиальное решение задачи ММ164. Достаточно взять $c=r^2$. Тогда при любом $d>2$ последовательность, начинающаяся с $a_0=r, a_1=dr$, будет подходящей.
Поэтому при составлении и решении задач ММ135 и ММ164 я сосредоточился на рассмотрении $c$, не являющихся полными квадратами. И настолько свыкся с этим. что забыл упомянуть в условии, что $c$ не должно быть квадратом. К чести марафонцев все они сумели прочитать мысли ведущего и искали $c$, отличные от квадратов.

Предлагая эту задачу, я видел, что диофантово уравнение $x^2-dxy+y^2=c$ (1), к решению которого сводится отыскание интересующих нас последовательностей, разрешимо не только при $d$, описанных выше.
Конечно, я попытался найти закономерность, которой бы подчинялись все $d$, для которых (1) разрешимо. Но тщетно.
Значительное продвижение в этом направлении (а точнее, обобщение предыдущего рассуждения) сделал Олег Полубасов:

Пусть $c=r^2(ef+1)$, где $e+2<f$. Положим $d=f-e$, $a_0=r, a_1=rf, a_{i+1}=da_i-a_{i-1}$. И мы вновь получили требуемую последовательность.

Но задача оказалась коварной. Существуют разрешимые уравнения вида (1) (а значит, и искомые последовательности), для которых $d$ b $c$ не связаны описанным способом.
Вот пример, найденный Олегом Полубасовым: При $c=170244, d=4862$ уравнение (1) разрешимо, но это $d$ нельзя получить вышеописанным способом.

Приведу еще несколько интересных фактов, найденных (Вы уже, конечно, догадались!) Олегом Полубасовым.

Случаи $c=2$ и $c=3$ единственные (если, конечно, два числа могут единственными) натуральные числа, для которых не существует подходящих последовательностей.
Это, разумеется, не отменяет дополнения к ММ135, найденного Дмитрием Пашуткиным. Существует бесконечно много пар натуральных чисел таких, что остаток от деления квадрата каждого из них на другое число пары равен 3. Ситуация для двойки аналогична. Но эти пары не являются решениями уравнения (1) ни при каких $d$ и рекуррентные соотношения для таких пар более сложны.

Наименьшее $c$, удовлетворяющее условию задачи равно 33049.

Существует аж 51069 натуральных чисел, не превосходящих 2000000 и не являющихся квадратами, для каждого из которых найдется не менее 100 подходящих $d$. Для 161-го из этих чисел требуемое количество $d$ можно получить, основываясь только на разложениях $c-1$.

Наибольшее количество последовательностей (а именно, 303) с попарно различными $d$ порождает число $1995841 = 1 + 2^6\cdot3^4\cdot5\cdot7\cdot11$. Вот список $d$:
3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 16, 17, 18, 21, 22, 23, 24, 25, 26, 28, 30, 34, 37, 38, 40, 42, 43, 44, 46, 47, 54, 57, 58, 61, 67, 68, 74, 77, 78, 79, 82, 86, 93, 94, 99, 102, 103, 106, 112, 141, 142, 145, 152, 154, 163, 166, 179, 180, 192, 194, 195, 200, 226, 244, 248, 249, 251, 252, 258, 262, 268, 306, 324, 332, 344, 348, 362, 366, 382, 383, 388, 394, 397, 418, 443, 453, 492, 493, 504, 545, 548, 572, 573, 574, 579, 583, 626, 646, 662, 666, 670, 724, 768, 824, 834, 838, 871, 889, 934, 972, 982, 1006, 1010, 1023, 1026, 1033, 1043, 1119, 1146, 1150, 1167, 1236, 1248, 1349, 1360, 1388, 1402, 1442, 1446, 1454, 1501, 1536, 1582, 1594, 1654, 1725, 1728, 1802, 1822, 1884, 1888, 1898, 1993, 2006, 2026, 2052, 2131, 2187, 2251, 2298, 2364, 2372, 2432, 2510, 2538, 2598, 2624, 2638, 2737, 2763, 2766, 2889, 2953, 3004, 3148, 3156, 3252, 3456, 3537, 3678, 3858, 3952, 4007, 4096, 4188, 4310, 4318, 4332, 4523, 4644, 4750, 4799, 4902, 5184, 5318, 5584, 5604, 5718, 5836, 5917, 5933, 6021, 6172, 6423, 6634, 6642, 6848, 7122, 7214, 7296, 7660, 7668, 8076, 8314, 8409, 8526, 8686, 8852, 9024, 9294, 9498, 9502, 9882, 10203, 10371, 10502, 10908, 11164, 11669, 11712, 11877, 11931, 12158, 12314, 12784, 12806, 13716, 14116, 14649, 14988, 15118, 15714, 16512, 16627, 17708, 18034, 18142, 18372, 18903, 19952, 20061, 20694, 21688, 22086, 22174, 22592, 23676, 24559, 24868, 25843, 27648, 27718, 28442, 30174, 31121, 31617, 33204, 33260, 35584, 35638, 36233, 36906, 38378, 41532, 44307, 45316, 47478, 47518, 49856, 55404, 56989, 60447, 62338, 66498, 66526, 71252, 73893, 83136, 83157, 90698, 95019, 99772, 99790, 110862, 124724, 133041, 142546, 166308, 166318, 181429, 199574, 221751, 249472, 285113, 332634, 332638, 399163, 498956, 665277, 997918, 1995839.

Число $c = 2011$, рассмотренное в задаче ММ135, порождает 23 последовательности с попарно различными $d$. Список $d$:
3, 5, 7, 9, 11, 13, 17, 23, 37, 43, 47, 57, 65, 93, 107, 119, 191, 329, 333, 397, 667, 1003, 2009.

Награды

За правильное решение и содержательное обобщение задачи ММ164 Олег Полубасов получает 9 призовых баллов.
за правильное решение задачи Алексей Волошин, Виктор Филимоненков, Анатолий Казмерчук и Сергей Половинкин получают по 6 призовых баллов.

Эстетическая оценка - 4.9 балла

[Masik]

Хиленькое какое-то обсуждение. Может, кому-то и интересно рассмотрение частных фактов, вроде списков d для конкретных значений c, но лично мне было бы гораздо приятнее увидеть обсуждение более общих теоретических вопросов.
Во-первых, при $c = r^2$ допустимые d не больше 2, а больше или равны. Да и убывающие последовательности никто не отменял.
Во-вторых, уравнение $x^2 - dxy + y^2 = c$ имеет бесконечное множество решений в целых числах и поэтому практически бесполезно.
Чтобы ограничить количество решений, нужно рассмотреть последовательности, бесконечные в обе стороны, и выбрать последовательные члены x и y разных знаков. Тогда -dxy будет положительным, а значит (для возрастающих последовательностей) при $x \leqslant -1, y \geqslant 1, d \geqslant 3$:
$ -\sqrt{c-4} \leqslant x \leqslant -1, $
$1 \leqslant y \leqslant \sqrt{c - x^2 - 3|x|} \leqslant \sqrt{c-4},$
$3 \leqslant d = (c - x^2 - y^2)/|xy| \leqslant c-4$.
Подходящую пару будут давать любые два соседних члена, большие c.
В-третьих, назначать параметрами уравнения (1) c и d не выгодно, гораздо удобнее назначить параметрами c и x, где $ -\sqrt{c-4} \leqslant x \leqslant -1$. Тогда уравнение (1) запишется в виде: $y(y + d|x|) = c - x^2$. Раскладывая $c - x^2$ на два множителя: y и $(y + d|x|)$, получаем все решения без повторений.
В-четвёртых, при $y = 0$ все подходящие последовательности имеют три общих последовательных члена: $-\sqrt c, 0$ и $\sqrt c$, что, на первый взгляд, кажется невозможным.
В-пятых, интересен случай $d = 2$.

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

[VAL]

Masik в сообщении #627629 писал(а):

Хиленькое какое-то обсуждение.

Ветка называется "Обсуждение и разбор марафонских задач". То, что публикую я - это разбор. А каким будет обсуждение зависит не только от меня. Я же всегда приветствую конструктивную критику (ту, которую не приветствую не конструктивна по определению ).

Цитата:

Может, кому-то и интересно рассмотрение частных фактов, вроде списков d для конкретных значений c, но лично мне было бы гораздо приятнее увидеть обсуждение более общих теоретических вопросов.

Ok! Сейчас подкину. И ответы, и вопросы.

Цитата:

Во-первых, при $c = r^2$ допустимые d не больше 2, а больше или равны.

Я квадраты не рассматривал. И уже покаялся, что замял этот момент в условии.

Цитата:

Во-вторых, уравнение $x^2 - dxy + y^2 = c$ имеет бесконечное множество решений в целых числах и поэтому практически бесполезно.

Иногда имеет. А иногда нет. И потому полезно. Что, разумеется, не отрицает полезности иных подходов.

Цитата:

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

Нет проблем.
Основные тезисы уже изложены. Подробности в прилагаемом файле.

Цитата:

И наоборот, хотелось бы почитать решения других участников, пусть даже и неправильные.

А здесь, на мой взгляд, проблемы есть. Этические.

Цитата:

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

Выкладывать все решения заведомо не имеет смысла. Очень многие похожи друг на друга больше, чем числа 638 и 568

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

Хотелось бы услышать мнения марафонцев по этому вопросу.

ЗЫ: Маленький технический вопрос. Раньше у меня не было возможности прикручивать файлы, а сейчас есть. Она есть у всех или только у более равных форумчан?

-- 06 окт 2012, 20:20 --

Взглянем на вопросы, обсуждаемые в ММ135 и ММ164 немного под другим углом.

Будем называть натуральные числа $a$ и $b$ квадратично сопряженными, если остатки от деления $a^2$ на $b$ и $b^2$ на $a$ равны.

Для каждого натурального числа $a$ существует лишь конечное количество квадратично сопряженных чисел (самое большое из них $a^2$).
Понятно, что квадратично сопряженными являются все близкие натуральные числа. А именно, натуральное число а квадратично сопряжено c помощью $s^2$ со всеми натуральными числами вида $a - s$, где $s$ - целое неотрицательное число и $s^2 + s < a$, и со всеми числами вида $a + t$, где $t^2 < a$.
Понятно, также, что натуральное число $a$ квадратично сопряжено с помощью 0 со всеми натуральными числами, в каноническое разложение которых входят те же самые множители, что и в каноническое разложение $a$, а показатели степени при одинаковых простых сомножителях отличаются не более чем в два раза.
Наконец, $a$ всегда квадратично сопряжено с помощью единицы с числом $a^2 - 1$.
Все перечисленные случаи квадратичного сопряжения назовем тривиальными. Очевидно, что общий остаток в тривиальных случаях всегда является квадратом.

Существуют натуральные числа, для которых нет нетривиальных квадратично сопряженных с ними чисел. Например, таковыми являются число 1, простые числа: $2, 3, 5, 7, 13, 17, 31, 67, 73, 313, 353, 421, 541, 821, 947, 1033, 1123, 1321, 1453, 2371, 2381, 2707, 2887, 3041, 3319, 3461, 3727, 3767, 4021, 4201, 5521, 6701, 6947, 7757, 8011, 8087, 8971, 9811$; а так же числа $2^2, 3^2, 5^2, 19^2, 59^2, 197^2, 641^2$. Однако чаще встречаются числа, для которых имеются нетривиальные квадратично сопряженные. Так, среди первых десяти тысяч натуральных чисел не имеют нетривиальных квадратично сопряженных только числа, указанные выше (то, что последние два больше 10000 сути дела не меняет).
Закономерность проследить не удалось. А хотелось бы!

Вот и обещанный вопрос (и готовая последовательность для OEIS).

[Masik]

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

Цитата:

И наоборот, хотелось бы почитать решения других участников, пусть даже и неправильные.

А здесь, на мой взгляд, проблемы есть. Этические.

Согласен, есть этические проблемы. Присланные решения должны быть проверяемыми. Иначе профессор не отмоется от подозрений, действительно ли студентка сдала ему зачёт, или оказала услуги иного рода.

Цитата:

Цитата:

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

Выкладывать все решения заведомо не имеет смысла. Очень многие похожи друг на друга больше, чем числа 638 и 568

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

Цитата:

ЗЫ: Маленький технический вопрос. Раньше у меня не было возможности прикручивать файлы, а сейчас есть. Она есть у всех или только у более равных форумчан?

У себя я такой кнопки не вижу. Это не значит, что её нет, может быть, есть, но я не знаю, где.

Цитата:

-- 06 окт 2012, 20:20 --
Существуют натуральные числа, для которых нет нетривиальных квадратично сопряженных с ними чисел. Например, таковыми являются число 1, простые числа: $2, 3, 5, 7, 13, 17, 31, 67, 73, 313, 353, 421, 541, 821, 947, 1033, 1123, 1321, 1453, 2371, 2381, 2707, 2887, 3041, 3319, 3461, 3727, 3767, 4021, 4201, 5521, 6701, 6947, 7757, 8011, 8087, 8971, 9811$; а так же числа $2^2, 3^2, 5^2, 19^2, 59^2, 197^2, 641^2$. Однако чаще встречаются числа, для которых имеются нетривиальные квадратично сопряженные. Так, среди первых десяти тысяч натуральных чисел не имеют нетривиальных квадратично сопряженных только числа, указанные выше (то, что последние два больше 10000 сути дела не меняет).
Закономерность проследить не удалось. А хотелось бы!
Вот и обещанный вопрос (и готовая последовательность для OEIS).

Не знаю. Это уже другая задача. Может быть, ММ174?