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

[grizzly]

Ariadna H в сообщении #1340890 писал(а):

Анимация к задаче ММ233

Спасибо, понравилось!

[VAL]

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

[VAL]

===========ММ234===============

ММ234 (5 баллов)

Функция $g(n)$ натурального аргумента $n$ задается так:
Пусть $n$ натуральное число. Определим $f(n)$ как число, полученное удалением последней цифры из десятичной записи $n$, увеличенное на квадрат этой цифры.
Например, $f(576) = 57 + 36 = 93$.
Тогда $g(n) = |\{n, f(n), f(f(n)), f(f(f(n))), \dots \}|$.
Пусть $a$ и $b$ – 2018-значные числа. Может ли оказаться, что $g(a) = g(b) + 26$?

Решение

Привожу решения Юрия Варламова (минималистическое) Василия Дзюбенко (более развернутое) и vpb (солидное).

(Решение vpb)

Решение задачи ММ234

Обозначим $f^{(k)}(n)=f(f(f...(n)))$ ( $f$ применяется $k$ раз), $f^{(0)}(n)=n$.
Общая идея такова: при большом $n$ $f(n)\approx n/10$. Последовательность $x_k=f^{(k)}(n)$ ведет себя примерно как $n/10^k$, а ближе к концу начинает колебаться, и в конце зацикливается.

Разобьем решение на несколько мелких утверждений.
1) Лемма. Пусть $a$, $b$ --- постоянные, $a\ne1$, и последовательность $(y_n)$ удовлетворяет условию $y_n=ay_{n-1}+b$, $\forall\ n$. Тогда всегда

$$ y_{n+k}=a^ky_n+\frac{a^k-1}{a-1}b\,.$$

Доказательство --- очевидной индукцией по $k$.

2) Всегда $f(n)\leq(n+801)/10$ и $f(n)\geq n/10$.
Действительно, пусть $r$ --- последняя цифра в $n$, тогда
$f(n)=(n-r)/10+r^2=n/10+(r^2-r/10)\leq n/10+(9^2-9/10)=n/10+801/10$.

3) Если $n\leq89$, то $f(n)\leq89$.
Очевидно следует из 2).

4) Если $n>89$, то $f(n)<n$.
Действительно, если $n>89$, то $(n+801)/10<n$, и тем более $f(n)<n$.

Из 3), 4) следует, что $X=\{1,2,\ldots,89\}$ --- инвариантное множество и
аттрактор для $f$. Непосредственно выясняя, как действует $f$ на $X$, можно
найти значения $g$ на $X$; в частности, $g(n)$ принимает на $X$ все значения
между $1$ и $26$; $g(1)=g(89)=1$, $g(48)=26$ .
Также, циклы для $f$, т.е. такие подмножества $\{x_1,\ldots,x_t\}$,
которые $f$ переставляет по циклу, суть $\{1\}$, $\{89\}$, и $\{9,81\}$.

5) Если $n$ --- 2018-значно, то $g(n)\geq2017$. Значение $g(n)=2017$
достигается.
Действительно, $n$ последовательно уменьшается под действием $f$, пока не
попадает в $X$. При этом, как следует из второго утверждения в 2), число
цифр в $n$ всегда уменьшается не более чем на 1. Любое число в $X$ одно-
или двузначно. Поэтому, чтоб добраться от $n$ до него, надо сделать по
крайней мере 2016 шагов, откуда $g(n)\geq2017$.
При $n=89\cdot10^{2016}$ эта оценка достигается.

Дальше хотим оценить $g(n)$ сверху.

6) Всегда $f^{(k)}(n)\leq 10^{-k}n+89$.
Индукция по $k$, с использованием 2). База $k=0$ очевидна. Шаг:

$$f^{(k+1)}(n)=f(f^{(k)}(n))\leq \frac{f^{(k)}(n)}{10}+\frac{801}{10} \leq \frac{10^{-k}n+89}{10}+\frac{801}{10}=10^{-(k+1)}n+89.$$

