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

[VAL]

========= 153 ==========

ММ153 (ТГ-2) (4 балла)

Пусть n, m и k означают соответственно число вершин, ребер и связных компонент графа.
Какое наименьшее количество изолированных вершин может иметь граф, для которого выполняется соотношение $11k = 10n = 8m$?

Решение

Очевидно, что условие $11k = 10n = 8m$ равносильно следующему:
$m = 55t, n = 44t, k = 40t$, для некоторого натурального $t$.

Широко известно и легко доказывается, что при фиксированных $m$ и $k$ наибольшее число ребер достигается в графе, в котором все ребра сосредоточены в одной связной компоненте (если это не так, число ребер легко увеличить, перебросив вершину из одной компоненты в другую, имеющую не меньше вершин, чем исходная).
Отсюда сразу следует, что $t>6$ т.к. при меньших $t$ не удается "разместить" в графе $55t$ ребер.
При $t=7$ это уже возможно. Имеем $m = 385, n = 308, k = 280$. Если 279 компонент сделать одновершинными, то на 280-ю придется 29 вершин. Поскольку $C_{29}^2=406 > 385$, существует граф с 279-ю изолированными вершинами, удовлетворяющий условиям задачи.
Поскольку $C_{28}^2+C_2^2 = 379 < 385$, уменьшить число изолированных вершин при $t = 7$ нельзя.

Остается показать, что при бОльших $t$ изолированных вершин будет больше.
Из соотношения $11k = 10n$ вытекает, что изолированные вершины составляют не менее 90% от общего числа компонент. 90% достигается в случае, когда остальные компоненты имеют по две вершины (при нашем количестве ребер это, конечно же невозможно, так что изолированных вершин будет даже более 90%). Но уже при $t = 8$ 90% от $k$ будет больше чем 279.

Ответ: 279.

Обсуждение

Составляя задачу, я планировал ответ 278. Еще одна компонента планировалась двухвершинной, а самая большая должна была быть 28-вершинной. Но уже после публикации задачи неожиданно выяснилось, что $C_{28}^2$ не равно 384

Награды

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

Эстетическая оценка - 4.5 балла

Разбор задачи ММ153 подготовил Владимир Лецко

[VAL]

========= 152 ==========

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

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

Решение

Приведу решение Олега Полубасова.

Для любого разбиения прямоугольника на k квадратов можно выписать систему из k-1 однородных линейных уравнений, связывающих размеры квадратов, поэтому размеры квадратов относятся как рациональные числа.
План таков: найти все решения уравнения $\sum_{i=1}^{10}x_i^2=y^2 \ (1)$ в натуральных числах, где $x_i$ взаимно просты в совокупности. Затем отбросить наборы, из которых не удаётся сложить квадрат.
Перебор кажется необозримым, но Г. Дьюдени в задаче "Стёганое одеяло миссис Перкинс" предположил (а в 1964 г. Дж. Конуэй в статье с одноимённым названием доказал), что для 10 квадратов $y$ не может превышать 9.
С другой стороны, ясно, что $y\ge4$, поэтому количество перебираемых вариантов оказывается совсем небольшим.
Дополнительным отсечением служит тот очевидный факт, что сумма размеров двух наибольших квадратов не должна превышать размера разбиваемого квадрата, то есть $x_i + x_j \le y$.
Удобнее оперировать переменными $z_i = (x_i^2 - 1), \ w = y^2 - 10$, тогда уравнение (1) перепишется как $w=\sum_{i=1}^m z_i \ (2)$ , где $m \le 10, \ z_i \in \{ 3, 8, 15, 24, 35, 48, 63 \}, \ w \in \{6, 15, 26, 39, 54, 71\}.$

