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

[VAL]

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

[VAL]

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

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

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

ММ98 (7 баллов)

Васю Пупкина заслали в тыл врага с целью выявить секретный код, ввод которого предотвратит термоядерный взрыв. Вася незамеченным проник в святая святых и сфотографировал секретный код на мобильник. Но, пробираясь к своим, Вася потерял мобильник и теперь пытается вспомнить код.
- Помню только, что код состоял из трех чисел, расположенных строго в порядке
возрастания - удрученно докладывает Вася руководству.
- А какие числа: двузначные, трехзначные,..?
- Не помню...
- Вася, но ведь ты по образованию математик! Вспомни, может быть, среди чисел были какие-нибудь особенные: квадраты, кубы,..
- Нет, таких не было, но я припоминаю, что сложив сумму квадратов цифр одного из этих чисел с суммой кубов цифр другого я получил сумму этих двух чисел.
- Это уже кое-что! Но код можно вводить только один раз. В случае неверного кода взрыв неминуем. Вспоминай дальше.
- Вспомнил! Эти числа могли служить количествами вершин, граней и, соответственно, ребер некоторого выпуклого многогранника. Я даже мысленно представил себе подходящий многогранник.
- Хорошо. Дальше.
- Так... Каждое из чисел представлялось в виде суммы двух натуральных квадратов. Что еще? Ах, да! По крайней мере два из них были простыми... А еще У двух чисел были одинаковые значения функции Эйлера...
Все! Больше ничего не помню.

1. Помогите Васе спасти человечество.
2. Какие из пришедших на память Васе соотношений избыточны?


Решение

Приведу немного подкорректированное решение Эдварда Туркевича.

1. Ответ: 401, 409, 808
Простой анализ соотношения с цифрами показывает, что числа состоят не более чем из 4 цифр. Заложив в программку все соотношения, получим единственную тройку (401, 409, 808).

2. Ищем излишние условия:
Убирая в программке по одному соотношению, получаем:
а) условие "строго в порядке возрастания" необходимо - (41, 41, 80);
б) условие "не квадраты" необходимо - (41, 61, 100);
в) условие "не кубы" излишнее;
г) условие "условия с цифрами" необходимо - (97, 113, 208);
д) условие "многогранник" необходимо - (41, 61, 82);
е) условие "представление в виде суммы двух натуральных квадратов" излишнее;
ж) условие "по крайней мере два простые" излишнее;
з) условие "у двух чисел одинаковые значения функции Эйлера" необходимо - (50, 53, 101).

Условие "не кубы" излишнее вовсе, а одно из условий "представление в виде суммы двух натуральных квадратов" и "по крайней мере два простые" необходимо - (13, 21, 32)

Все указанные тройки удовлетворяют условию "многогранник". Например, тройку (401, 409, 808) можно получить, поместив на боковые грани 392-угольной пирамиды 8 низеньких (чтобы выпуклость сохранилась) тетраэдров.

Обсуждение

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

Ориентируясь на условие д), обозначим исходные числа через В, Г и Р соответсвенно.

Из г) следует, что числа не более чем четырехзначны. Поэтому сумма квадратов цифр одного из них, сложенная с суммой кубов цифр другого, не превышает $4*9^3 + 3*9^2 + 8^2 = 3223$. Но тогда сумма чисел не превышает 3223. А для чисел, не превышающих 3223, сумма квадратов цифр одного из них, сложенная с суммой кубов цифр другого, не превышает
$2^3 + 3*9^3 + 1+3*9^2 = 2439$. Учитывая, что не только каждое слагаемое, но и сумма не должны теперь превышать 2439, можно показать, что В не превосходит 999, а Г - 1299.

Из условий ж) и з) можно заключить, что В простое, а среди Г и Р ровно одно составное. В противном случае, значения функции Эйлера всех трех чисел будут различны.

Условие е) позволяет перебирать в качестве потенциальных В только простые вида 4k+1...

