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

[VAL]

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

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

Сергей Половинкин заметил, что если бы мальчики клеили четырехмерные параллелепипеды, среди них могло бы оказаться больше честных

А почему Сергей Половинкин никак не поощрён за это?
Ведь клеить четырёхмерные параллелепипеды - увлекательнейшее занятие. Кватернионы рулят.

Я думал над этим. Но...
Поскольку примеры, подобные приведенному, легко обнаруживаются не только без кватернионов, но даже и без компьютерного перебора (например, $1+1+9+25=36, \ 4+4+16+25=49$), решил, что поощрение будет перебором

[VAL]

========= 172 ==========

ММ172 (А-2) (5 баллов)

Доказать, что существует бесконечно много хитовых abc-троек, таких что c является степенью пятерки.

Примечание:
Тройка натуральных чисел $a,b,c$ называется хитовой abc-тройкой, если $a+b = c$, $GCD(a,b) = 1$ и $c > rad(abc)$.
Примечание к примечанию:
Пусть $n = p_1^{\alpha_1}\dots \p_k^{\alpha_k}$, тогда $rad(n) = p_1\dots p_k$

Решение

Построим требуемые хитовые тройки с помощью пифагоровых.
Положим $a_0=2, b_0=1, a_{n+1}=|a_n^2-b_n^2|, b_{n+1}=2a_nb_n$.
Непосредственно проверяется что:
$a_n$ и $b_n$ всегда взаимно просты;
$a_n^2+b_n^2=5^{2^n}$;
все тройки, начиная с $n=2$, хитовые;

Обсуждение

Достаточно легко получить и другие бесконечные множества хитовых троек, которых $c$ является степенью пятерки:
$(a=1, b=5^{4k}-1), c=5^{4k}$;
$(a=1, b=5^{6k}-1), c=5^{4k}$;
несколько более общий случай - $1, 5^{p(p-1)}-1, 5^{p(p-1)}$, где $p>5$ - простое число.
Во всех этих примерах $a$ (или, если угодно, $b$) равно единице. Составляя задачу, я планировал в формулировке условия отсечь такие тройки. Но, верный своей рассеянности, забыл. И заметил свою оплошность, лишь когда мне указал на нее Алексей Волошин (и то со второго раза). Однако к этому времени я уже получил решение, в котором $a=1$. После этого вносить изменения в условие было бы дурным тоном.
Ниже приведены решения Олега Полубасова и Анатолия Казмерчука, в которых $a$ отлично от единицы. Решение Николая Дерюгина по сути повторяет решение Анатолия, но менее строго аргументировано.
Специально для Олега Полубасова отмечу, что так полюбившийся ему термин "хитовые тройки" придуман не мной.

Многие марафонцы отметили, что пятерка не является уникальным числом: присланные ими решения позволяют строить аналогичные множества хитовых троек и для степеней других чисел.
Приведенное выше решение также допускает подобное обобщение. Например, положив $a_0=3, b_0=2$, можно получить бесконечно много хитовых троек, у которых $c$ будет степенью числа 13.

Награды

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

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

[Masik]

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

Специально для Олега Полубасова отмечу, что так полюбившийся ему термин "хитовые тройки" придуман не мной.

Извините, пожалуйста. Я сразу понял, что в условии очипятка, но не смог распознать, в какой букве.

Цитата:

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

Многие - это не все.
Если поощрения за обобщения отменили, то неплохо бы об этом этим "многим" сообщить. Они не будут стараться в следующий раз.

[VAL]

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

Цитата:

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

Многие - это не все.
Если поощрения за обобщения отменили, то неплохо бы об этом этим "многим" сообщить. Они не будут стараться в следующий раз.

Опять оправдываться?!

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

Теперь оправдания:

Во-первых, цитата из правил конкурса:

Цитата:

Субъективизм в оценивании является неизбежным злом.

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

Бывают ситуации типа ММ50. Я усиленно пытался снять ограничение "$2u<v$" в условии задачи. Но не смог найти доказательство без этого "костыля". Разумеется, получив решение для общего случая, я поощрил его дополнительными баллами (причем многими).

