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

[VAL]

===========ММ254===============

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

Вася вписал круг в треугольник со сторонами 3, 4, 5. И вписывает новые круги так, что каждый последующий касается двух сторон треугольника и одного из предыдущих кругов. Может ли суммарная площадь кругов превысить 80% от площади треугольника и на каком шаге (круге) может случиться это событие?

Решение

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

Обсуждение

В отличие от прошлой задачи, при решении ММ254 избежали технических ошибок (хотя ошибиться было где). Но неожиданно вернулись проблемы с пониманием условия и вопроса задачи.
И если для ММ251 такие проблемы были вполне ожидаемы (я уже объяснял, почему сознательно не стал доскональнее прописывать условие той задачи), то ММ254 представлялась мне сформулированной ясно и однозначно.
Единственный нюанс - учитывать ли первый круг. Для придания однозначности я продублировал слово "шагов", словом "кругов", поясняя, что первый круг тоже следует считать. Тем не менее, сосчитали его не все. Но я заранее решил, что не буду считать это за ошибку.
Я не снижал баллы и за отсутствие явного указания на то, что Вася может и не добраться до 80% даже при бесконечном числе шагов (ведь в задаче спрашивалось "может ли площадь кругов превысить 80%", а не "превысит ли").
Теперь о замечаниях, за которые баллы снимались.
Валентин Пивоваров почему-то решил, что за один шаг обязательно вписывается сразу по 3 круга (в каждый из углов треугольника). Перечитав условие я убедился, что в нем нет намеков на такое толкование. Тем не менее, я счел возможным поставить Валентину достаточно высокий балл, поскольку параметры трех геометрических прогрессий были определены верно, то есть, было сделано практически все, что нужно для решения.
Еще два участника почему-то ограничились нахождением наименьшего количества кругов, покрывающих более 80% площади треугольника. Пронализировав условие, я пришел к выводу, что вина за такую трактовку лежит исключительно на этих участниках
Наконец, в одном из решений превышение 80% на любом круге, начиная с 6-го, отмечается, но отдельно не обосновывается. Хотя легко подобрать начальные данные так, что правильным ответом будет, например, такой "требуемый процент будет превышен на 3-м, 4-м или 5-м шаге".

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

Отдельно отмечу замечательное наблюдение Олега Полубасова - поразительную близость отношения площади египетского треугольника к сумме площадей вписанного круга и трех кругов, вписанных в углы треугольника, к $\frac{\pi}2$.

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

Награды

За решение задачи ММ254 участники Марафона получают следующие призовые баллы:
Анатолий Казмерчук - 7;
Владислав Франк - 7;
Олег Полубасов - 7;
Константин Шамсутдинов - 6;
Виктор Филимоненков - 6;
Денис Овчинников - 5;
Валентин Пивоваров - 4.

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

[vlad239]

Владислав Франк строго обосновал нижнюю границу

Не уверен. Я обосновал лишь то, что при очень остроугольных треугольниках ответ будет мало отличаться от нижней границы. То, что для других он не окажется еще меньше - ниоткуда там не следует. Надо бы снять мне балл.

[VAL]

vlad239 в сообщении #1484959 писал(а):

Владислав Франк строго обосновал нижнюю границу

Не уверен. Я обосновал лишь то, что при очень остроугольных треугольниках ответ будет мало отличаться от нижней границы. То, что для других он не окажется еще меньше - ниоткуда там не следует. Надо бы снять мне балл.

Похвальная самокритичность. С критикой ведущего тоже согласен.
Заменил "строго обосновал" на получил. Но баллы трогать не стал.

[VAL]

===========ММ255===============

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

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

Решение

Привожу решения Виктора Филимоненкова, Олега Полубасова и Константина Шамсутдинова.

Обсуждение

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

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

Награды