7) Используя 4) и таблицу значений $g(n)$ при $n\leq89$, легко найти значения
$g(n)$ при $90\leq n\leq 192$. В частности, максимальное значение есть $g(126)=27$.

8) Заметим следующее: если $n'=f^{(k)}(n)$ не лежит в каком-либо цикле, то
$g(n)=k+g(n')$. (Это ясно).

9) Если $n\leq 10^{2018}-1$, то $g(n)\leq2043$.
Действительно, рассмотрим $n'=f^{(2016)}(n)$. Тогда

$$n'\leq 10^{-2016}(10^{2018}-1)+89\leq100-10^{-2016}+89,$$

откуда на самом деле $n'\leq188$. По 7), $g(n')\leq27$. Значит $g(n)=2016+g(n')\leq 2043$.

10) Теперь покажем, что верхняя оценка для $g(n)$ достигается. Для $n\geq90$ определим

$$ h(n)=10(n-81)+9=10n-801. $$

Тогда довольно ясно, что $h(n)>n$ и $f(h(n))=n$, откуда $g(h(n))=g(n)+1$. Мы возьмем $N=h^{(2016)}(126)$. Легко посчитать, используя 1), что $N=37\cdot10^{2016}+89$ --- 2018-значное. $g(N)=2016+g(126)=2016+27=2043$.

Таким образом, искомые $a$ и $b$ существуют. Чем задача и решена.

Обсуждение

Большая разрядность чисел в условии, кроме очевидной отсылки к году проведения конкурса, призвана устранить прямое переборное решение.
Но, разумеется, это лишь некая "дымовая завеса". Разность 26 достигается уже для трехзанчных чисел и больше не меняется с ростом разрядности. Я полагаю, что это заметили все конкурсанты. Но, в условиях дефицита красивых обобщений, я поощрил дополнительным тех, кто явно сформулировал этот момент.
Еще один дополнительный балл, получил vpb (за лемму 1, без которой в решении вполне можно обойтись). И это тоже свидетельство некоторой тоски ведущего о реально серьезных обобщениях и интересных аналогах конкурсных задач.
Я был почти уверен, что многие конкурсанты рассмотрят наиболее напрашивающиеся аналоги ММ234 для других систем счислеия, других степеней последней цифры. И, возможно, иные.
Однако, к другим системам счисления обратился лишь Владимир Дорофеев. Он заметил, что аналог петли 89 имеется для всех оснований ситемы счисления, больших 2, и наличие петель для систем с основанием $k^2-k+1$. Например, в семеричной системе $g_7(13)=g_7(24)=1$. Однако и Владимир не пошел дальше рассмотрения одноэлементных циклов.
Честно признаюсь, и сам ведущий поленился рассматривать естественные обобщения данной задачи. В отличие от ряда других.

Награды

За решение задачи ММ233 участники Марафона получают следующие призовые баллы:

Владимир Дорофеев - 6;
Василий Дзюбенко - 6;
Анатолий Казмерчук - 6;
vpb - 6;
Юрий Варламов - 5;
Валентина Колыбасова - 5;
Виктор Филимоненков - 5;
Евгений Гужавин - 5;
Владимир Чубанов - 5;
Владислав Франк - 5.

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

[VAL]

===========ММ235===============

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

Существует ли выпуклый многогранник, у которого равны: количество ребер; количество диагоналей; суммарное количество диагоналей граней?

Решение

Привожу решения Виктора Филимоненкова и Анатолия Казмерчука.

Обсуждение

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

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

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

Награды

За решение задачи ММ235 участники Марафона получают следующие призовые баллы:
Анатолий Казмерчук - 9;
Виктор Филимоненков - 9;
vpb - 8;
Константин Шамсутдинов - 8;
Валентина Колыбасова - 8;
Владимир Чубанов - 8;
Владислав Франк - 7.

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