С ММ172 ситуация совсем иная. Задача обобщается совершенно естественно. Пятерка в условии появилась лишь оттого, что для частного случая формулировка задачи, на мой взгляд, была благозвучнее.

[Masik]

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

Субъективизм в оценивании является неизбежным злом.

Согласен: "субъективизм в оценивании является злом", а объективизм в оценивании, соответственно, является добром.
Один марафонец доказал требуемое утверждение для степени 5, другой заметил, что 5 можно заменить на 13, а третий привёл доказательство для степеней любых целых чисел, больших 1. Можно ли объективно оценить, кто из них больше обобщил задачу?

[General]

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

Однако к этому времени я уже получил решение, в котором $a=1$.

От меня, наверное? :)

Можно и без единицы:
$(a=9, b=5^{8k+6}-9, c=5^{8k+6})$ Здесь $rad(abc) < \frac{15}{16}c$

[General]

По четвёртой на всякий уточню - само число учитывается же в произведении всех своих делителей?

[VAL]

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

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

Субъективизм в оценивании является неизбежным злом.

Согласен: "субъективизм в оценивании является злом", а объективизм в оценивании ...

не достижим в принципе
... но я пытаюсь к нему стремиться, в меру моего субъективного понимания

-- 04 май 2013, 16:01 --

General в сообщении #719197 писал(а):

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

Однако к этому времени я уже получил решение, в котором $a=1$.

От меня, наверное? :)

Нет. От более "ранних пташек"

Цитата:

Можно и без единицы:
$(a=9, b=5^{8k+6}-9, c=5^{8k+6})$ Здесь $rad(abc) < \frac{15}{16}c$

Разумеется, можно и без единицы. Причем многими разными способами.

-- 04 май 2013, 16:02 --

General в сообщении #719429 писал(а):

По четвёртой на всякий уточню - само число учитывается же в произведении всех своих делителей?

Конечно! Мы же не пифагорейцы

[VAL]

========= 173 ==========

ММ173 (А-3) (5 баллов)

Последовательность состоит из натуральных чисел, представимых в виде суммы четырех своих (попарно различных) делителей, расположенных в естественном порядке. Найти стомиллиардный член этой последовательности.

Решение

В качестве "типичного представителя" приведу решение Сергея Половинкина.

Обсуждение

Задача не вызвала затруднений у большинства участников. Единственный нюанс - очередная неоднозначность в условии.
Уточнение "расположенных в естественном порядке" можно отнести как к натуральным числам (что и имелось в виду), так и к их делителям.
На этот раз обошлось: я был понят правильно. Но проблема оттачивания формулировок осталась...

Награды

За правильное решение задачи ММ173 Сергей Половинкин, Алексей Волошин, Виктор Филимоненков, Олег Полубасов, Анатолий Казмерчук, Алексей Извалов и Кирилл Веденский получают по 5 призовых баллов. Тимофей Игнатьев получает 3 призовых балла.

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

[VAL]

========= 174 ==========

ММ174 (А-4) (7 баллов)

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

Примечание:
Система счисления десятичная.

Решение

Приведу решение Алексея Извалова.
Безусловно это решение можно было бы изложить короче. Приводимый ниже текст - это, скорее, не результат, а процесс рассуждений Алексея.
Но...
Во-первых, весьма любопытно заглянуть "на кухню", где готовится решение, сопоставить чьи-то рассуждения со своими.
А во-вторых, некоторые из более коротких рассуждений привели рассуждавших к неверному ответу на вопрос пункта б)

Цитата:

Обозначим: $n$- само число, $k$- количество его делителей, $x$- количество нулей в конце этого числа.

$A$- произведение всех $k$делителей числа $n$.

Если $n=2^{\alpha_1}3^{\alpha_2}5^{\alpha_3}\dots p_m^{\alpha_m}$, то у него будет $(1+\alpha_1)(1+\alpha_2)(1+\alpha_3)\dots(1+\alpha_m)$делителей. При этом, если число $n$оканчивается $x$нулями, то наименьшая из степеней двойки и пятерки должна равняться $x$(другая степень может и превосходить $x$).
($\min(\alpha_1, \alpha_3)=x, \max(\alpha_1, \alpha_3)\geq x$)