Выясним теперь связь между В, Г и Р, вытекающую из д). Наиболее очевидное соотношение Р = В + Г -2, вытекающее из теоремы Эйлера, заметили все участники Марафона. Но часть из них ограничились лишь этим соотношением. На самом деле оно не является достаточным.
Каждая грань многогранника ограничена не менее, чем тремя ребрами. При этом каждое ребро учитывается дважды. Поэтому 3Г $\le$ 2Р = 2(В + Г - 2). Откуда Г $\le$ 2В - 4. (Этого соотношения тоже не достаточно для существования многогранника, но достаточно для решения задачи.)

Игнорирование последнего соотношения частью марафонцев позволили им рассмотреть, "многогранники", например, с 43-я вершинами, 98-ю гранями и 139-ю ребрами, что в свою очередь привело их к выводу о необходимости условия е).
Аналогично "многогранник" с 317-ю вершинами, 634-я гранями и 949-ю ребрами "доказывает" необходимость условия ж).

Многие конкурсанты рассматривали условия б) и в) как одно. Я считал такой подход правильным (как и подход тех, кто эти условия разделил)

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

Алексей Волошин заинтересовался достаточными условиями существования многогранников с заданными количествами вершин, граней и ребер.
Добавим, к двум уже имеющимся соотношениям (B+Г-З = 2 и 2Р $\ge$ 3Г) еще одно.
Поскольку из каждой вершины выходит не менее трех ребер и при этом каждое ребро учитывается дважды, 2P $\ge$ 3В.
Оказывается трех этих ограничений вполне достаточно.
Во-первых, легко убедиться, что наименьшая тройка, для которой проходят все три cоотношения: В = Г = 4, Р = 6.
Пусть теперь натуральные числа В, Г, Р удовлетворяют всем трем соотношениям.
Если В = Г, то искомым многогранником будет В-1-угольная пирамида.
Пусть Г больше В и Г-В = k. Тогда возьмем В-1-k-угольную пирамиду (такая пирамида существует, поскольку из наших условий следует Г $\le$ 2В - 4, откуда В-1-k не меньше 3). На k треугольных гранях этой пирамиды как на основаниях построим маленькие треугольные пирамидки (если граней исходной пирамиды не хватит, то воспользуемся гранями уже построенных пирамидок). Ясно, что полученный многогранник будет иметь требуемые характеристики.
Если же В больше Г, то мы наоборот будем отрезать уголки от основонаия В-1-k-угольной пирамиды (или вновь возникшие трехгранные уголки) так, чтобы на каждом шаге наращивать число граней на одну, вершин на две, а ребер на три.

Награды

За решение задачи 98 Алексей Волошин и Влад Франк получают по 7 баллов, Эдвард Туркевич - 6 баллов, Алексей Извалов - 5 баллов, Андрей Халявин и Виктор Михайлов - по 4 балла, Николай Дерюгин и Усимов - по 3 балла.

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

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

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

[VAL]

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

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

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

ММ99 (З-5) (8 баллов)

Продолжить последовательность 0,0,1,0,3,4,6,0,1,8,6,4,6,6,13,8...

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

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


Решение

Это остатки от деления числа 2008 на последовательные натуральные числа.
Следующее число - 2008 mod 17 = 2.


Обсуждение

Планируя конкурс, я заранее придумал 5 последовательностей и расположил их, как мне казалось, в порядке возрастания трудности обнаружения принципа построения. Однако уже первая закономерность (задача №91) была выявлена не всеми участниками конкурса, а вторая (задача №93) и вовсе не поддалась конкурсантам. "Обжегшись на молоке", я заменил последовательность в задаче №97, а последнюю задачку конкурса закономерностей снабдил подсказкой. Предпринятые пожарные меры сработали - остальные закономерности были
учпешно разгаданы.

Награды

За правильное решение задачи №99 Алексей Волошин, Владимир Боровских, Андрей Халявин и Алексей Извалов получают по 5 призовых баллов.

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

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

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

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

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

Мои позздравления лауреатам конкурса: Андрею Халявину, Алексею Волошину и Алексею Извалову!

[General]

Ура!

Вам, Владимир, огромное спасибо за организацию и интересные задачи!

А, да, в реале Алексей Извалов - это я

О, я так понимаю, будет ещё одна задача, но не на поиск закономерности?

[VAL]

General писал(а):