Решения последнего уравнения сведены в таблицу.
Вторая колонка - решения уравнения (2); третья колонка - взаимно простые решения уравнения (1), удовлетворяющие условию $x_i + x_j \le y$; четвертая - номера рисунков, для решений, из которых можно сложить квадрат.
\begin{array}{|l|l|l|l|} \hline 1. & 6=2\cdot 3 & 2\cdot2^2+8\cdot1^2 = 4^2 & \mbox{Рис.} \ 1 \\ \hline 2. & 15=15 & 1\cdot4^2+9\cdot1^2 = 5^2 & \mbox{Рис.} \ 2 \\ \hline 3. & 15=5\cdot 3 & 5\cdot2^2+5\cdot1^2 = 5^2 & \\ \hline 4. & 26=15+8+3 & & \\ \hline 5. & 26=8+6\cdot 3 & 1\cdot3^2+6\cdot2^2+3\cdot1^2 = 6^2 & \\ \hline 6. & 39=24+15 & & \\ \hline 7. & 39=24+5\cdot 3 & 1\cdot5^2+5\cdot2^2+4\cdot1^2 = 7^2 & \mbox{Рис.} 3 \\ \hline 8. & 39=2\cdot15+3\cdot 3 & & \\ \hline 9. & 39=15+3\cdot 8 & 1\cdot4^2+3\cdot3^2+6\cdot1^2 = 7^2 & \mbox{Рис.} 4 \\ \hline 10. & 39=15+8\cdot 3 & 1\cdot4^2+8\cdot2^2+1\cdot1^2 = 7^2 & \\ \hline 11. & 39=3\cdot8+5\cdot3 & 3\cdot3^2+5\cdot2^2+2\cdot1^2 = 7^2 & \\ \hline 12. & 54=48+2\cdot3 & & \\ \hline 13. & 54=35+2\cdot8+3 & & \\ \hline 14. & 54=2\cdot24+2\cdot3 & & \\ \hline 15. & 54=24+2\cdot15 & & \\ \hline 16. & 54=24+3\cdot8+2\cdot3 & 1\cdot5^2+3\cdot2^2+2\cdot2^2+4\cdot1^2 = 8^2 & \mbox{Рис.} \ 5 \\ \hline 17. & 54=3\cdot15+3\cdot3 & 3\cdot4^2+3\cdot2^2+4\cdot1^2 = 8^2 & \mbox{Рис.} \ 6 \\ \hline 18. & 54=2\cdot15+3\cdot8 & 2\cdot4^2+3\cdot3^2+5\cdot1^2 = 8^2 & \\ \hline 19. & 54=2\cdot15+8\cdot3 & & \\ \hline 20. & 54=6\cdot8+2\cdot3 & 6\cdot3^2+2\cdot2^2+2\cdot1^2 = 8^2 & \\ \hline 21. & 71=63+8 & & \\ \hline 22. & 71=48+15+8 & & \\ \hline 23. & 71=48+8+5\cdot3 & & \\ \hline 24. & 71=35+24+4\cdot3 & & \\ \hline 25. & 71=2\cdot24+15+8 & & \\ \hline 26. & 71=2\cdot24+8+5\cdot3 & & \\ \hline 27. & 71=24+2\cdot15+8+3\cdot3 & 1\cdot5^2+2\cdot4^2+1\cdot3^2+3\cdot2^2+3\cdot1^2 = 9^2 & \mbox{Рис.} \ 7 \\ \hline 28. & 71=24+15+4\cdot8 & 1\cdot5^2+1\cdot4^2+4\cdot3^2+4\cdot1^2 = 9^2 & \\ \hline 29. & 71=24+4\cdot8+5\cdot3 & 1\cdot5^2+4\cdot3^2+5\cdot2^2 = 9^2 & \\ \hline 30. & 71=4\cdot15+8+3 & 4\cdot4^2+1\cdot3^2+1\cdot2^2+4\cdot1^2 = 9^2 & \\ \hline 31. & 71=3\cdot15+8+6\cdot3 & 3\cdot4^2+1\cdot3^2+6\cdot2^2 = 9^2 & \\ \hline 32. & 71=2\cdot15+4\cdot8+3\cdot3 & 2\cdot4^2+4\cdot3^2+3\cdot2^2+1\cdot1^2 = 9^2 & \\ \hline 33. & 71=15+7\cdot8 & 1\cdot4^2+7\cdot3^2+2\cdot1^2 = 9^2 & \\ \hline \end{array}















Ответ: 7 способов.

Обсуждение