За решение задачи ММ255 участники Марафона получают следующие призовые баллы:\
Константин Шамсутдинов - 10;
Олег Полубасов - 9;
Анатолий Казмерчук - 8;
Владислав Франк - 8;
Денис Овчинников - 8;
Виктор Филимоненков - 7;
Владимир Дорофеев - 4.

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

[VAL]

===========ММ256===============
ММ256 (8 баллов)

При каком наименьшем натуральном $n$ уравнение $n\{x\}^2+\{x\}=\lfloor x\rfloor$ имеет не менее 1000000 решений в рациональных числах?

Примечание: $\{x\}$ – дробная часть числа $x, \lfloor x\rfloor$ – целая часть (пол) числа $x$.

Решение

Привожу решения vpb, Дениса Овчинникова и Анатолия Казмерчука.

(Решение vpb)

ММ256

Заметим, что если $x$ --- решение уравнения $n\{x\}^2+x=\lfloor x\rfloor$, то числа $\alpha=\{x\}$ и $\beta=\lfloor x\rfloor$ удовлетворяют уравнению $n\alpha^2+\alpha=\beta$, и также $\alpha\in[0,1)\cap{\mathbb Q}$, $\beta\in{\mathbb Z}$. Наоборот, если $\alpha\in[0,1)\cap{\mathbb Q}$ и $\beta\in{\mathbb Z}$ удовлетворяют условию $n\alpha^2+\alpha=\beta$, то $x=\alpha+\beta$ удовлетворяет уравнению. Таким образом, нам надо посчитать, для данного $n$, сколько есть пар $\alpha$, $\beta$ с указанными условиями. То есть сколько есть чисел $\alpha\in[0,1)\cap{\mathbb Q}$ таких, что $n\alpha^2+\alpha$ --- целое.

Пусть $\alpha=p/q$, где $(p,q)=1$. Условие записывается как $n p^2/q^2+p/q\in{\mathbb Z}$. Тогда $np^2/q+p$ --- целое, а значит, и $np^2/q$ --- целое. Поскольку $p$ и $q$ взаимно просты, то $n$ должно делиться на $q$.