Вам, Владимир, огромное спасибо за организацию и интересные задачи!

Рад стараться!

Цитата:

А, да, в реале Алексей Извалов - это я

Я (а теперь и не только я) в курсе

Цитата:

О, я так понимаю, будет ещё одна задача, но не на поиск закономерности?

Блестящая догадка!

[General]

VAL писал(а):

General писал(а):

Цитата:

А, да, в реале Алексей Извалов - это я

Я (а теперь и не только я) в курсе

Ну да, я вот подумал, может кто ещё из марафонцев немного девиртуализируется теперь

[VAL]

Срок приема решений марафонской задачи № 100 продлен до 23.12.08.
Уважаемые участники (включая потенциальных) поторапливайтесь, а то и к этому сроку не поспеете.

В новый год с новым туром!

[VAL]

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

=============
Юбилейная задача представляет собой по сути целый букет задач, связанных общей тематикой и общими идеями. Часть подзадач - известные (но, с учетом их красоты, на мой взгляд, недостаточно известные) утверждения. Другие - новые (хотелось бы надеяться не только для меня).


ММ100 (17 баллов)

Пусть $S_n$ множество всех перестановок множества $M_n = \{1,2,3,\dots,n\}$

1. Найти и обосновать рекуррентное выражение количества перестановок $g$ из $S_n$ таких, что для всех $k$ из $M_n$ $g(k)$ может отличаться от $k$:
a) не более, чем на $1$;
b) не более, чем на $2$.

2. Рассмотрим произвольный элемент из $S_n$ и произвольное $a$ из $M_n$.
Найти вероятность того, что $a$ входит в цикл длины $k$.

3. Для произвольного элемента $g$ из $S_n$ найти:
a) математическое ожидание количества циклов длины $k$;
b) математическое ожидание количества циклов;
c) моду циклового вида (учитываются количество и длина циклов);
d) полагая $k > n/5$, найти вероятность того, что в $g$ будет хотя бы один цикл
длины $k$.

4. Вспомним, что $S_n$ является группой относительно композиции перестановок.
Обозначим $s(n,k) = | \{g^k | g \in S_n\} |, q(n,k) = s(n,k)/n!$:
a) найти $20$ наименьших значений $s(n,k)$;
b) возможно ли равенство $q(n,k) = 1/2$ для нечетных $k$.

Решение

1.a.

Этот пункт совсем легкий.
Перестановки, удовлетворяющие условию пункта 1.a будем называть подходящими.
Обозначим искомое количество подходящих перестановок через $F(n)$.
Ясно, что $F(1) = 1$ и $F(2) = 2$.
Требуемые перестановки, очевидно, представляют собой произведение транзпозиций соседних элементов и "циклов" длины 1. Т. е. их можно получить, приписывая транспозицию $(n-1\quad n)$ к $F(n-2)$ подходящим перестановкам множества $M_{n-2}$ и петли $(n)$ к $F(n-1)$ подходящим перестановкам множества $M_{n-1}$.
Поэтому $F(n) = F(n-1) + F(n-2)$, и мы получаем ряд Фибоначчи.

1.b.

Здесь ситуация похитрее.
Теперь подходящими будем называть перестановки, удовлетворяющие условию пункта
1.b. Обозначим искомое количество подходящих перестановок через $G(n)$. Первые значения $G$: $G(1) = 1, G(2) = 2, G(3) = 6, G(4) = 14$. Учитывая, что $0! = 1$, положим $G(0) = 1$.
Пусть теперь $n$ не меньше $5$.
i) Из каждой подходящей перестановки множества $M_{n-1}$ можно получить подходящую перестановку множества $M_n$, добавив петлю $(n)$.

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

ii) Заметим, что, если в цикловую запись подходящей перестановки на множестве $M_{n-1}$ входит цикл, содержащий $(n-1)$, длина которого больше двух, то в такой цикл можно добавить элемент $n$ единственным способом.

iii) Если цикловая запись перестановки заканчивается петлей $(n-1)$, перед которой идет цикл, содержащий более одного элемента, то такую перестановку также можно продолжить до подходящей, не добавляя новых циклов, единственным способом, заменив петлю $(n-1)$ на транспозицию $(n-1\quad n)$.

