• Правила марафона
• Рейтинг участников
• Архив Марафона

Стартовал 24-й конкурс в рамках Математического марафона

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

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

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

Жду от вас комментариев марафонских задач, а также пожеланий Марафону. Эта обратная связь позволит сделать Марафон интереснее для вас.

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

Ведущий Марафона — Vladimir letsko

Конкурсная задача ММ238 (7 баллов)

Решения принимаются до 27.10.2018

Вася написал на доске k последовательных натуральных чисел и нашел их НОК - V.
Петя написал k последовательных натуральных чисел, больших Васиных, и тоже нашел их НОК - P.
Оказалось, что 2018 < V/P < 2019.
При каком наименьшем k такое возможно?

Конкурсная задача ММ239 (10 баллов)

Решения принимаются до 17.11.2018

Существует ли выпуклый многогранник, у которого:
a) не менее половины граней - семиугольники;
b) более половины граней - семиугольники;
с) не менее половины граней - восьмиугольники;
d) более половины граней - восьмиугольники;
e) не менее половины граней - девятиугольники?

Примечание: Если у вас получается, что ответ на пункт «а» отрицательный, а на пункт «b» - положительный, подумайте еще.

Конкурсная задача ММ237 (7 баллов)

Студент математического факультета Вася Пупкин написал на доске некоторую перестановку A из S₁₀ в виде произведения независимых циклов (запись каждого цикла начинается с наименьшего элемента; опускались ли в записи циклы длины 1 - неизвестно). Васины однокурсники прокомментировали эту запись.

Аня: A⁶ – тождественная перестановка.
Ваня: Длины всех циклов A – числа Фибоначчи.
Даня: В S₁₀ существует ровно 3 перестановки, квадрат которых равен A.
Маня: Хм, уравнение X² =B не может иметь в S₁₀ ровно 3 решения ни при каком B.
Саня: Более того, количество решений уравнения X² =B в S₁₀ не может быть нечетным ни при каком B.
Таня: Квадрат наибольшего элемента в самом длинном цикле меньше порядка A.
Зина: A⁵ имеет столько же циклов, сколько и A.
Лина: Внутри всех циклов элементы строго возрастают.
Нина: Произведение всех элементов одного из циклов кратно произведению всех элементов более длинного цикла и сумме всех элементов более короткого.
Фаина: Зина, Лина и Нина правы.

Вася (умница и отличник) заметил, что количество верных утверждений его однокурсников равно наибольшей длине цикла в A.
Найдите A.

Решение

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

Обсуждение

Естественно конкурсанты начали решение с проверки утверждений Мани и Сани, истинность которых не зависит от записанной на доске перестановки.
Причем проверка утверждения Мани оказывается наиболее сложной частью задачи. Некоторые участники предпочли ограничиться доказательством отсутствия трех решений уравнения X²=B в S₁₀, другие же рассмотрели более общий вопрос о возможных количествах решений этого уравнения. Наконец, еще один участник привел чисто алгебраическое обоснование правоты Мани. Ведущий пошел по пути «других» (комбинаторщиков), но для надежности проверил свои теоретические выкладки возведением всех элементов S₁₀ в квадрат (разумеется, не руками). Конкурсанты оказались более уверенными в себе и к мощи компа не прибегали (некоторые - зря ).
Дальнейшие рассуждения практически все вели, перебирая возможные длины наибольшего цикла. И только Влад Франк отталкивался от истинности или ложности утверждения Фаины, показав, что этот путь тоже ведет к верному ответу.

Увлекшись обобщениями вопроса о количестве решений уравнения X²=B в S₁₀, я доказал, что для любого простого p и любого n уравнение X^p=B имеет либо единственное решение, либо количество его решений кратно p (для составных показателей это уже не так). Не остановшись на достигнутом, я вывел общую формулу для количества решений уравнения X^k=B в S_n (понятно, что ответ зависит от цикловой структуры B). Конечно, я понимал, что вряд ли являюсь первопроходцем: уж больно классический объект и слишком естественна постановка задачи. Но всерьез гуглить начал лишь только получив результат. Разумеется, у меня нашлись предшественники. Причем, насколько мне удалось установить, первая работа с ответом на этот вопрос была на русском языке (хотя я старательно формулировал запрос на английском): http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=sm&paperid=2731&option_lang=eng

Приведу все возможные количества решений X^k=B в S_n для небольших k и n.

k = 2
1 {1}
2 {0, 2}
3 {0, 1, 4}
4 {0, 1, 2, 10}
5 {0, 1, 2, 26}
6 {0, 1, 4, 76}
7 {0, 1, 2, 4, 8, 10, 232}
8 {0, 1, 2, 4, 8, 12, 20, 26, 764}
9 {0, 1, 2, 4, 10, 12, 16, 52, 76, 2620}
10 {0, 1, 2, 4, 6, 8, 10, 24, 26, 40, 152, 232, 9496}