Если число $n$имеет $k$делителей и $k$- чётно, то все делители числа $n$разбиваются на пары, дающие $n$в произведении. Тогда число $A$, произведение всех $k$делителей числа $n$будет равно $n^{\frac{k}{2}}$И если число $n$оканчивается на $x$нулей, то у данного произведения будет в конце $\frac{xk}{2}$нулей.

Если же $n$- полный квадрат и у него нечётное количество делителей, произведение всех его делителей будет равно $n^{\left[\frac{k}{2}\right]}\sqrt{n}$, т.е., опять-таки $n^{\frac{k}{2}}$имеющее $\frac{xk}{2}$нулей в конце.

Поскольку как минимум один из множителей (2 или 5) входит в разложение числа $n$в степени $x$, а другой - как минимум в степени $x$, то $k|(x+1), k\geq(1+x)^2$

Если $A$оканчивается ровно 2013 нулями, то
$xk=4026=2\cdot 3\cdot 11\cdot 61$

Условию, связывающему $k$и $x$удовлетворяют следующие пары:
$x=1, k=2\cdot 3\cdot 11\cdot 61$
$x=2, k=3\cdot 11\cdot 61$

В первом случае минимальным будет число $n=2^{60}3^{10}5^{1}7^2$
Во втором: $n=2^{60}3^{10}5^{2}$

Второй число меньше, так что оно и будет ответом на вопрос а)
Ответ: $2^{60}3^{10}5^{2}$


$xk \geq 4026$
Рассмотрим сначала число вида $n=2^x 5^x$. $k=(1+x)^2$
$x(1+x)^2 \geq 4026$
$x\geq16$
$n=10 000 000 000 000 000$

Можем ли мы уменьшить искомое число? Число делителей удвоится, если $n$умножить на 3.
Тогда
$x(1+x)^2 \geq 2013$
$x\geq12$
$n=3 000 000 000 000$

Удвоим $k$снова, умножив $n$на 7.
$x(1+x)^2 \geq 1007$
$x\geq10$
$n=210 000 000 000$

Удвоим $k$снова, умножив $n$на 9 (увеличение выходит меньше, чем если бы умножить на 11).
$x(1+x)^2 \geq 504$
$x\geq8$
$n=18 900 000 000$

Удваивать $k$, домножая на простые числа, будет выгодно, пока это позволит избавиться от двух нулей, а число. на которое домножаем, будет меньше 100.
Умножаем на 11:
$x(1+x)^2 \geq 252$
$x\geq6$
$n= 2 079 000 000$

Вот умножение на 13 приводит к неравенству
$x(1+x)^2 \geq 126$
$x\geq5$
$n= 2 702 700 000$и число увеличилось.

Но необходим более систематичный подход для поиска минимального $n$. Который, к тому же, мог бы учитывать неравенство степеней двойки и пятёрки в числе $n$.
Понятно, что если двойка и пятёрка входят в разложение числа $n$не в равных степенях, то количество делителей не изменится, само число будет меньше, если степень двойки будет больше степени пятёрки.


Пусть $n=2^{x+d}5^x B$, где $d\geq0$, в разложение числа $B$не входят ни 2, ни 5, и число $B$имеет c делителей.

Тогда $k = (x+d+1)(x+1)c$

А число $A$будет оканчиваться $x(x+d+1)(x+1)c$нулями.

$x(x+d+1)(x+1)c \geq 4026$
$c\leq\frac{4026}{x^3+(2+d)x^2+(1+d)x}$

Для облегчения перебора, предварительно я построил таблицу минимальных чисел, не делящихся на 2 или 5 и имеющих ровно с делителей. (если числа нет в таблице, то оно больше миллиона. Как правило, это для простых c, когда минимальное $B = 3^{c-1}$или для $c=pq, p<q, B=3^q 7^p$)
2 3
3 9
4 21
5 81
6 63
7 729
8 189
9 441
10 567
11 59049
12 693
13 531441
14 5103
15 3969
16 2079
18 4851
20 6237
21 35721
22 413343
24 9009
25 194481
27 53361
28 56133
30 43659
32 27027
36 63063
40 81081
42 392931
45 480249
48 153153
54 693693
56 729729
60 567567