iv) Если цикловая запись перестановки заканчивается двумя петлями $(n-2)(n-1)$, то в каждую из них можно добавить $n$.

v) Если цикловая запись перестановки заканчивается транспозицией $(n-2\quad n-1)$, то оба возможных способа добавления элемента $n$ в эту транспозицию ведут к получению подходящих перестановок множества $M_n$.

vi) Если цикловая запись подходящей перестановки заканчивается выражением $(n-3\quad n-1)(n-2)$, то элемент $n$ нельзя "впихнуть" в транспозицию $(n-3\quad n-1)$, но можно добавить в одноэлементный цикл $(n-1)$.

vii) Наконец, если цикловая запись подходящей перестановки заканчивается выражением $(n-4\quad n-4)(n-3\quad n-1)$, то добавить элемент n в уже имеющиеся циклы невозможно.

Поэтому $G(n) = 2G(n-1) + 2G(n-3) - G(n-5)$.

(Большинстово подходящих перестановок можно продолжить не менее чем двумя способами. Второе слагаемое учитывает дополнительные подходящие перестановки, возникающие в случаях iv и v, а последнее слагаемое обусловлено случаем vii.)

2.

Ответ к этому пункту: $1/n$ для всек $k \le n$ и $0$ при $k > n$.

В самом деле, произвольный элемент $a$ множества $M_n$ при произвольной перестановке с вероятностью $1/n$ переходит в себя и образует цикл длины $1$. Вероятность его вхождения в цикл длины $2$ равна произведению $(n-1)/n$ (вероятности того, что $a$ не перешел в себя) на $1/(n-1)$ (верояности того, что образ $a$ перешел в $a$). Итого, вновь имеем верояность $1/n$.
И т.д.

3.a.

Запишем все $n!$ перестановок в цикловом виде (не опуская одноэлементных циклов). В этой записи будет участвовать ровно $n*n!$ элементов, разбитых на циклы длин $1, 2, ... n$. Из пункта 2 следует что для каждого $k$ из ${1,2,...,n}$ в этой записи будет ровно $n!$ элементов, входящих в циклы длины $k$ и, значит, $n!/k$ циклов длины $k$.
(Например, для $n = 3$ имеем: $(1)(2)(3),(12)(3),(13)(2),(1)(23),(123),(132)$.)
Но тогда искомое математическое ожидание равно $(n!/k)/n! = 1/k$.

3.b.

Для получения ответа к этому пункту достаточно просто просуммировать математические ожидания числа циклов длины $k$ по всем возможным $k$. Таким образом, математическое ожидание количества циклов в произвольной перестановке n-элементного множества равно $1 + 1/2 +\dots+ 1/n$, т.е. $n$-му гармоническому числу.

3.c.

При $n = 1$ в единственной перестановке множества $M_n$ есть единственный цикл длины $1$. При $n = 2$ возможные цикловые виды $[1]-[1]$ и $[2]$ встречаются одинаково часто (по одному разу).
Пусть $n > 2$.
Из предыдущих пунктов следует, что ровно $(n-1)!$ перестановок представляют собой цикл длины $n$. Аналогично, цикловой вид $[n-1]-[1]$ имеют $n!/(n-1)$ перестановок. Т.е. их больше, чем длинных циклов. Покажем, что $[n-1]-[1]$ и есть мода циклового вида.
В самом деле, легко видеть, что престановок циклового вида $[n-1]-[1]$ больше, чем престановок циклового вида $[n-k]-[k]$ при $k$ и $n-k$, бОльших $1$.
Пусть теперь $n = a + b + c$, где $a \ge b \ge c$. Тривиально показывается, что перестановок вида $[a+b]-[c]$ больше чем перестановок вида $[a]-[ b ]-[c]$.
И т.д.

3.d.

i. Со случаем $n/2 < k \le n$ мы разобрались в предыдущих пунктах. Искомая вероятность равна $1/k$.

ii. При $n/3 < k \le n/2$, разобрав случаи одного и двух циклов, получим искомую вероятность $\frac{2k-1}{2k^2}$.