Назначая цену задачу, я планировал давать 6 призовых баллов тем участникам, которые решат задачу так же, как сделал это я. То есть найдут все 7 разбиений, но не получат строгого доказательства полноты решения.
За наличие такого доказательства или нахождение других разбиений (в эту альтернативу я не верил, но чем черт не шутит?) планировались дополнительные баллы.
На чем базировалась моя уверенность в отсутствии других разбиений? Так же, как и многие участники, я перебирал разбиении я квадрата $n\times n$ на квадраты со взаимно простыми в совокупности длинами сторон.
Осуществляя перебор для последовательных n, я пришел к твердому убеждению (но не доказательству, что при больших n (я добрался до 15) минимальное число квадратов заведомо больше 10.

На Wolfram'е для небольших n приведены минимальные количества квадратов в разбиении квадрата $n\times n$.
Сначала эта зависимость вполне монотонна. Однако не все так просто. Квадрат $40\times40$ нельзя порезать менее чем на 16 квадратов со взаимно простыми сторонами. А квадрат $41\times41$ можно разрезать на 15 квадратов.
Вот таблица, сопоставляющая числу квадратов в разрезании те n, для которых это число минимально.

\begin{array}{|l|l|} \hline s(n) & n \\ \hline 1 & 1 \\ \hline 4 & 2 \\ \hline 6 & 3 \\ \hline 7 & 4 \\ \hline 8 & 5 \\ \hline 9 & 6,7 \\ \hline 10 & 8,9 \\ \hline 11 & 11-13 \\ \hline 12 & 14-17 \\ \hline 13 & 18-23 \\ \hline 14 & 24-29 \\ \hline 15 & 30-39,41 \\ \hline 16 & 40,42-53 \\ \hline 17 & 54-70 \\ \hline 18 & 71-91 \\ \hline 19 & 92-120,122,126 \\ \hline 20 & 121,123-125,127-154,157,158 \\ \hline \end{array}

Сергей Половинкин составил таблицу, в которой представлены количества способов разрезания квадрата на k квадратов, для всех k, не превышающих 12.
$\begin{array}{|c|c|} \hline k & f(k) \\ \hline 1 & 1 \\ 2 & 0 \\ 3 & 0 \\ 4 & 1 \\ 5 & 0 \\ 6 & 1 \\ 7 & 1 \\ 8 & 2 \\ 9 & 4 \\ 10 & 7 \\ 11 & 16 \\ 12 & 30 \\ \hline \end{array}$
Интересно, что начиная с $k=7$ идет почти точное удвоение числа разбиений на каждом шаге. Между прочим, данная последовательность отсутствует в OEIS. Полагаю, следует восполнить этот пробел.

Готовя эту задачу прошлым летом, я оптимистично начинал со случая $k=13$. Добравшись до разбиений квадрата $17\times17$ и получив несколько десятков разбиений квадрата на 13 квадратов, я понял, что погорячился и переключился на случай $k=11$. Его я просчитал до конца (если чего-то не прозевал). Но, к сожалению, не могу найти летнюю тетрадку, чтобы свериться с результатами Сергея.

Наиболее знаменитой задачей, связанной с разрезанием квадрата, является задача о разрезании квадрата на попарно различные квадраты. В свое время Н.Н.Лузин полагал, что этого сделать нельзя. Однако вскоре было найдено решение. Основная идея - сопоставить каждому разрезанию прямоугольника на квадраты некую схему электрической цепи. Подробнее об этом можно почитать, например, в "Кванте" №5 за 2010 год (там этот вопрос рассматривается сразу в двух статьях).
Разумеется, напрашивается свести к рассмотрению электрических цепей и нашу задачу. Сам я, изучая такой подход пришел к выводу, что "хрен редьки не слаще". Однако Олег Полубасов и Анатолий Казмерчук оказались более настойчивы преуспели в возникающем переборе уже не квадратов, но цепей.

Награды

За правильное решение задачи ММ152 и обоснование его полноты Олег Полубасов и Анатолий Казмерчук получают по 9 призовых баллов. За правильное решение и любопытные (хотя не абсолютно строгие) соображения по обоснованию полноты решения Николай Дерюгин получает 7 призовых баллов. Столько же баллов получает Сергей Половинкин за верное решение и рассмотрение случаев разрезания на другое число квадратов. За верное решение Виктор Филимоненков получает 6 призовых баллов. Алексей Волошин получает 4 призовых балла. Александр Князев и Елизавета Евдокимова - по 2 призовых балла, Екатерина Шарпанова - 1 призовой балл.

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

Разбор задачи ММ152 подготовил Владимир Лецко

[VAL]

========= 154 ==========

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

Математик D предложил математикам A, B и C следующую задачку:

Я загадал два натуральных числа (не обязательно различных), каждое из которых не превосходит 20.
Сейчас я сообщу A сумму квадратов, B - произведение, а C - сумму этих чисел, а вы должны будете отгадать эти числа.
Узнав предназначенную информацию математики разговорились.
A: Я не знаю этих чисел.
B: Я тоже их не знаю.
C: И я не знаю.
B: Тогда я их знаю.
C: А я не знаю.
А: Зато я узнал их еще до того, как ты в первый раз это сказал.

Что это за числа?

Решение

Из первой реплики А следует, что известное ему число раскладывается в сумму квадратов двух чисел, не превосходящих 20, более чем одним способом. Таких чисел 25, причем два числа 325 и 425 имеют по три представления. Таким образом, после первой реплики А на подозрении 52 пары чисел.
Дальнейший ход решения ясен из таблицы (которую я позаимствовал у Дмитрия Пашуткина):



Комметарии к таблице, на мой взгляд излишни.

Ответ: 4 и 7.

Обсуждение

В свое время я был очарован задачкой, при решении которой надо было ставить себя на место персонажей, обладающих информацией, не данной в условии явно. С тех пор я решил и составил немало подобных задач. К сожалению, тем, кто знаком с их логикой, радость открытия уже не светит. Ее заменяет техника перебора и отсечения. Но я постоянно сталкиваюсь с массой людей, для которых подобные задачки в новинку. Им-то, в первую очередь, и адресована ММ154.

Награды

За правильное решение задачи ММ154 Олег Полубасов, Сергей Половинкин, Дмитрий Пашуткин, Евгений Машеорв и Анатолий Казмерчук получают по 5 призовых баллов. Виктор Филимоненков (он потерял одну пару пар с равными произведениями, но это загадочным образом не повлияло на ответ) получает 4 призовых балла, а Александр Князев - 1 призовой балл.

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

Разбор задачи ММ154 подготовил Владимир Лецко

-- 18 фев 2012, 17:21 --

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

Сергей Половинкин нашел пропущенный ранее способ разрезать квадрат на 11 квадратов. Теперь табличка выглядит так:

$$\begin{array}{|c|c|} \hline k & f(k) \\ \hline 1 & 1 \\ 2 & 0 \\ 3 & 0 \\ 4 & 1 \\ 5 & 0 \\ 6 & 1 \\ 7 & 1 \\ 8 & 2 \\ 9 & 4 \\ 10 & 7 \\ 11 & 16 \\ 12 & 30 \\ \hline \end{array}$$

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

[VAL]

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

Текущее положение участников
в XVI туре Математического марафона
\begin{tabular}{|l|l|r|r|r|r|r|r|r|r|} \hline №& Участники& 151 & 152 &153 & 154 &\Sigma \\ \hline 1.& Олег Полубасов & 5 & 9 & 4 & 5 & 23 \\ \hline 2.& Сергей Половинкин & 4 & 7 & 4 & 5 & 20 \\ \hline 3.& Виктор Филимоненков & 4 & 6 & 4 & 4 & 18 \\ \hline 4.& Анатолий Казмерчук & - & 9 & 2 & 5 & 16 \\ \hline 5.& Алексей Волошин & 4 & 4 & 2 & 5 & 15 \\ \hline 5.& Николай Дерюгин & 4 & 7 & 4 & - & 15 \\ \hline 7.& Дмитрий Пашуткин & - & - & 4 & 5 & 9 \\ \hline 8.& Александр Князев & 1 & 2 & 3 & 1 & 7 \\ \hline 9.& Евгений Машеров & - & - & - & 5 & 5 \\ \hline 10.& Евгений Гужавин & 4 & - & - & - & 4 \\ \hline 11.& Елизавета Евдокимова & - & 2 & - & - & 2 \\ \hline 12.& Екатерина Шарпанова & - & 1 & - & - & 1 \\ \hline \end{tabular}

[Masik]

О! Нам составил компанию санитар Женя. Превед!

[VAL]

========= 155 ==========

ММ155 (4 балла)

Существует ли цепочка из 1000 последовательных натуральных чисел, каждое из которых имеет не менее 1000 натуральных делителей?

Решение

Приведу решение Алексея Волошина:

Возьмём 1000000 различных простых чисел $p_1, p_2, \dots, p_{1000000}$, больших 1000. По китайской теореме об остатках найдётся такое $n$, которое при делении на $p_i$ дает остаток $p_i- \left \lfloor \frac{i-1}{1000} \right \rfloor$.
Тогда $n$ делится на $p_1,p_2, \dots, p_{1000}$, $n+1$ делится на $p_{1001},p_{1002}, \dots, p_{2000}$ и т.д.

Обсуждение

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

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

Цитата:

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

Награды

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

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

Разбор задачи ММ155 подготовил Владимир Лецко

-- 25 фев 2012, 11:27 --

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

Текущее положение участников
в XVI туре Математического марафона
\begin{tabular}{|l|l|r|r|r|r|r|r|r|r|} \hline №& Участники& 151 & 152 &153 & 154 & 155 &\Sigma \\ \hline 1.& Олег Полубасов & 5 & 9 & 4 & 5 & 4 & 27 \\ \hline 2.& Сергей Половинкин & 4 & 7 & 4 & 5 & 4 & 24 \\ \hline 3.& Виктор Филимоненков & 4 & 6 & 4 & 4 & 4 & 22 \\ \hline 4.& Анатолий Казмерчук & - & 9 & 2 & 5 & 4 & 20 \\ \hline 5.& Алексей Волошин & 4 & 4 & 2 & 5 & 4 & 19 \\ \hline 5.& Николай Дерюгин & 4 & 7 & 4 & - & 4 & 19 \\ \hline 7.& Дмитрий Пашуткин & - & - & 4 & 5 & 4 & 13 \\ \hline 8.& Александр Князев & 1 & 2 & 3 & 1 & - & 7 \\ \hline 9.& Евгений Машеров & - & - & - & 5 & -& 5 \\ \hline 10.& Евгений Гужавин & 4 & - & - & - & - & 4 \\ \hline 11.& Елизавета Евдокимова & - & 2 & - & - & 0 & 2 \\ \hline 12.& Екатерина Шарпанова & - & 1 & - & - & - & 1 \\ \hline \end{tabular}

[VAL]

========= 156 ==========

ММ156 (ТГ-3) (5 баллов)

На занятии по дискретной математике на доске был изображен некоторый граф.
Вася Пупкин записал в тетрадку количество вершин и ребер каждой связной компоненты графа, а также степени вершин самой большой (по количеству вершин) компоненты.
Но само изображение графа он срисовать забыл. Кроме того, он забыл, за какую именно из вышеперечисленных характеристик отвечает каждое из записанных чисел.
Сможет ли Вася решить домашнее задание "Найти диаметры каждой связной компоненты", если у него в тетрадке записаны числа: 1, 2, 2, 3, 3, 3, 4, 4, 4, 5, 6, 9?

Решение

Приведу решение Евгения Гужавина:

Из анализа чисел последовательности видно, что:

1. В самой большой компоненте связности (КС) чётное число вершин, т.к. количество чисел в последовательности чётно.
2. Число 9 может обозначать только число рёбер одной из КС. Действительно, если это количество вершин КС, то количество рёбер в этой КС должно быть не менее 8, а если это степень одной из вершин самой большой КС, то количество вершин в этой КС должно быть не менее 10, но таких чисел в заданной последовательности нет.
3. КС с 9-ю рёбрами должна иметь не менее 5-ти вершин, т.к. для полного графа $(3\cdot 4)/2<9<(4\cdot 5)/2$. Из пункта 1 следует, что это число 6.

Теперь известно, что граф имеет три КС и в большей из них шесть вершин и девять рёбер. Для того, чтобы найти пары чисел (количество вершин, количество рёбер) оставшихся КС, используем тот факт, что количество рёбер графа равно полусумме степеней вершин. В нашем случае сумма оставшихся десяти чисел последовательности равна 31, значит нужно проверить все группы по четыре числа, дающие в сумме 13:
$(1,4,4,4)$ не подходит - четыре вершины и одно ребро;
$(2,3,4,4)$ подходит - $(3,2),(4,4)$;
$(2,2,4,5)$ не подходит - две вершины и два ребра;
$(1,3,4,5)$ не подходит - три вершины и одно ребро;
$(2,3,3,5)$ не подходит - пять вершин и три ребра;
$(3,3,3,4)$ подходит - $(3,3),(4,3)$.

В итоге имеем два варианта разделения чисел заданной последовательности: $\{(3,2),(4,4),(6,9),(1,2,3,3,4,5)\}$ и $\{(3,3),(4,3),(6,9),(1,2,2,4,4,5)\}$.
Покажем, что для второго варианта невозможно построить граф. Для этого рассмотрим самую большую КС. Видно, что шестая (по порядку) вершина смежна всем остальным, т.к. её степень равна пяти. Удалим все рёбра инцидентные этой вершине, получим следующую последовательность степеней вершин нового графа $(0,1,1,3,3,0)$. Повторим проделанное для пятой (по порядку) вершины, получим последовательность $(0,0,0,2,0,0)$ - петля в четвёртой вершине, что невозможно.
Проверим первый вариант: $(1,2,3,3,4,5)\to (0,1,2,2,3,0)\to (0,0,1,1,0,0)$.
Теперь можно ответить на поставленный в задаче вопрос - не сложно увидеть, что диаметр каждой из трёх КС равен двум.

Обсуждение

Легко убедиться, кто трехвершинная и шестивершинная компоненты определены условиями задачи однозначно, а для четырехвершинной существуют два варианта. Некоторые участники остановились на этом моменте, другие ограничились констатацией факта, что диаметр каждой компоненты определен однозначно.
В связи с этим я испытывал затруднения, оценивая решение, в котором утверждалось, что существует более одного графа, со степенями вершин 1, 2, 3, 3. 4, 5. С одной стороны, это не так, а с другой - никак не влияет на ответ. Я думаю наиболее проницательные читатели догадаются, стал ли снижать оценку за этот промах.

Удовлетворю любопытство одного из участников Марафона: расскажу, как я сочинял задачу ММ156.
Каюсь, я делал это совершенно неправильно. Мне просто было интересно, что получится при таком подходе.
Сначала я сочинил текст условия. Но без вопроса, что надо найти. А затем написал "от фонаря", не имея в виду ни одного конкретного графа, 12 чисел (даже то, что их именно 12 выяснилось позже, когда я их пересчитал). Затем провел анализ, наподобие тех, что проводили участники, решившие задачу.
Я полагал, что для получения содержательной задачи придется сделать несколько попыток. Однако первый же набор чисел привел к ситуации, когда граф определен неоднозначно, но количество компонент и их диаметры можно восстановить.

Награды

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

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

Разбор задачи ММ156 подготовил Владимир Лецко

[VAL]

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

Текущее положение участников
в XVI туре Математического марафона
\begin{tabular}{|l|l|r|r|r|r|r|r|r|r|r|} \hline №& Участники& 151 & 152 &153 & 154 & 155 & 156 &\Sigma \\ \hline 1.& Олег Полубасов & 5 & 9 & 4 & 5 & 4 & 5 & 32 \\ \hline 2.& Сергей Половинкин & 4 & 7 & 4 & 5 & 4 & 5 & 29 \\ \hline 3.& Виктор Филимоненков & 4 & 6 & 4 & 4 & 4 & 5 & 27 \\ \hline 4.& Анатолий Казмерчук & - & 9 & 2 & 5 & 4 & 5 & 25 \\ \hline 5.& Алексей Волошин & 4 & 4 & 2 & 5 & 4 & 5 & 24 \\ \hline 5.& Николай Дерюгин & 4 & 7 & 4 & - & 4 & 5 & 24 \\ \hline 7.& Дмитрий Пашуткин & - & - & 4 & 5 & 4 & 5 & 18 \\ \hline 8.& Евгений Машеров & - & - & - & 5 & -& 5 & 10 \\ \hline 9.& Евгений Гужавин & 4 & - & - & - & - & 5 & 9 \\ \hline 10.& Александр Князев & 1 & 2 & 3 & 1 & - & - & 7 \\ \hline 11.& Елизавета Евдокимова & - & 2 & - & - & - & - & 2 \\ \hline 12.& Екатерина Шарпанова & - & 1 & - & - & - & - & 1 \\ \hline \end{tabular}

[VAL]

========= 157 ==========

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

В треугольнике ABC, отличном от прямоугольного, проведены высоты AE и CF, пересекающиеся в точке H. Через точки A и H проведены перпендикуляры к EF, пересекающие прямую BC в точках K и L.
Найти KL, если радиус окружности, вписанной в треугольник ABC равен r, а BC = a.

Решение

Приведу решение Алексея Волошина:

Имеют место следующие равенства:

$$\frac{KL}{KE}=\frac{AH}{AE} \ (1)$$

$$\frac{KE}{AE}=\frac{CF}{AF} \ (2)$$

$$\frac{AH}{AF}=\frac{AB}{AE} \ (3)$$

$$CF\cdotAB=AE\cdotBC\ (4)$$

Первое тождество следует из параллельности прямых AK и HL.
Третьё - из подобия прямоугольных треугольников AFH и AEB по трем углам.
В четвёртом тождестве слева и справа записана удвоенная площадь треугольника ABC.
Для доказательства второго тождества нужно заметить, что точки E и F лежат на окружности с диаметром AC. Далее простым перебором вариантов доказываем, что $\angle ACF=\angle AKE$:
Если треугольник $ABC$ остроугольный, то $\angle ACF=\angle AEF=\frac{\pi}2-\angle FEK=\angle AKE$. Если же один из углов тупой, то $\angle ACF = \frac{\pi}2-\angle CAF =\frac{\pi}2-\angle CEF = \angle AKE$ (все три варианта нужно рассматривать отдельно, но цепочка равенств будет одинаковой).
Следовательно, треугольники $KEA$ и $CFA$ подобны по трем углам, а значит второе равенство верно.









После этого ответ находится совсем просто:

$$KE=KL\frac{AH}{AE}=AH\frac{KE}{AE}=AH\frac{CF}{AF}=CF\frac{AH}{AF}=CF\frac{AB}{AE}=\frac{AE\cdot BC}{AE}=BC=a$$

Обсуждение

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

Большинство конкурсантов привели решения, либо схожие с приведенным, либо средствами аналитической геометрии.
На этом фоне выделяется решение, присланное сразу после опубликования задачи. Его автор - nnosipov

Цитата:

Будем вычислять, используя комплексные числа. Положим $A=z_1$, $B=z_2$, $C=z_3$, где все $z_k$ по модулю равны единице. Тогда

$$ H=z_1+z_2+z_3, \quad E=\frac{z_1^2+z_1z_2+z_1z_3-z_2z_3}{2z_1}, \quad F=\frac{z_3^2+z_1z_3+z_2z_3-z_1z_2}{2z_3}, $$

$$ K=\frac{z_1^2z_3+z_1z_2^2+z_1z_2z_3-z_2^2z_3}{z_1(z_2+z_3)}, \quad L=\frac{z_3(z_1^2+z_1z_2+z_1z_3-z_2^2)}{z_1(z_2+z_3)}. $$

Отсюда

$$ |KL|^2=-\frac{(z_2-z_3)^2}{z_2z_3}=|BC|^2. $$

Некоторые марафонцы задались вопросом (у наиболее проницательных вопросов не возникло): зачем в условии дан радиус вписанной окружности, от которого ответ никак не зависит (разве что r будет слишком велико по сравнению с a). Отвечаю: для запутывания "вероятного противника". Впрочем, вынужден признать, что затея провалилась.

Что будет, если исходный треугольник прямоугольный?
Если угол $C$ прямой, то решение останется в силе. только станет значительно проще ($KL$ совпадет с $BC$).
Если угол $B$ прямой, то точки $E, F, H$ и $B$ совпадают и отрезок $KL$ не определен.
Если же прямым будет угол $A$, точки $A$ и $H$ совпадают, а препендикуляр к $EF$ не пересекается с $BC$.

Награды

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

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

Разбор задачи ММ157 подготовил Владимир Лецко

[VAL]

Текущее положение участников
в XVI туре Математического марафона
\begin{tabular}{|l|l|r|r|r|r|r|r|r|r|r|r|} \hline №& Участники& 151 & 152 &153 & 154 & 155 & 156 & 157 &\Sigma \\ \hline 1.& Олег Полубасов & 5 & 9 & 4 & 5 & 4 & 5 & 6 & 38 \\ \hline 2.& Сергей Половинкин & 4 & 7 & 4 & 5 & 4 & 5 & 6 & 35 \\ \hline 3.& Виктор Филимоненков & 4 & 6 & 4 & 4 & 4 & 5 & 6 & 33 \\ \hline 4.& Анатолий Казмерчук & - & 9 & 2 & 5 & 4 & 5 & 6 & 31 \\ \hline 5.& Алексей Волошин & 4 & 4 & 2 & 5 & 4 & 5 & 6 & 30 \\ \hline 5.& Николай Дерюгин & 4 & 7 & 4 & - & 4 & 5 & 6 & 30 \\ \hline 7.& Дмитрий Пашуткин & - & - & 4 & 5 & 4 & 5 & 6 & 24 \\ \hline 8.& Евгений Машеров & - & - & - & 5 & -& 5 & - & 10 \\ \hline 9.& Евгений Гужавин & 4 & - & - & - & - & 5 & - & 9 \\ \hline 10.& Александр Князев & 1 & 2 & 3 & 1 & - & - & - & 7 \\ \hline 11.& nnosipov & - & - & - & - & - & - & 6 & 6 \\ \hline 12.& Елизавета Евдокимова & - & 2 & - & - & - & - & - & 2 \\ \hline 13.& Екатерина Шарпанова & - & 1 & - & - & - & - & - & 1 \\ \hline \end{tabular}

[Masik]

С разрешения nnosipov, форваржу фрагмент переписки.

nnosipov писал(а):

Здравствуйте, Олег! Попробую ответить на Ваши вопросы.

Цитата:

Очень хочется узнать, это какой-то стандартный метод решения геометрических задач, используя комплексные числа?

Думаю, да. Вот две книжки, где про это довольно подробно написано:
1. Моденов П.С. Задачи по геометрии. М.: Наука, 1979.
2. Понарин Я.П. Алгебра комплексных чисел в геометрических задачах: Книга для учащихся математических классов школ, учителей и студентов педагогических вузов. М.: МЦНМО, 2004.

Цитата:

Координаты точки H Вы получили, воспользовавшись теоремой Эйлера, или это само собой получилось?

Точка $H$ вычислилась сама собой.

Цитата:

А выражения для координат других точек из каких соображений получаются?

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

Цитата:

Насколько важно, что все $z_k$ по модулю равны единице?

Это важно, поскольку в формулах используется операция сопряжения комплексных чисел. Когда $|z|=1$, то $\overline{z}$ --- это просто $z^{-1}$.

Цитата:

А если в качестве нуля взять не центр описанной окружности, а, например, ортоцентр (точку H), то как изменятся формулы?

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

Цитата:

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

Вопросы совершенно разумные. Алгебра комплексных чисел, как правило, просто удобнее, чем обычная векторная алгебра. И ещё одно замечание: без компьютера (а точнее, без системы компьютерной алгебры) здесь трудно обойтись, поскольку вычисления оказываются довольно громоздкими.

У метода есть очевидные минусы. Если Вам интересно обсудить конкретные детали, можем продолжить (у меня довольно много материалов на эту тему, но сейчас ограничусь одним довольно типичным примером topic50494.html).

2VAL. Всё-таки, я считаю, что нестандартные решения заслуживают поощрения, так как расширяют кругозор остальных участников. Если все ответят одинаково, то никто ничего нового не узнает.

[VAL]

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

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

Возможно следовало поощрить обсуждаемое решение дополнительными баллами. Я и сам сомневался.
В качестве компромисса предлагаю приплюсовать поощрительный балл к оценке следующего решения nnosipov'а (вдруг приманка сработает )

Цитата:

Если все ответят одинаково, то никто ничего нового не узнает.

Ну, такое в Марафоне крайне редко случалось. Преимущественно в тех случаях, когда на задачу поступало всего одно решение

[VAL]

Сергей Половинкин опубликовал кое-что по следам задачи ММ152. Кто может подтвердить или уточнить (а может, расширить) его результаты?

[VAL]

Внимание!
Срок приема решений задачи ММ158 продлен до 12:00 19.03.12

[VAL]

========= 158 ==========

ММ158 (ТГ-4) (7 баллов)

I. Города занумерованы от 1 до N. Дорога, непосредственно соединяющая города i и j, существует, если и только если $|i-j|$ - простое число. Длина дороги равна $|i-j|$.
Найти зависимость длины кратчайшего гамильтонова цикла от величины N.
II. Заменим в I $|i-j|$ нат $i+j$.
Найти зависимость длины кратчайшего гамильтонова цикла от величины N, при условии, что полученный граф гамильтонов.

Решение

Приведу решение Алексея Волошина (с картинкой Николая Дерюгина)

I. При малых N кратчайший гамильтонов цикл находим прямым перебором:
При N < 5 гамильтоновых циклов нет.
При N = 5 минимальным будет цикл 1-3-5-2-4-1, длина 12 (цикл единственен с точностью до направления обхода).
При N = 6 минимальным будет цикл 1-3-5-2-4-6-1, длина 16 (цикл единственен с точностью до направления обхода).
При N = 7 минимальным будет цикл 1-3-5-7-2-4-6-1, длина 20 (цикл единственен с точностью до направления обхода).
При N = 8 минимальным будет цикл 1-3-6-8-5-7-2-4-1, длина 22 (цикл единственен с точностью до направления обхода).
При N = 9 минимальным будет цикл 1-3-8-6-9-7-5-2-4-1 или 1-3-5-8-6-9-7-2-4-1, длина 24 (минимальных циклов ровно два, с точностью до направления обхода).
При N > 9 построим цикл длины следующим способом:



На картинке приведен цикл для нечетного N. Для четных N "узелки", позволяющие соединить четную и нечетную цепочки, выглядят аналогично.
Докажем теперь, что этот гамильтонов путь минимален.
а) Длина пути от вершины i до вершины j не меньше |j-i|, при этом равенство достигается тогда и только тогда, когда в пути номера вершин строго монотонны, это следует из неравенства треугольника.
б) Длина пути из 1 в 2 не меньше 5, при этом равенство достигается только в случае пути 1-4-2. Доказательство очевидно - напрямую из 1 в 2 попасть нельзя, следовательно в пути не меньше двух ребер, длиной не менее 2. Но два ребра длины 2 не меняют четность вершин, следовательно длина по крайней мере одного ребра не меньше 3.
в) Аналогично, длина пути из N в N-1 не меньше 5, при этом равенство достигается только в случае пути N - (N-3) - (N-1).
В гамильтоновом цикле есть три возможных порядка обхода вершин с номерами 1, 2, N-1, N (с точностью до направления обхода):
1. 1 - 2 - (N-1) - N. При этом длина пути не меньше 2N+6. (1)
2. 1 - 2 - N - (N-1). При этом длина пути не меньше 2N+6. (2)
3. 1 - N - 2 - (N-1). При этом длина пути не меньше 4N-8. (3)
При N > 9 путь в (3) заведомо длиннее: 4N-8 > 2N+6.