[grizzly]

VAL
В задаче 236 речь идёт об абсолютном минимуме для всех $n$ или своём минимуме для каждого $n$ (то есть о формуле зависимости минимума от $n$)?

[VAL]

grizzly в сообщении #1344989 писал(а):

VAL
В задаче 236 речь идёт об абсолютном минимуме для всех $n$ или своём минимуме для каждого $n$ (то есть о формуле зависимости минимума от $n$)?

Об абсолютном для всех $n$.

[VAL]

===========ММ236===============

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

Натуральные числа от 1 до $4n$ разбили на четыре группы по $n$ чисел в каждой. Оказалось, что произведение всех чисел из первой группы равно произведениям всех чисел из второй и третьей групп. Найти наименьшую возможную сумму чисел четвертой группы.Существует ли выпуклый многогранник, у которого равны: количество ребер; количество диагоналей; суммарное количество диагоналей граней?

Решение

Привожу решения Виктора Филимоненкова (мне понравилось его доказательство минимальности ответа), Юрия Варламова (с принципиально иным подходом к доказательству минимальности) и Анатолия Казмерчука (с хорошей оценкой на подходящие $n$ для обобщения задачи).

Обсуждение

Наиболее сложной частью решения данной задачи оказалось внимательное прочтение условия. Сразу три конкурсанта решали другую задачу, в которой произведение чисел первой группы равнялось не произедениЯМ чисел из второй и третьей групп, а произведениЮ этих произведений. Причем один из них не "исправился" даже после явного указания на этот момент.

Основным недочетом решения было недостаточно строгое обоснование минимальности найденного ответа. Лично меня вполне убеждает реплика типа "ясно, что с дальнейшим ростом $n$ сумма чисел в 4-й группе будет возрастать". Но балл я, все таки, снимал. Тем более, что я не вовсе не уверен в монотонности этого роста.

Другие неточности были связаны с тем, что один из конкурсантов "прозевал" требуемое разбиение для $n=10$ и нашел его только для $n=11$, а другой наоборот не заметил разбиения для $n=11$. Последнее, правда, вовсе и не требовалось (при наличии разбиения для $n=10$), но это не повод, чтобы утверждать, что его нет

Задача просто напрашивается на обобщения. Выражу эти обобщения в виде двух предположений:

1. Для любого натурального $k$ найдется натуральное $n$ такое, что числа от 1 до $kn$, можно разбить на $k$ групп по $n$ чисел так, что произведения чисел во всех группах, за исключением одной, будут одинаковы.
2. Для любого натурального $k$ найдется натуральное $n_0$ такое, что для любого натурального $n\ge n_0$ числа от 1 до $kn$, можно разбить на $k$ групп по $n$ чисел так, что произведения чисел во всех группах, за исключением одной, будут одинаковы.

Тех конкурсантов, которые высказали подобные гипотезы, я поощрял дополнительным призовым баллом. Еще одним баллом поощрялись оценки снизу для подходящих $n$ для разных количеств групп. Разглядеть следы этих поощрений в разделе "Награды" можно не всегда, поскольку они в значительной мере скомпенсировались штрафами за отмеченные выше недостатки.