iii. Для остальных случаев удобно воспользоваться формулой включения и исключения. При $n/4 < k \le n/3$ имеем $\frac{6k^2-3k+1}{6k^3}$.

iv. При $n/5 < k \le n/4$ имеем $\frac{24k^3-12k^2+4k-1}{24k^4}$.

4.a.

При возведении в степень $k$ цикл длины $m$ распадается на $(k,m)$ циклов длины $m/(k,m)$. Учитывая это соображение и количество подстановок каждого циклового вида в группах $S_n$ при малых $n$ можно получить следующие $20$ значений $s(n,k)$ (если значение получается при разных наборах значений $n$ и $k$, указан один из таких наборов):

$1$ (при $n = 1, k = 1$)
$2$ (при $2 = 1, k = 1$)
$3$ (при $n = 3, k = 2$)
$4$ (при $n = 3, k = 3$)
$6$ (при $n = 3, k = 1$)
$9$ (при $n = 4, k = 9$)
$12$ (при $n = 4, k = 2$)
$16$ (при $n = 4, k = 3$)
$21$ (при $n = 5, k = 30$)
$24$ (при $n = 4, k = 1$)
$25$ (при $n = 5, k = 12$)
$36$ (при $n = 5, k = 10$)
$40$ (при $n = 5, k = 6$)
$45$ (при $n = 5, k = 4$)
$46$ (при $n = 6, k = 30$)
$56$ (при $n = 5, k = 15$)
$60$ (при $n = 5, k = 2$)
$80$ (при $n = 5, k = 3$)
$81$ (при $n = 6, k = 20$)
$96$ (при $n = 5, k = 5$)

Обоснование того, что приведены наименьшие возможные значения можно посмотреть на http://www-old.fizmat.vspu.ru/doku.php? ... thon:about
4.b.

Покажем, что $q(9,3) = 1/2$.
Для этого заметим, что в $s(9,3)$, в отличие от $S_9$, нет перестановок с циклами, длины которых кратны $3$, за исключением перестановок вида $[3]-[3]-[3]$.
В $S_9$ Имеется:
девятиэлементных циклов - $8!$;
перестановок, содержащих шестиэлементный цикл, - $9!/6$;
перестановок с ровно двумя трехэлементными циклами, - $C_9^3 C_6^3 2^2|s(3,3)|/2$;
перестановок с ровно одним трехэлементным циклом, - $C_9^3 2|s(6,3)|$.
Учитывая, что $|s(6,3)| = 400, |s(3,3)| = 4$, и суммируя, получим $181440 = 9!/2$.


Обсуждение

Любопытно, что большинство участников Марафона, получив рекуррентное соотношение для $F(n)$, никоим образом не отреагировали, что это числа Фибоначчи.

Последовательность $G(n)$ (как, разумеется, и $F(n)$) есть онлайновой энциклопедии целочисленных последовательностей. Её номер A002524.

Применяя метод включения и исключения, можно получить общую формулу, выражающую вероятность наличия цикла длины $k$ в $S_n$ - $\sum_{i=1}^{[n/k]} \frac{(-1)^{i+1}}{k^i i!}$.

Любопытно, 21-е по величине значение $|s(n,k)|$ получается при $n = 8$ Это $|s(8,420)| = 106$ ($|s(7,210)|$ тоже равно $106$).

С пунктом 4.b. не справился ни один участник. Это оказалось для меня неожиданным. Ведь подходящий пример возникает при совсем не запредельных $n$ и $k$.
Кстати, $q(10,3)$ и $q(11,3)$ тоже равны по $1/2$.
Справедливо и более общее утверждение: $q(n,k) \le q(n+1,k)$, причем это неравенство трансформируется в равенство всякий раз, когда $(k,n+1) = 1$.

Вызывает интерес доказательство (или опровержение) следующей гипотезы:
$ \forall k \in {\bf N} \forall e>0 \exists n \in {\bf N}( q(n,k) < e)$.


Награды

За правильное решение большинства пунктов задачи 100 участники получают:
Владислав Франк - 15 баллов;
Алексей Волошин - 14 баллов;
Андрей Халявин и Алексей Извалов по 12 баллов.


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

[VAL]

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