II. Длина гамильтонова пути $a_1-a_2-a_3-\dots-a_{N-1}-a_N-a_1$ в таком графе равна $(a_1+a_2) + (a_2+a_3) + \dots + (a_{N-1}+a_N) + (a_N+a_1) = 2( 1 + 2 + \dots + N-1 + N) = N(N+1).$

Ответ:
I.
При N < 5 гамильтонова цикла нет;
при N = 5 длина кратчайшего гамильтонова цикла равна 12;
при N = 6 длина кратчайшего гамильтонова цикла равна 16;
при N > 6 длина кратчайшего гамильтонова цикла равна 2N+6;
II.
Если гамильтонов цикл существует, его длина равна N(N+1).

Обсуждение

Легко видеть, что в пункте II граф получется двудольным (смежные вершины могут быть только разной четности). Поскольку при нечетных N число вершин в долях получается разным, гамильтонова цикла в этом случае быть не может.
При четных N > 2 гамильтоновы циклы для малых значений N легко строятся. Поскольку с ростом N число гпмильтоновых циклов лавинообразно возрастает, очевидно (хотя и не доказано строго никем из участников ), что гамильтоновы циклы есть при всех четных N > 2.

Можно показать, что в пункте I при N > 9 для четных N в кратчайшем гамильтоновом цикле реализуется только схема обхода (1), а для нечетных - схема обхода (2). Поэтому при N > 9 кратчайший гамильтонов цикл определен однозначно. Таким образом, случай N = 9 является особенным. Только для него существует два различных кратчайших гамильтоновых цикла.