Подтвердить первое утверждение мне удалось пока лишь для $k=5$. Подходящее $n$ оказалось равно 440. Оно хорошо согласуется с оценкой из решения Анатолия и, по-видимому, является минимальным.
В особую группу в этом случае можно включить числа:
47, 59, 71, 73, 79, 83, 97, 101, 103, 113, 127, 139, 149, 151, 157, 158, 163, 167, 191, 193, 194, 197, 199, 211, 223, 226, 227, 229, 233, 239, 241, 277, 278, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 382, 383, 386, 389, 394, 397, 398, 401, 409, 417, 419, 421, 422, 431, 433, 439, 554, 557, 562, 563, 566, 569, 571, 573, 577, 586, 587, 593, 599, 601, 607, 613, 614, 617, 619, 622, 625, 626, 631, 634, 641, 643, 647, 653, 659, 661, 662, 673, 674, 677, 683, 691, 694, 698, 701, 709, 719, 727, 729, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 831, 839, 843, 849, 853, 857, 859, 863, 877, 879, 881, 883, 887, 907, 911, 919, 921, 929, 933, 937, 939, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1059, 1061, 1063, 1069, 1077, 1087, 1091, 1093, 1097, 1103, 1109, 1114, 1117, 1123, 1126, 1129, 1138, 1142, 1151, 1153, 1154, 1163, 1171, 1174, 1181, 1186, 1187, 1193, 1198, 1201, 1202, 1213, 1214, 1217, 1223, 1226, 1229, 1231, 1234, 1237, 1238, 1249, 1259, 1262, 1277, 1279, 1282, 1283, 1286, 1289, 1291, 1294, 1297, 1301, 1303, 1306, 1307, 1318, 1319, 1321, 1322, 1327, 1346, 1354, 1361, 1366, 1367, 1373, 1381, 1382, 1399, 1402, 1409, 1418, 1423, 1427, 1429, 1433, 1438, 1439, 1447, 1451, 1453, 1454, 1459, 1466, 1471, 1478, 1481, 1483, 1486, 1487, 1489, 1493, 1499, 1502, 1511, 1514, 1522, 1523, 1531, 1538, 1543, 1546, 1549, 1553, 1559, 1567, 1571, 1574, 1579, 1583, 1594, 1597, 1601, 1607, 1609, 1613, 1618, 1619, 1621, 1622, 1627, 1637, 1642, 1646, 1654, 1657, 1658, 1663, 1667, 1669, 1671, 1678, 1679, 1689, 1693, 1697, 1699, 1706, 1707, 1709, 1713, 1714, 1718, 1721, 1723, 1726, 1731, 1733, 1741, 1747, 1753, 1754, 1759, 1761, 1762, 1766, 1774, 1777, 1779, 1783, 1787, 1789, 1797, 1801, 1803, 1811, 1814, 1817, 1821, 1822, 1823, 1831, 1838, 1839, 1847, 1851, 1857, 1858, 1861, 1867, 1871, 1873, 1874, 1877, 1879, 1882, 1889, 1893, 1894, 1901, 1906, 1907, 1909, 1913, 1923, 1927, 1929, 1931, 1933, 1934, 1937, 1941, 1942, 1949, 1951, 1954, 1959, 1963, 1966, 1973, 1977, 1979, 1982, 1983, 1987, 1993, 1994, 1997, 1999, 2003, 2011, 2017, 2018, 2019, 2026, 2027, 2029, 2031, 2038, 2039, 2041, 2042, 2049, 2053, 2059, 2062, 2063, 2066, 2069, 2073, 2078, 2081, 2083, 2087, 2089, 2098, 2099, 2102, 2103, 2111, 2113, 2122, 2123, 2126, 2127, 2129, 2131, 2137, 2138, 2141, 2143, 2147, 2153, 2157, 2161, 2167, 2173, 2174, 2179, 2181, 2182, 2186, 2189, 2194, 2199
Я, правда, поленился разбивать остальные 1760 чисел отрезка $[1..2200]$ на 4 группы по 440 чисел с произведениями
2504958280188081419921948972441396317993403801235686917189404793494410952319221107430699726426543482893150616818461328275525066728687821299944018804591123621764708436862923779082966701604255562735809
1289805092573842321119037749653748128030277852462704135079581240704766941274957290255116129389746051106781284949262988305500523148052986768314929608953462205114770269799533777220776888022882268969186
8256939455438775400312990802515143584992001317970206751063207265933958654529870772678667922698614937697266272985614883442793368986129518695143853094690122842913111643945798988875703895754483271038238
5182286564472391875215890301211571968504622359098107301057543005228410333158529079435309905796210654850747735976571461993013928271912292976427305555810117105923392750217796599906972251697366242580020
6575367017793348811892036002082886312661321854126266243791495009659816597145491149452188822078532158201083317945464571775879624578222350271609362065397049910467258829985447414830630497759605272939234
1842004607084907601089731497294700874743226451167075020005453698345376641104337205715485217753202924728864257010129270319864299599985377280000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000.
Но, учитывая, что произведение этих чисел в точности равно 4-й степени вышеприведенного числа, я уверен, что это возможно.