Завершился 10-й, юбилейный тур Математического марафона

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

Мои поздравления подебителям десятого тура (и, кстати, дебютантам Марафона) Андрею Халявину, Алексею Извалову и Алексею Волошину!

[VAL]

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

Положение лидирующей группы после 10-и туров
\begin{tabular}{|l|l|r|r|r|r|r|r|r|r|r|r|c|} \hline № & Участники & I & II & III & IV & V & VI & VII & VIII & IX & X & \Sigma\\ \hline 1. & Владислав Франк & - & - & 32 & 53 & 47 & 85 & 59 & 47 & 23 & 33 & 379\\ \hline 2. & Олег Полубасов & - & - & - & - & 77 & - & 65 & 45 & 81 & - & 268\\ \hline 3. & Виктор филимоненков & - & - & - & - & - & 77 & 64 & 60 & 7 & 21 & 229\\ \hline 4. & Анатолий Казмерчук & - & - & - & - & - & - & - & 55 & 67 & - & 122\\ \hline 5. & Андрей Богданов & - & - & - & - & 45 & - & 52 & 15 & - & - & 112\\ \hline 6. & Иван Козначеев & - & - & - & 53 & 2 & 13 & 8 & 9 & 3 & - & 88\\ \hline 7. & Борис Бух & 38 & 28 & 15 & - & - & - & - & - & - & - & 81\\ \hline 8. & Макс Алексеев & 8 & 6 & 28 & 12 & 26 & - & - & - & - & - & 80\\ \hline 9. & Константин Кноп & - & - & - & - & 14 & - & 16 & 45 & - & - & 75\\ \hline 10. & Андрей Винокуров & - & - & - & - & 73 & - & - & - & - & - & 73\\ \hline 10. & Дмитрий Милосердов & - & - & - & - & 18 & 4 & 28 & 23 & - & - & 73\\ \hline 12. & Мигель Митрофанов & - & - & - & - & 48 & 3 & - & - & - & - & 51\\ \hline 13. & Андрей Халявин & - & - & - & - & - & - & - & - & - & 49 & 49\\ \hline 14. & Алексей Извалов & - & - & - & - & - & - & - & - & - & 46 & 46\\ \hline 15. & Евгений Машеров & - & - & - & - & - & - & 17 & 15 & 8 & 5 & 45\\ \hline 15. & Алексей Волошин & - & - & - & - & - & - & - & - & - & 45 & 45\\ \hline 17. & Андрей Бежан & - & 6 & 26 & - & 5 & - & 5 & - & - & - & 42\\ \hline 18. & Сергей Аракчеев & - & - & - & - & - & - & 35 & 4 & - & - & 39\\ \hline 19. & Сергей Беляев & - & - & - & - & - & - & 24 & 14 & - & 49 & 38\\ \hline 20. & Вячеслав Пономарев & 20 & 11 & - & 3 & - & - & - & - & - & - & 34\\ \hline 21. & Павел Егоров & 20 & - & 13 & - & - & - & - & - & - & - & 33\\ \hline 21. & Владимир Трушков & - & 12 & 18 & - & 3 & - & - & - & - & - & 33\\ \hline 21. & Стас Грицюк & - & - & - & - & - & - & 27 & 6 & - & - & 33\\ \hline 24. & Маша Никулина & 5 & 7 & - & 4 & 8 & - & - & - & - & - & 24\\ \hline 24. & Алексей Кутузов & - & - & - & - & - & - & 24 & - & - & - & 24\\ \hline 24. & Галина Крюкова & - & - & - & - & - & - & - & 13 & 11 & - & 24\\ \hline 27. & Николай Дерюгин & - & - & - & - & - & - & - & - & 18 & 3 & 21\\ \hline 28. & Татьяна Шемелова & - & - & - & - & - & - & 15 & - & 4 & - & 19\\ \hline 29. & Иван Держанский & - & - & - & - & - & - & 16 & - & - & - & 16\\ \hline 30. & Олег Чечулин & - & - & - & - & - & - & 15 & - & - & - & 15\\ \hline \end{tabular}

[VAL]

Попробую успеть еще в этом году добавить несколько мазков к картине под названием "100 задач Математического марафона"