Алексей Волошин задался вопросом о нахождении не кратчайших, а наоборот длиннейших гамильтоновых циклов для пункта (1).
Очевидно, что эта длина не превосходит $\left{\lfloor{N^2}2\rfloor$ - длины наибольшего гамильтонова цикла в полном графе, в котором длина ребра из i в j равна $|j-i|$ (см. A007590 в OEIS).
При 4 < N < 12 эта оценка точна. Однако, при N = 12 наибольшая длина гамильтонова цикла в графе из I равна 70, а не 72.

Сергей Половинкин рассмотрел графы, возникающие при комбинировании условий пунктов I и II: дорога из i в j существует, i+j - просто, но ее длина равна $|j-i|$.
Вот таблица зависимости длины кратчайшего гамильтонова цикла от N для этого типа графов.

$$\displaystyle \begin{array}{|c|c|} \hline N & d(N) \\ \hline 4 & 6 \\ 6 & 14 \\ 8 & 18 \\ 10 & 20 \\ 12 & 28 \\ 14 & 48 \\ 16 & 40 \\ 18 & 52 \\ 20 & 58 \\ \hline \end{array}$$

Бросается в глаза отсутствие монотонности. Общую формулу Сергею получить не удалось.

Награды

За правильное решение и некоторое обобщение задачи ММ158 Алексей Волошин и Сергей Половинкин получают по 8 призовых баллов. За верное решение задачи Виктор Филимоненков и Анатолий Казмерчук получают по 7 призовых баллов. Николай Дерюгин (допустивший ошибку для случая N=8) получает 6 призовых баллов. Автор задачи Олег Полубасов получает 7 призовых баллов.

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

Разбор задачи ММ158 подготовил Владимир Лецко