Для $х=7$,
$c\geq\frac{4026}{448+56d}$
Составим таблицу:
d c
0 9
1 8
2 8
3 7
.....
Увеличение $d$удваивает число, так что выгода в его увеличении будет лишь тогда, когда множитель В удаётся уменьшить более, чем вдвое.
Минимальное значение $n$будет достигаться при $d=1, B = 189$, $n=2^8 5^7\cdot 189=3 780 000 000$

При $х=6$
$c\geq\frac{4026}{294+42d}$
Составим таблицу:
d c
0 14
1 12
2 11
3 10
4 9
5 8
.....

Минимум будет при $d=1, B=693$, $n=2^7 5^6 \cdot 693=1 386 000 000$

При $х=5$
$c\geq\frac{4026}{170+30d}$
Составим таблицу:
d c
0 24
1 21
2 18
3 16
.....
Минимум будет при d=0, B=9009, $n=2^5 5^5 \cdot 9009 = 900 900 000$

При $x=4$
$c\geq\frac{4026}{100+20d}$
Составим таблицу:
d c
0 41
1 34
2 29
3 26
4 23
.....
Минимум будет при $d=2, B=27027$(в таблице указано минимальное значение $c$, но для $с=32$значение $B$меньше, чем для $с=29$), $n=2^6 5^4 \cdot 27027= 1 081 080 000$

Дальнейшее уменьшение числа нулей в конце числа $x$приведёт к ещё большему росту числа $B$, который превысит выгоду от отказа от лишних множителей $2\cdot 5$.

На всякий случай я провёл перебор (со всеми оптимизациями) и получил, что действительно, наименьшее число, произведение всех делителей которого оканчивается не менее чем 2013ю нулями равно 900 900 000. Следующим будет 1 081 080 000

Ответ:
а) $2^{60}3^{10}5^{2}$
б) $900 900 000$

Обсуждение

Сергей Половинкин нашел в Интернете задачу (предлагаемую в качестве образца задачи С6 ЕГЭ), где требовалось найти намиеньше натуральное число, произведение делителей которого заканчивается на 399 нулей.
Каюсь, одиннадцатиклассники, у которых я веду факультатив, приносили мне эту задачу (только не уверен, что там именно 399 нулей было). И именно она легла в основу ММ174.
Единственное существенное изменение - добавление пункта б), на мой взгляд, гораздо более содержательного, чем а). В частности, у меня ушло на второй пункт раз в 10 больше времени, чем на первый.

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

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

Награды

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

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

[Masik]

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

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

Золотые слова!
А про ограничение перебора буду иметь в виду.

[General]

Очень рад, что выбрали моё решение. Да-да, я специально описывал, как к подбирался к ответу. Ещё со школьных олимпиадных времён помню, как при разборах задач любят слово "очевидно" :)

[VAL]

В соответствии с пожеланиям некоторых участников Марафона прием решений ММ175 продлен до 26.05.13

[VAL]

========= 175 ==========

ММ175 (А-5) (8 баллов)

Натуральное число n назовем g-2-числом, если число 2n, записанное в системе счисления c основанием g получается из n перестановкой цифр. Какие основания встречаются (в натуральном ряду) чаще: те, для которых существуют трехзначные g-2-числа, или те, в которых нет трехзначных g-2-чисел?

Примечание:
Расcматриваются позиционные системы счисления с натуральными основаниями $g>1$.

Решение

Приведу решение Олега Полубасова.
В первой части оно по сути не отличается от других правильных решений. Интерес представляет вторая часть, обобщающая задачу.

Обсуждение

Задача ММ175 допускает обобщения по разным направлениям. Наиболее естественны два пути:
изучение g-2-чисел произвольной значности;
Изучение g-k-чисел для произвольного натурального k.