Итак, $n=n'q$. Условие переписывается как $n'p^2/q+p/q\in{\mathbb Z}$, что означает в точности, что $(n'p+1)p$ делится на $q$. Отсюда, опять в силу взаимной простоты $p$ и $q$, $n'p+1$ делится на $q$. Значит, $n'$ должно быть взаимно просто с $q$.

С другой стороны, пусть $q$ --- любой делитель $n$ такой, что $(n',q)=1$, где $n'=n/q$. Существует ровно одно $p$, $0\leq p<q$, такое, что $n'p\equiv-1\pmod q$. Тогда, ясно, $\alpha=p/q$ удовлетворяет требуемым условиям.

Итак, решения исходного уравнения взаимно однозначно соответствуют делителям $q$ числа $n$ таким, что $(n/q,q)=1$. А такие делители, конечно, взаимно однозначно соответствуют всем подмножествам во множестве простых делителей числа $n$. Значит, искомое число решений есть $2^s$, где $s$ --- число различных простых делителей $n$. Наименьшее $s$, при котором $2^s>10^6$ --- это $s=20$. Отсюда $n=2\cdot 3\cdot\ldots\cdot71$.

Обсуждение

В Марафоне неоднократно встречались задачи про функции $\lfloor x\rfloor$ и $\{x\}$ (ММ79, ММ176, ММ202, ММ263...)
Маскируется под них и ММ256. Но прозорливые конкурсанты верно разглядели в ней задачку по арифметике (теории чисел). И уверенно справились.
А вот попыток изучить аналоги и обобщения было меньше обычного. Единственным, кто преуспел в этом оказался (и это не стало неожиданностью для ведущего) Анатолий Казмерчук.

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

Награды

За решение задачи ММ256 участники Марафона получают следующие призовые баллы:
Анатолий Казмерчук - 10;
Константин Шамсутдинов - 8;
Олег Полубасов - 8;
Владислав Франк - 8;
Денис Овчинников - 8;
Виктор Филимоненков - 8;
vpb - 8.

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

[VAL]

Решил разместить числа, возникающие в ММ255 в OEIS.
При этом обнаружилось два расхождения в данных, приведенных Олегом Полубасовым и Константином Шамсутдиновым.
А именно: $a_p(18)=93312, a_s(18)=181440$ и $a_p(20)=82944, a_s(20)=5598720$.
Сам я решал ММ255 руками и программку не писал.
А при ручном переборе представлений для указанных чисел недолго и наврать.
Рассудите нас люди! (c)

[VAL]

Ручной перебор показал, что $a(18)\le 93312$.

[VAL]

===========ММ257===============

Задача ММ257 сюжетно связана с ММ237.

ММ257 (9 баллов)

Студент математического факультета Вася Пупкин пропустил (по уважительной причине) занятие по дискретной математике. Однокурсники рассказали, что на занятии рассматривался некий граф. Но ни один из них не зафиксировал этот граф ни с помощью гаджетов, ни на бумагу. Впрочем, Васины однокурсники, утверждают, что это не страшно, поскольку они и так помнят этот граф. В подтверждение своих слов они наперебой кинулись вспоминать характеристики графа:
Аня: В графе было ровно 3 связных компоненты.
Ваня: Причем во всех связных компонентах графа имелись циклы.
Даня: А еще среди связных компонент не было изоморфных.
Маня: Число ребер в одной из компонент было равно половине общего числа ребер.
Саня: При этом число ребер было равно сумме количеств вершин и связных компонент.
Таня: В графе была всего одна вершина степени 3.
Зина: А всего в графе было не более 13 вершин.
Лина: И при этом не было висячих вершин.
Нина: А степень одной из вершин не менее чем на 2 превосходила степень каждой из остальных вершин.
Фаина: Зина, Лина и Нина правы.
Услышавший эти реплики преподаватель сказал, что память подвела ровно одного человека. Сможет ли Вася (умница и отличник) однозначно восстановить граф?

===== ММ257 =====
Решение

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

Обсуждение

Сразу несколько участников покритиковали ведущего за то, что он не уточнил, что имеет в виду под "графом".
Сначала меня удивила такая реакция: ведь в предудыщих марафонских турнирах графы фигурировали десятки раз и подобных вопросов не возникало.
Задумавшись я понял, что в большинстве предыдущих задач структура графа, возникающего на том или ином множестве, вводилась прямо в условии.
Впрочем, в ряде задач (ММ105, ММ116, ММ146, ММ153, ММ156) так же как и в ММ257 рассматривались абстрактные графы, но к неоднозначности это не приводило. А меожет, и приводило... Давно это было, 100 задач назад.
В общем, на будущее: под графом я всегда имею в виду классический граф: непустое (обычно конечное) множество вершин и множество ребер, каждое из которых есть двухэлементое множество вершин.
Это не значит, что я зарекаюсь использовать будущих задачах, орграфы, мультиграфы, гиперграфы, бинарные отношения и даже матроиды. Но когда я буду использовать такие структуры, я отдельно заострю на этом внимание.

Составляя задачу, я вдохновлялся ММ237. И начал с того, что продублировал реплику Фаины. Дальнейшие реплики подбирались так, чтобы, с одной стороны, не было лишних, а с другой - граф определялся однозначно.
Вроде, удалось. Хотя задача понравилась далеко не всем. Но мне понравилась. Поэтому я, все же, намерен в одном из грядущих конкурсов заставить Васю и его друзей обсудить новый математический объект.

У тех, кто отозвался, задача затруднений не вызвала. Единственный балл изъят за излишнее увлечение сестрой таланта.

Награды

За решение задачи ММ257 участники Марафона получают следующие призовые баллы:
Анатолий Казмерчук - 10;
Константин Шамсутдинов - 9;
Владислав Франк - 9;
Денис Овчинников - 9;
Виктор Филимоненков - 9;
Олег Полубасов - 8.

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

[VAL]

===========ММ258===============

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

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

Решение

Привожу решения Виктора Филимоненкова, Дениса Овчинникова и Анны Букиной.

Обсуждение

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

Естественные обобщения задачи рассмотрели Олег Полубасов и Анатолий Казмерчук. Процитирую Олега:

Цитата:

Если рассмотреть всевозможные тройки {a, b, c} от {1, 1, 1} до {9, 9, 9}, то окажется, что размеры множеств сумм могут принимать следующие значения:
2-38, 40, 42-49, 52, 56, 57, 60.
Двухэлементное множество сумм даёт тройка {1, 1, 1}, а 60-элементное – тройка {7, 8, 9}.
Чаще всего (13 раз) встречается размер 24. Размер 25 встречается 7 раз.

Эта техническая и достаточно рутинная задача возникла как побочный продукт из попытки решить более содержательную задачу.
Легко понять, что суммы квадратов цифр натурального числа может быть любым натуральным числом (достаточно ограничиться рассмотрением репьюнитов).
Немногим сложнее обосновывается, что сумма цифр квадрата натурального числа может быть любым натуральным числом, сравнимым с 0, 1, 4, 7 (квадратами) по модулю 9.
А вот с суммами квадратов цифр квадратов натуральных чисел дело обстоит интереснее.
По-видимому, они могут принимать любые значения за исключением 2, 3, 4, 5, 7, 8, 9, 10, 11, 12, 14, 20.
При попытке обосновать это утверждение и возникла данная задача. Почему именно 1, 4, 9?
Во-первых, сумма число 149 приводит 13, а 1049 - к 19 (эти числа наряду с 15, 17 и 18 входят в список небольших чисел, имеющих нетривиальные требуемые представления).
А во-вторых, 1, 4, 9 (фигурирующие в условии) - это все ненулевые цифры, являющиеся квадратами, а 25 (фигурирующее в ответе) тоже квадрат. Мне показалось, что это будет уместно в задаче про сумму квадратов цифр квадратов чисел.
Сама же попытка обоснования приведенного предположения утонула в переборе переборов и к задаче не привела.

Награды

За решение задачи ММ258 участники Марафона получают следующие призовые баллы:
Анатолий Казмерчук - 8;
Олег Полубасов - 8;
Владислав Франк - 8;
Константин Шамсутдинов - 7;
Денис Овчинников - 7;
Виктор Филимоненков - 7;
Анна Букина - 7.

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

[VAL]

Влад Франк прислал мне доказательство того, что каждое число, большее 20 представляется в виде суммы квадратов цифр некоторого квадрата!

1, 6, 13, 15, 16, 17, 18, 19 представляются.
То что 2, 3, 5, 8 не имеют требуемого представления доказывается не сложно.
Таким образом, задача описания натуральных чисел, представимых в виде суммы квадратов цифр некоторого квадрата, практически решена.

Хотя, если вспомнить проблему 17 or bust...

[VAL]

Что-то ажиотажа с требованиями выложить доказательство Влада не наблюдается
Но я, все равно это сделаю.

Цитата:

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

1) Докажем, что достаточно большие числа подходят всегда. Рассмотрим числа вида $33\ldots3400\ldots00(\overline{3x})$ и возведем их в квадрат. Поскольку $33\ldots 34=\frac{10^n+2}{3}$, его квадрат можно записать в виде $\frac{10^{2n}+4\cdot 10^{n}+4}{9}=\frac{10^{2n}-1}{9}+4\cdot \frac{10^n-1}{9}+1=11\ldots155\ldots56$. Кроме того, $2\cdot 3x\cdot 333\ldots 34=1000\ldots 02\cdot 2x=\overline{2x}00\ldots \overline{4x}$. Окончательно, квадрат данного числа имеет вид $11\ldots155\ldots5600\ldots \overline{2x}00\ldots \overline{4x}00\ldots 0\overline{9x^2}$. Мы будем выбирать $x\le 100$, поэтому $9x^2$ будет не более чем пятизначным числом. Возьмем тогда число $3\ldots 34$, в котором не менее трех троек. При умножении на $3$ оно даст минимум $1002$, поэтому при умножении потом на $2x$ записи чисел $2x$ и $4x$ не будут перекрываться. Количество нулей возьмем минимум в $10$ раз больше количества троек, тогда записи чисел $11\ldots155\ldots56$, $\overline{2x}00\ldots \overline{4x}$ и $9x^2$ действительно не будут перекрываться.

В таком случае сумма квадратов цифр этого числа будет равна сумме квадратов цифр числа $\overline{2x}00\ldots \overline{4x}00\ldots 0\overline{9x^2}$ (которая не зависит от количества нулей или троек) с прибавленной суммой квадратов цифр числа $11\ldots155\ldots56$, равной $37+26k$, где $k$ - количество троек в числе $33\ldots 34$. Следующая табличка показывает, как суммами квадратов цифр числа
$\overline{2x}00\ldots \overline{4x}00\ldots 0\overline{9x^2}$ получить все остатки от деления на $26$ (остаток - подходящее $x$ - получаемая из него сумма).

0 0 0

1 87 261

2 3 106

3 52 159

4 4 134

5 23 239

6 26 162

7 67 163

8 19 268

9 32 243

10 9 244

11 59 219

12 5 38

13 73 325

14 7 118

15 48 301

16 16 94

17 24 303

18 42 356

19 35 97

20 36 176

21 2 125

22 13 100

23 1 101

24 31 258

25 41 233

Максимальная сумма в таблице равна $356$. Кроме того, мы договорились, что $k\ge 2$, поэтому можно получить любую сумму, начиная с $26\cdot 2+37+356=445$. Например, получим сумму $2000$. Поскольку $(2000-37) mod 26=13$, то следует взять $x=73$. Тогда нужно будет набрать еще сумму $2000-37-325=1638=26\cdot 63$. Следовательно нужно взять число $33\ldots 3400\ldots 0219$, в котором $63$ тройки и, например, $630$ нулей и возвести его в квадрат.

Этап 2. Теперь найдем числа, дающие маленькие суммы - меньшие $445$
[..]

Я убрал часть сообщения, посвященную поиску этих чисел.
Представление для всех чисел меньших 445 (кроме 2, 3, 4, 5, 7, 8, 9, 10, 11, 12, 14 и 20) найти легко (и давно найдены).

[vlad239]

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

Среди задач мы нашли такую - "Докажите, что число из нулей и единиц (единиц хотя бы две)" не может быть точным квадратом, стоявшую на отборе 9 класса номером 4 в 1963 году (кажется). Мы ее не смогли (очевидно, она когда-то была записана с ошибкой). Один из наших написал программу, которая нашла квадрат из 56 цифр - нулей, единиц и одной, кажется, шестерки на 12 месте.

Это я все к чему. Вопрос о том, почему нет квадрата из 10, например, единиц - вот вообще непростой...

[worm2]

$100549^2=10110101401$, ну почти

[VAL]

vlad239 в сообщении #1490032 писал(а):

Это я все к чему. Вопрос о том, почему нет квадрата из 10, например, единиц - вот вообще непростой...

Конкретно для 10 цитирую:

KK писал(а):

2111111 не годится по mod3, 2211 по mod 9, 31 не годится как угодно

А вот почему нет квадрата из 10 единиц и нулей?..
Но нету же!

[vlad239]

У меня в третьей части эти все объяснения были (кстати, про 31 там оно содержательное немного). Но фиг поймешь, почему не бывает.

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