Среди бегунов на длинные дистанции "засветились" 60 человек (не считая тех, кто не получил ни одного балла и не попал в мою сводную таблицу).
Если внимательно изучить приведенную выше тридцатку лучших марафонцев можно заметить немало известных (в том числе и на этом форуме) людей.

Пик (хотелось бы верить, что локальный) популярности пришелся на 7-й тур Марафона, в котором приняли участие 24 человека. А самый малолюдный тур предшествовал самому бурному: в 6-м туре отметились решениями всего 6 человек.

Но именно на шестой тур приходится рекорд по количеству призовых баллов, заработанных одним участником за один тур: Владу Франку покорилась вершина в 85 баллов!
Укажу имена и результаты победителей в каждом из туров:

I. Борис Бух - 38 баллов.
II. Борис Бух - 28 баллов.
III. Влад Франк - 32 балла.
IX. Влад Франк и Иван Козначеев - по 53 балла.
V. Олег Полубасов - 77 баллов.
VI. Влад Франк - 85 баллов
VII. Олег Полубасов - 65 баллов
VIII. Виктор Филимоненков - 60 баллов.
IX. Олег Полубасов - 81 балл.
X. Андрей Халявин - 49 баллов.

Самой популярной задачей стала задача №61 (на восстановление турнирной таблицы), на которую откликнулись 18 человек. На втором месте задача №65 (она опубликована в первом номере "Кванта" за истекающий год) - 15 откликов.
На две задачи (№2 и №93) так и не было получено ни одного отклика, оцененного призовыми баллами.

Интересно, что полулярность задачи не особенно связана с той эстетической оценкой (в практику Марафона такие оценки введены в середине 5-го тура), которую дают ей сами участники Марафона. Если тут и есть какая-то корреляция, то, скорее, отрицательная.
Максимальные эстетические оценки в 5 баллов получили задчи №№ 65, 70, 83, 84, 88 и 100.
Менее всего участникам Марафона понравились задачи №51 (2 балла) и 71 (2.4 балла).

Больше всего баллов, аж 119, принесла марафонцам задача №56.
Больше всего баллов за одну задачу - 20 получили пять человек. Но лишь Олегу Полубасову этот рубеж покорился дважды.
Лидер Марафона, Влад Франк, отметился еще одним достижением: он решил 59 марафонских задач, больше, чем любой из других участников.

5 марафонских задач опубликованы в "Кванте" (еще несколько ждут своего часа).
А по мотивам еще одной задачи (или двух?) опубликована довольно большая статья в журнале "Потенциал". Считаю участников Марафона полноправными соавторами этих публикаций.

Поздравляю действующих, бывших и потенциальных (а также бывших и потенциальных одновременно) участников Марафона с Новым Годом!
Желаю, чтобы в наступающем году вам хватало времени, здоровья и творческого запала на все ваши достойные начинания и свершения! И чтобы еще немного оставалось на Марафон!

Жду от вас комментариев марафонских задач и пожеланий Марафону. Эта обратная связь позволит сделать Марафон интереснее для вас.
Никакого точного DeadLine для приема ваших пожеланий нет. Они принимаются без ограничений. Но все же желательно успеть оформить и отправить свои соображения еще в 2008-м году

[General]

Ура!!!
Спасибо!!!
С Новым годом!!!

[VAL]

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

Вызывает интерес доказательство (или опровержение) следующей гипотезы:
$ \forall k \in {\bf N\backslash\{1\}} \forall e>0 \exists n \in {\bf N}( q(n,k) < e)$

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

[VAL]

Обсуждение марафонских задач и сбор пожеланий Марафону протекают, мягко говоря, вяло

В целях оживления дискуссии информирую марафонцев и болельщиков, что числа $s(n,k)$, описанные в ММ100.4 появились в он-лайновой энциклопедии целочисленных последовательностей под красивым номером A155510 (http://www.research.att.com/~njas/sequences/).

[VAL]

А я то наивно полагал, что некотрые задания конкурса "Поиск закономерности 2" (сгенерированные мной практически с помощью датчика псевдослучайных чисел), не могут быть разгаданы в принципе
Оказывается могут!

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