Конечно же я думал над задачами, сформулированными в последнем пункте решения Олега.
И задал бы вместо ММ175..., если бы решил.
Сначала у меня была идея закрыть все классы вычетов по какому-нибудь модулю. Так, например, по модулю 9 мне довольно быстро удалось закрыть почти все классы.
В самом деле, классы двойки, пятерки и восьмерки закрываются уже двузначными числами: число записанное цифрами $m$ и $2m+1$ будет g-2-числом при $g=3m+2$.
Основания, кратные трем (т.е. классы нуля, тройки и шестерки), закрываются четырехзначными числами: $m(m-1)(2m-1)(2m)_g$, где $g=3m$.
При $g=9m+4$ g-2-числом будет $m(2m)(5m+2)(4m+1)(8m+3)(7m+3)_g$.
При $g=9m+7$ g-2-числом будет $(2m+1)(8m+6)m(5m+3)(7m+5)(4m+3)_g$.
Оставался только класс единицы. Но его закрыть так и не удалось.
Я попробовал сменить модуль (разумеется, выбирая модули, являющиеся делителями чисел $2^s-1$ с небольшими $s$. Однако, класс единицы не удалось закрыть ни по одному из модулей.
Говоря о конкретных g, отмечу что в первой сотне осталось непокоренным единственное основание $g=91$ (разумеется, $g=2$ не в счет), коварным образом сравнимое с единицей одновременно по модулям 2, 5 и 9.

Алексей Волошин подсчитал, что доля оснований, для которых существуют трехзначные g-3-числа равна $\frac{49}{104}$. Этот вывод совпал с результатами Сергея Половинкина.
Сергей Половинкин не ограничился g-3-числами и оценил долю оснований для которых существуют трехзначные g-k-числа для достаточно многих $k$ (для одних теоретически, для других статистически, компьютерным перебором). Оказалось, что чаще всего встречаются основания, в которых есть трехзначные g-4-числа (частота - 0.75). Второе место занимает $k$, равное 7.

Отмечу, числа, образованные цифрами от единицы до "девятки" (т.е. $g-1$) в порядке возрастания являются g-2-числами для всех четных оснований $g>2$. Эти же числа будут одновременно g-k-числами для всех $k$, взаимно простых с $g$ и меньших $g-1$.

Награды

Дополнительные баллы ставились за всевозможные обобщения, углубления и дополнения, к которым располагает ММ175. Я не стал карать тех участников, которые утверждали что "оснований, для которых существуют трехзначные g-2-числа больше", посчитав это выражение фигурой речи, а не математическим утверждением.
За решение задачи ММ175 Олег Полубасов получает 14 призовых баллов, Сергей Половинкин - 12 призовых баллов, Алексей Волошин и Николай Дерюгин - по 9 призовых баллов, Виктор Филимоненков, Алексей Извалов, Анатолий Казмерчук, Евгений Гужавин и Кирилл Веденский - по 8 призовых баллов.

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

-- 27 май 2013, 00:21 --

======================================
Поначалу тематический конкурс складывался по сценарию, аналогичному тому, по которому развивается проходящий в настоящее время этап Гран-при по шахматам в Салоникам: в лидерах шла большая часть участников.
Однако, задача ММ175 оправдала мои ожидания и позволила выявить лучших из лучших и расставить по местам призеров конкурса, коих я и поздравляю!

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

[VAL]

========= 176 ==========

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

Сколько точек экстремума, не являющихся точками разрыва, имеет функция $f(x) = \{x\}+\{x^2\}+\{x\}^2$ ?

Примечание:
$\{x\}$ - дробная часть числа $x$.

Решение

Приведу решения Олега Полубасова, рассмотревшего ряд аналогичных задач, и Алексея Волошина (а то у Олега чертежа нет).

Обсуждение

Другие решения (если не считать неправильных ) по сути аналогичны приведенным.
Замечу (для тех, кого это касается), что у команды plot в maple есть опция discont. Если придать ей значение true, то на графике не будет вертикальных линий в точках разрыва функции (ну или почти не будет ).

Награды

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

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