k = 3
1 {1}
2 {1}
3 {0, 1, 3}
4 {0, 1, 9}
5 {0, 1, 3, 21}
6 {0, 1, 9, 81}
7 {0, 1, 3, 9, 21, 351}
8 {0, 1, 3, 9, 33, 81, 1233}
9 {0, 1, 3, 9, 18, 21, 27, 33, 351, 5769}
10 {0, 1, 3, 9, 18, 21, 33, 81, 1233, 31041}

k = 4
1 {1}
2 {0, 2}
3 {0, 1, 4}
4 {0, 1, 16}
5 {0, 1, 2, 56}
6 {0, 1, 4, 256}
7 {0, 1, 2, 4, 16, 1072}
8 {0, 1, 4, 8, 48, 56, 6224}
9 {0, 1, 2, 10, 16, 256, 33616}
10 {0, 1, 2, 4, 6, 10, 56, 64, 96, 1072, 218656}

k = 5
1 {1}
2 {1}
3 {1}
4 {1}
5 {0, 1, 25}
6 {0, 1, 145}
7 {0, 1, 25, 505}
8 {0, 1, 25, 145, 1345}
9 {0, 1, 25, 145, 505, 3025}
10 {0, 1, 25, 145, 385, 505, 1345, 78625}

k = 6
1 {1}
2 {0, 2}
3 {0, 6}
4 {0, 2, 18}
5 {0, 1, 2, 66}
6 {0, 1, 4, 396}
7 {0, 1, 2, 12, 2052}
8 {0, 1, 4, 6, 12, 36, 12636}
9 {0, 2, 4, 12, 18, 132, 91548}
10 {0, 2, 6, 8, 18, 24, 66, 792, 625176}

Поясню, как я реагировал на шибки при подсчете возможных количеств решений уравнения X²=B в S₁₀. Фатальная ошибка (вместо самих решений считалось лишь возможное количество их цикловых видов), приведшая к «опровержению» утверждения Маши, разумеется, нарушила весь дальнейший ход решения и была отражена в оценке. Автору неверных комбинаторных формул при подсчете количеств решений повезло больше. Одно решение при этом не исчезло, а три не появилось. Поэтому дальнейшая цепочка рассуждний привела к верному ответу. Но оставить ощибки на промежуточных шагах без внимания я, конечно, не мог. Наконец, локальные арифметические ошибки, не повлиявшие на решения я вовсе не учитывал. Пример такой ошибки есть в приведенном решения Анатолия Казмерчука (там, где у Анатолия получилсь 18 решений должно быть 24). В самом деле, 18 получается как сумма двух слагаемых, одно из которых подсчитано верно и равно 12. Понятно, что сумма при этом будет больше 3, что собственно и требовалось. Поэтому данная вычислительная ошибка в принципе не могла повлиять на ход решения. Неполный балл у Константина Шамсудтинова связан не с ошибками, а с недостаточно подробным изложением решения. Обосновав верную оценку утверждений Сани и Мани, Константин написал, что дальнейшее очевидно и привел павильный ответ.

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

Награды

За решение задачи ММ237 участники Марафона получают следующие призовые баллы:
Анатолий Казмерчук - 10;
vpb - 8;
Виктор Филимоненков - 7;
Владислав Франк - 7;
Константин Шамсутдинов -6.
Валентина Колыбасова - 5;
Евгений Гужавин - 2;

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

Конкурсная задача ММ2409 (13 баллов)

Решения принимаются до 01.12.2018

Проективную плоскость разбили несколькими прямыми общего положения. При этом образовалось ровно 17 треугольников. Сколько пятиугольников могло при этом получиться?

Конкурсная задача ММ236 (7 баллов)

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

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

Решение

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

Обсуждение

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

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

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

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

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

Награды

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

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

Конкурсная задача ММ235 (7 баллов)

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

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

Конкурсная задача ММ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))), …}|.
Пусть a и b – 2018-значные числа. Может ли оказаться, что g(a) = g(b) + 26?

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

Конкурсная задача ММ233 (6 баллов)
Очередной отголосок ЕГЭ в Марафоне

При каких значениях параметра a множество точек плоскости, задаваемых системой
(x - a + 1)² + (y - 3)² ≤ 80,
(x - 3)² + (y - 4a + 1)² ≤ 20a²,
230 - 2a = |4x + 3y + 115 - a| + |4x + 3y - 115 + a|
является кругом?

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

Конкурсная задача ММ232 (6 баллов)

Сколько решений в натуральных числах, имеет уравнение x³ + y³ = z³ - i для каждого i ∈ {1, 2, 4} ?

Я нашел воистину замечательные ответы на эти вопросы, но поля… Надеюсь, у конкурсантов с полями все хорошо.

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

Конкурсная задача ММ231 (4 балла)

На сторонах AB, BC и AC египетского треугольника ABC выбрали точки C₁, A₁ и B₁ соответственно. Оказалось, что треугольники AB₁C₁, BC₁A₁ и CA₁B₁ равновелики. Какую часть площади ABC составляет площадь треугольника A₁B₁C₁ при условии, что последний - прямоугольный?

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