Что касается второй гипотезы, полагаю, что для $k=4$ подходит $n_0=28$. Среди $n$, меньших $n_0$ требуемое разбиение возможно для $n \in \{10,11,14,15,18,20,22,23,24,25,26\}$. Я не искал требуемого разбиения для большинства этих $n$, ограничившись составлением 4-й группы, для которой произведение остальных чисел является точным кубом.
Моя уверенность в том, что $n_0=28$ базируется на том, что бОльших чисел 4-я группа составляется со все возрастающим запасом (из отрезка $[1..4n]$ можно изъять существенно меньше $n$ чисел так, что произведение остальных будет кубом). Но точного доказательства у меня нет.

Награды

За решение задачи ММ236 участники Марафона получают следующие призовые баллы:
Анатолий Казмерчук - 9;
Виктор Филимоненков - 7;
Валентина Колыбасова - 7;
Владислав Франк - 7;
Евгений Гужавин - 7;
Владимир Дорофеев - 7;
Юрий Варламов - 7;
Дмитрий Курашкин - 6;
Владимир Чубанов - 6;
Константин Шамсутдинов -3.

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

[rockclimber]

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

Лично меня вполне убеждает реплика типа "ясно, что с дальнейшим ростом $n$ сумма чисел в 4-й группе будет возрастать". Но балл я, все таки, снимал.

А почему снимали, если вас это убеждает? Для каждого следующего $n$ по сравнению с предыдущим из 4-й группы убираются меньшие числа и добавляются большие. Кстати, в качестве дополнительной задачи можно было бы поискать хоть один пример немонотонности. То есть если обозначить минимально возможную сумму чисел 4-й группы для данного $n$ как $S_n$, то найти такое $n$, для которого $S_n < S_{n-1}$.

А кто-нибудь знает алгоритм формирования 4-й группы? Не так, чтобы на глазок выбирать, а чтобы запрограммировать можно было? Можно будет попробовать продолжить поиски. Я написал программу, которая делает все вплоть до переноса в 4-ю группу "хвоста распределения" - то есть простых чисел, которые входят в $(4n)!$ со степенями 2 и меньше. А вот дальше считал вручную. Осталось чуть-чуть дописать, но идей никаких.

[VAL]

rockclimber в сообщении #1346157 писал(а):

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

Лично меня вполне убеждает реплика типа "ясно, что с дальнейшим ростом $n$ сумма чисел в 4-й группе будет возрастать". Но балл я, все таки, снимал.

А почему снимали, если вас это убеждает?

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

Возвращаюсь к ММ236. Тут все не так просто. Может оказаться, что с увеличением $n$ новых простых не добавится, но при этом пара чисел $p$ и $2p$ уйдут из 4-й группы, поскольку $3p$ станет меньше $n$. Правда, при этом могут возрасти степени меньших простых чисел и перестать быть кратными 3. В общем, не так все очевидно.

[grizzly]

rockclimber в сообщении #1346157 писал(а):

все вплоть до переноса в 4-ю группу "хвоста распределения" - то есть простых чисел, которые входят в $(4n)!$ со степенями 2 и меньше.

Предлагаю так:

1. Вы уже выбрали первую часть группы 4.
2. После этого выбираем числа, которые больше $\sqrt{4n}$ и степени которых не кратны 3.
3. Часть этих чисел попадут в группу 4 (ровно столько, чтобы обократнить трём показатели оставшихся).
4. Если излишков показателей по модулю 3 у чисел из п.2 в сумме с мощностью части п.1 получилось больше $n$, конец алгоритма;
4.1 Иначе -- нужно смотреть, можно ли удалить часть выбранных в п.2 чисел так, чтобы все младшие множители остались при кратных 3 степенях (никто не сомневается, что при $n>1$ это получится сделать -- здесь понадобится простой "set covering", который при не очень больших $n$ можно будет тупо перебрать);
5. Если после этого нужно будет добавить ещё чисел в группу 4 -- добрасываем кубами мелких чисел или делаем ещё один set covering.

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

[VAL]

grizzly в сообщении #1346193 писал(а):

Предлагаю так:[..]

Вы полагаете, я приведенную в обсуждении из 440 чисел руками искал?!

Приблизительно по описанной Вами схеме. Правда, не самостоятельной программкой, а неким гибридом в maple.
Подробности сейчас не помню. Дело было еще в апреле.

[grizzly]

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

Вы полагаете, я приведенную в обсуждении из 440 чисел руками искал?!

Нет, конечно, я всего лишь полагаю, что если уважаемый rockclimber заинтересуется, то у нас может появиться статистика разбиений до $10^{10}$ групп

[rockclimber]

Я не то чтобы сильно заинтересовался, просто основная часть программы уже написана. Если чуть доработать, то можно ее просто запустить, и пусть молотит числа до посинения.

grizzly в сообщении #1346193 писал(а):

4.1 Иначе -- нужно смотреть, можно ли удалить часть выбранных в п.2 чисел так, чтобы все младшие множители остались при кратных 3

Так тут вся соль в том, как именно "нужно смотреть". Я же не могу сказать компьютеру "ну ты посмотри там".
Пока алгоритм вырисовывается такой:
1. Числа, которые входят в $(4n)!$ со степенями 1 или 2 - убираем все.
2, Числа, которые больше $\sqrt{4n}$, но которые входят со степенями, не кратными 3, нужно убрать 1 или 2 таких числа. Если нужно убрать одно - то само это число, а если два - тут возможны варианты. И проблема еще в том, что нужно учитывать, сколько именно нужно убрать чисел. Вот тут я не уверен, но думаю, может, начать программировать, а потом посмотреть, чего не хватает.

[grizzly]

rockclimber в сообщении #1346277 писал(а):

Если нужно убрать одно - то само это число

Нет, тут тоже те же варианты.
Я думаю, что если Вы пройдёте руками этот алгоритм для $n=11$ (это займёт от силы пару минут), тогда всё станет просто и понятно. Там после шага 1 (который Ваш) останется убрать только одно число, кратное 11. Там этих чисел 4, но убрать нужно именно число 33 -- тогда все остальные степени станут кратными трём.

[rockclimber]

grizzly в сообщении #1346290 писал(а):

Я думаю, что если Вы пройдёте руками этот алгоритм для $n=11$

Руками я его проходил уже, спасибо, что напомнили (я - тот самый участник, который нашел решение для $n=11$, но проскочил $n=10$ ).
Тогда наверное так (шаги те же, что и в предыдущем сообщении)
1) Все то же самое, но дополнительно запоминаем, что с каждым простым числом, которое входит в факториал 2 раза, мы дополнительно убираем одну двойку
2) Для чисел больше $\sqrt{4n}$ считаем, сколько их надо убрать (эти числа хороши тем, что их квадраты в факториал не входят, поэтому их посчитать проще). Соответственно, каждому такому числу может соответствовать некоторая степень одного из маленьких чисел (меньше $\sqrt{4n}$). Тут нужно посчитать, сколько мест осталось в 4-й группе. На примере $n=11$ - решить, убирать $3$ и $11$ или $33$.