2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5, 6, 7 ... 58  След.
 
 Re: Обсуждение и разбор марафонских задач
Сообщение18.06.2009, 00:11 
Заслуженный участник


27/06/08
4058
Волгоград
Текущее положение конкурсантов
в 11-м туре Математического марафона

$\begin{tabular}{|l|l|r|r|r|r|r|r|r|} 
\hline 
№& Участники& 101 & 102 & 103 & 104 & 105 & 106 & \Sigma \\ 
\hline 
1.& Анатолий Казмерчук & 8 & 8 & 3 & 9 & 6 & 7 & 41 \\ 
\hline
2.& Андрей Халявин & 9 & 8 & - & - & - & - & 17 \\ 
\hline 
3. & Кирилл Веденский & 2 & - & 3 & - & 6 & 5 & 16 \\ 
\hline 
4. & Николай Дерюгин & 1 & 6 & - & - & 3 & 4 & 14 \\ 
\hline 
5. & Виктор Филимоненков & - & - & 3 & - & 6 & 3 & 12 \\ 
\hline 
6. & Петр Бежик & - & - & - & - & - & 7 & 7 \\ 
\hline \end{tabular}$

-- 18 июн 2009, 02:18 --


 Профиль  
                  
 
 Re: Обсуждение и разбор марафонских задач
Сообщение24.06.2009, 00:32 
Заслуженный участник


27/06/08
4058
Волгоград
Последняя задачка 11-го тура Математического марафона доступна на http://www.fizmat.vspu.ru/doku.php?id=marathon:about.

 Профиль  
                  
 
 Re: Обсуждение и разбор марафонских задач
Сообщение26.06.2009, 11:32 
Заслуженный участник


27/06/08
4058
Волгоград
VAL в сообщении #224402 писал(а):
Последняя задачка 11-го тура Математического марафона доступна на http://www.fizmat.vspu.ru/doku.php?id=marathon:about.
А теперь и здесь http://dxdy.ru/topic16091.html

 Профиль  
                  
 
 Re: Обсуждение и разбор марафонских задач
Сообщение04.07.2009, 10:42 
Заслуженный участник


27/06/08
4058
Волгоград
===============

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

ММ107 (4 балла)

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

Примечание:
Магический квадрат - это квадратная матрица, у которой сумма элементов каждой строки (столбца, большой диагонали) равна одному и тому же числу (магической сумме).

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

Решение

Приведу решение Тимофея Игнатьева.

Лемма.
Центральный элемент магического квадрата 3x3 равен трети магической суммы.

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

Итак магическая сумма квадрата 3x3 является составным числом, даже если он заполнен произвольными (различными) натуральными (а не только простыми) числами.

Обсуждение

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

И лишь Николай Дерюгин привел сразу несколько квадратов, заполненных попарно различными простыми числами с магической суммой 61 (а также квадрат с магической суммой 67). К сожалению, Николай забыл, что сумма элементов каждой из больших диагоналей также должна совпадать с магической.

Награды

За правильное решение задачи ММ107 Виктор Филимоненков, Кирилл Веденский, Тимофей Игнатьев, Наталия Макарова, Алексей Волошин и Анатолий Казмерчук получают по 4 призовых балла. Николай Дерюгин (правильно решивший искаженную задачу) получает два призовых балла.

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

-- 04 июл 2009, 12:50 --

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

Текущее положение конкурсантов
в 11-м туре Математического марафона

$\begin{tabular}{|l|l|r|r|r|r|r|r|r|r|} 
\hline 
№& Участники& 101 & 102 & 103 & 104 & 105 & 106 & 107 & \Sigma \\ 
\hline 
1.& Анатолий Казмерчук & 8 & 8 & 3 & 9 & 6 & 7 & 4 & 45 \\ 
\hline
2. & Кирилл Веденский & 2 & - & 3 & - & 6 & 5 & 4 & 20 \\ 
\hline 
3.& Андрей Халявин & 9 & 8 & - & - & - & - & - & 17 \\ 
\hline 
4. & Николай Дерюгин & 1 & 6 & - & - & 3 & 4 & 2 & 16 \\ 
\hline 
4. & Виктор Филимоненков & - & - & 3 & - & 6 & 3 & 4 & 16 \\ 
\hline 
6. & Петр Бежик & - & - & - & - & - & 7 & - & 7 \\ 
\hline 
7. & Тимофей Игнатьев & - & - & - & - & - & - & 4 & 4 \\ 
\hline 
7. & Наталия Макарова & - & - & - & - & - & - & 4 & 4 \\ 
\hline
7. & Алексей Волошин & - & - & - & - & - & - & 4 & 4 \\ 
\hline 
\end{tabular}$

 Профиль  
                  
 
 Re: Обсуждение и разбор марафонских задач
Сообщение04.07.2009, 23:27 
Заслуженный участник


27/06/08
4058
Волгоград
===============

Задачка с антресолей.

ММ108 (4 балла)

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

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

Решение

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

Пусть вес самой верхней части (самой маленькой) равен 1. Тогда, из соображений подобия вес первых k частей равен $k^3$, а вес k-го слоя равен $k^3-(k-1)^3$.
Следовательно, вес каждого слоя - целое число. Если их можно разложить на разные чаши равноплечных весов без гирь так, чтобы весы уравновесились, то общий вес пирамиды - чётное число. Следовательно, общее число слоёв должно быть чётно.
При разбиении на 2 части на каждую чашу весов необходимо положить вес $(2^3)/2=4$, а веса слоёв равны 1 и 7. Вес второго слоя превышает 4, следовательно, уравновесить весы нельзя.
При разбиении на 4 части на каждую чашу весов необходимо положить вес $(4^3)/2=32$, а веса слоёв равны 1, 7, 19, и 37. Вес четвертого слоя превышает 32, следовательно, уравновесить весы нельзя.
При разбиении на 6 частей на каждую чашу весов необходимо положить вес $(6^3)/2=108$, а веса слоёв равны 1, 7, 19, 37, 61 и 91. На одну из чаш мы положим последний слой весом 91. Дополнительно на эту чашу нужно положить слои суммарным весом 108-91=17. Но слои весом более 17 мы положить не сможем, а вес всех оставшихся частей равен 1+7=8, т. е. меньше 17. Следовательно, уравновесить весы нельзя.
При разбиении на 8 частей на каждую чашу весов необходимо положить вес $(8^3)/2=256$, а веса слоёв равны 1, 7, 19, 37, 61, 91, 127 и 169. Имеем:
1+37+91+127=7+19+61+169=256.
Ответ: наименьшее количество слоёв равно 8.

Обсуждение

Задача ММ108 имеет интересное обобщение. Порежем n-мерную пирамиду гиперплоскостями, параллельными гиперплоскости основания на $2^n$ слоев равной толщины. Тогда т-мерные объемы слоев будут относиться как разности соседних n-x степеней.
Оказывается, при любом n можно разбить полученные слои на два класса по $2^{n-1}$ кусков в каждом, так что суммарные n-мерные объемы кусков в классах будут равны.
Пронумеруем куски от вершины к основанию числами $0, 1, ..., 2^n-1$. Соответствующее разбиение задается производящей функцией: $\Pi_{i=0}^{n-1}(1-x^{2^i})$. Если (после раскрытия скобок) коэффициент при соответствуещей степени $x$ положителен помещаем кусок в первый класс, если отрицателен - во второй.
Альтернативный способ - поместить в первый класс те и только те куски, номера которых в двоичной записи содержат четное число единиц.

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

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

Для $n\le3 \ \ 2^n$ - наименьшее число слоев, удовлетворяющее условию. Будет ли оно таковым для бОльших $n$ мне неизвестно.

Награды

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

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

-- 05 июл 2009, 01:32 --

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

Текущее положение конкурсантов
в 11-м туре Математического марафона

$\begin{tabular}{|l|l|r|r|r|r|r|r|r|r|r|} 
\hline 
№& Участники& 101 & 102 & 103 & 104 & 105 & 106 & 107 & 108 & \Sigma \\ 
\hline 
1.& Анатолий Казмерчук & 8 & 8 & 3 & 9 & 6 & 7 & 4 & 4 & 49 \\ 
\hline
2. & Кирилл Веденский & 2 & - & 3 & - & 6 & 5 & 4 & 4 & 24 \\ 
\hline 
3. & Николай Дерюгин & 1 & 6 & - & - & 3 & 4 & 2 & 4 & 20 \\ 
\hline 
3. & Виктор Филимоненков & - & - & 3 & - & 6 & 3 & 4 &  4 & 20 \\ 
\hline 
5.& Андрей Халявин & 9 & 8 & - & - & - & - & - & - & 17 \\ 
\hline 
6. & Тимофей Игнатьев & - & - & - & - & - & - & 4 & 5 & 9 \\ 
\hline 
7. & Алексей Волошин & - & - & - & - & - & - & 4 & 4 & 8 \\ 
\hline 
8. & Петр Бежик & - & - & - & - & - & 7 & - & - & 7 \\ 
\hline 
9. & Наталия Макарова & - & - & - & - & - & - & 4 & - & 4 \\ 
\hline
\end{tabular}$

 Профиль  
                  
 
 Re: Обсуждение и разбор марафонских задач
Сообщение07.07.2009, 12:26 
Заслуженный участник


27/06/08
4058
Волгоград
===============

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

Тремя семействами параллельных линий плоскость разрезана на равные треугольники.
Можно ли в каждый труегольник вписать одно из чисел 1, 2, 3 так, чтобы:
1) хотя бы в один треугольник была вписана тройка;
2) число в каждом треугольнике указывало, сколько различных чисел написано в трех треугольниках, имеющих общую сторону с данным?

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

Решение

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

Изображение

Обсуждение

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

Изображение

В задаче Н. Агаханова, послужившей прототипом для ММ109, речь шла о заполнении плоскости, разлинованной в клеточку, числами 1, 2, 3, 4. А решение заключалось в обосновании невозможности такого заполнения.

Награды

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

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

-- 07 июл 2009, 14:32 --

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

Текущее положение конкурсантов
в 11-м туре Математического марафона

$\begin{tabular}{|l|l|r|r|r|r|r|r|r|r|r|r|} 
\hline 
№& Участники& 101 & 102 & 103 & 104 & 105 & 106 & 107 & 108 & 109 & \Sigma \\ 
\hline 
1.& Анатолий Казмерчук & 8 & 8 & 3 & 9 & 6 & 7 & 4 & 4 & 6 & 55 \\ 
\hline
2. & Николай Дерюгин & 1 & 6 & - & - & 3 & 4 & 2 & 4 & 6 & 26 \\ 
\hline 
2. & Виктор Филимоненков & - & - & 3 & - & 6 & 3 & 4 &  4 & 6 & 26 \\ 
\hline 
4. & Кирилл Веденский & 2 & - & 3 & - & 6 & 5 & 4 & 4 & - & 24 \\ 
\hline 
5.& Андрей Халявин & 9 & 8 & - & - & - & - & - & - & - & 17 \\ 
\hline 
6. & Алексей Волошин & - & - & - & - & - & - & 4 & 4 & 6 & 14 \\ 
\hline 
7. & Тимофей Игнатьев & - & - & - & - & - & - & 4 & 5 & - & 9 \\ 
\hline 
8. & Петр Бежик & - & - & - & - & - & 7 & - & - & - & 7 \\ 
\hline 
9. & Наталия Макарова & - & - & - & - & - & - & 4 & - & - & 4 \\ 
\hline
\end{tabular}$

 Профиль  
                  
 
 Re: Обсуждение и разбор марафонских задач
Сообщение09.07.2009, 00:50 
Заслуженный участник


27/06/08
4058
Волгоград
===============

ММ110 (КГ-5) (6 баллов)

Квадрат со стороной n (n - натуральное, большее 1) разрезали на 4 прямоугольника
с целочисленными сторонами. Сколько различных значений может принимать сумма
периметров полученных прямоугольников при всех таких разрезаниях?

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

Решение

Приведу решение Виктора Филимоненкова (единственного из марафонцев, обошедшегося без чертежа):

Ответ: 1 при $n = 2$, 3 при $n = 3$, $2n-2$ при $n > 3$.

Любое разрезание квадрата $n\times n$ на 4 прямоугольника можно провести так: провести линию длины $n$ параллельно одной из сторон, потом провести линию, разрезающую один из полученных прямоугольников на 2, и, наконец, провести третью линию, разрезающую один из полученных прямоугольника на 2.

Сумма периметров полученных прямоугольников равна $4n$ (суммы длин квадратов) + $2k$ (удвоенная сумма длин трех внутренних отрезков). Значит, число различных периметров зависит от числа значений, которые может принимать число $k$.

При $n = 2$ $k$ принимает одно значение (4), что очевидно.
При $n = 3$ $k$ принимает 3 значения (5, 6 и 7), что легко проверить простым перебором.

Пусть $n > 4$. Поскольку один из трех внутренних отрезков равен n, то $k \ge n+2$ (когда остальные два внутренних отрезка равны 1). Поскольку каждый из внутренних отрезков не длиннее $n$, $k \le 3n$. При этом невозможно, чтобы $k = 3n-1$. Действительно, это означало бы, что проведены 2 внутренних отрезка длиной $n$, и один длиной $n-1$. Но тогда отрезки длиной n были бы параллельны, а отрезок длиной $n-1$ им перпендикулярен. Но 2 отрезка длиной $n$ разрезают квадрат на 3 полосы, ширина каждой из которых не меньше 1, поэтому самая длинная не шире, чем $n-2$, значит, отрезок длиной $n-1$ провести будет невозможно.

Все остальные $2n-2$ значения числа $k$ из интервала $n+2 \le k \le 3n$ возможны. Действительно, проведем линию длиной $n$, отрезав полосу шириной $m$, потом в этой полосе проведем линию длиной $m$, отрезав полосочку шириной 1. При $m = 1$ проведем еще линию длиной 1, параллельную второй, получим $k = n+2$.
При $m > 1$ в полоске $m\times 1$ проведем отрезок длиной 1, получим $k = n+m+1$ для всех возможных $m < n$.
Чтобы получить $k > 2n$, проведем две параллельные линии длиной $n$ каждая на ширине l друг от друга, и разделим эту полоску линией длины l на 2 прямоугольника ($1 \le l \le n-2$). Наконец, при $n > 4$ можно провести 3 параллельные друг другу линии длиной $n$, что дает значение $k = 3n$.


Награды

За правильное решение задачи ММ110 Алексей Волошин, Виктор Филимоненков, Анатолий Казмерчук и Кирилл Веденский получают по 6 призовых баллов.
Николай Дерюгин (он неверно сосчитал суммарные периметры при одном из способов разрезания) получает 4 призовых балла.
Анна Ширяева (она прошла мимо одного из возможных способов разрезания) получает 3 призвых балла.

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

-- 09 июл 2009, 03:02 --

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

Итоговое положение конкурсантов в 11-м туре Математического марафона


$\begin{tabular}{|l|l|r|r|r|r|r|r|r|r|r|r|r|} 
\hline 
№& Участники& 101 & 102 & 103 & 104 & 105 & 106 & 107 & 108 & 109 & 110 & \Sigma \\ 
\hline 
1.& Анатолий Казмерчук & 8 & 8 & 3 & 9 & 6 & 7 & 4 & 4 & 6 & 6 & 61 \\ 
\hline
2. & Виктор Филимоненков & - & - & 3 & - & 6 & 3 & 4 &  4 & 6 & 6 & 32 \\ 
\hline 
3. & Николай Дерюгин & 1 & 6 & - & - & 3 & 4 & 2 & 4 & 6 & 4 & 30 \\ 
\hline 
3. & Кирилл Веденский & 2 & - & 3 & - & 6 & 5 & 4 & 4 & - & 6 & 30 \\ 
\hline 
5. & Алексей Волошин & - & - & - & - & - & - & 4 & 4 & 6 & 6 & 20 \\ 
\hline 
6.& Андрей Халявин & 9 & 8 & - & - & - & - & - & - & - & - & 17 \\ 
\hline 
7. & Тимофей Игнатьев & - & - & - & - & - & - & 4 & 5 & - & - & 9 \\ 
\hline 
8. & Петр Бежик & - & - & - & - & - & 7 & - & - & - & - & 7 \\ 
\hline 
9. & Наталия Макарова & - & - & - & - & - & - & 4 & - & - & - & 4 \\ 
\hline
10. & Анна Ширяева & - & - & - & - & - & - & - & - & - & 3 & 3 \\ 
\hline
\end{tabular}$

-- 09 июл 2009, 03:15 --

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

Итоговое положение конкурсантов
в тематическом конкурсе по комбинаторной геометрии

$\begin{tabular}{|l|l|r|r|r|r|r|r|} 
\hline 
№& Участники& КГ1 & КГ2 & КГ3 & КГ4 & КГ5 & \Sigma \\ 
\hline 
1.& Анатолий Казмерчук & 8 & 8 & 3 & 9 & 6 & 34 \\ 
\hline
2.& Андрей Халявин & 9 & 8 & - & - & - & 17 \\ 
\hline 
3. & Николай Дерюгин & 1 & 6 & - & - & 4 & 11 \\ 
\hline 
3. & Кирилл Веденский & 2 & - & 3 & - & 6 & 11 \\ 
\hline 
5. & Виктор Филимоненков & - & - & 3 & - & 6 & 9 \\ 
\hline 
6. & Алексей Волошин & - & - & - & - & 6 & 6 \\ 
\hline 
7. & Анна Ширяева & - & - & - & - & 3 & 3 \\ 
\hline \end{tabular}$

Мои поздравления дважды триумфатору 11-го тура Анатолию Казмерчуку!

 Профиль  
                  
 
 Re: Обсуждение и разбор марафонских задач
Сообщение09.07.2009, 12:31 
Заслуженный участник


27/06/08
4058
Волгоград
Положение лидирующей группы после 11-и туров Марафона

\begin{tabular}{|l|l|r|r|r|r|r|r|r|r|r|r|r|c|}
\hline
№ & Участники                &  I  &  II  &  III  &  IV  &  V  &  VI  &  VII  &  VIII  &  IX  &  X  &  XI & \Sigma\\
\hline
1. & Владислав Франк     &  -  &  -  &  32  &  53  &  47  &  85  &  59  &  47  &  23  &  33  &    &  379\\
\hline
2. & Олег Полубасов       &  -  &  -  &  -     &  -     &  77  &  -    &  65  &  45  &  81  &  -   &    &  268\\
\hline
3. & Виктор Филимоненков &  -  &  -  &  -   &  -    &  -   &  77   &  64  &  60  &  7  &  21   & 32 &  261\\
\hline
4. & Анатолий Казмерчук  &  -  &  -  &  -     &  -     &  -  &  -    &  -   &  55  &  67   &   -   &  61  &  183\\
\hline
5. & Андрей Богданов       &  -  &  -  &  -     &  -     &  45  &  -    &  52  &  15  &  -  &  -   &    &  112\\
\hline
6. & Иван Козначеев        &  -  &  -  &  -     &  53    &  2   &  13   &  8   &  9   &  3   &  -   &    &  88\\
\hline
7. & Борис Бух               &  38  &  28  & 15  &  -  &   -   &  -    &   -   &  -    &  -    &  -    &    &  81\\
\hline
8. & Макс Алексеев        &  8  &  6  &  28     &  12     &  26   &  -    &  -  &  -  &  -  &  -   &     & 80\\
\hline
9. & Константин Кноп      &  -  &  -  &  -     &  -     &  14  &  -   &  16   &  45   &  -   &  -    &    &  75\\
\hline
10. & Андрей Винокуров  &  -  &  -  &  -     &  -     &  73  &  -    &  -   &   -   &  -   &  -    &    &  73\\
\hline
10. & Дмитрий Милосердов &  -  &  -  &  -   &  -    &  18  &  4    &  28   &   23   &  -   &  -   &    &  73\\
\hline
12. & Андрей Халявин         &  -  &  -  &  -     &  -     &  -   &  -    &  -   &   -   &  -   &  49    & 17 &  66\\
\hline
13. & Алексей Волошин       &  -  &  -  &  -     &  -     &  -   &  -    &  -   &   -   &  -   &  45   & 20 &  65\\
\hline
14. & Мигель Митрофанов  &  -  &  -  &  -    &  -     &  48  &  3    &  -   &   -   &  -   &  -    &    &  51\\
\hline
14. & Николай Дерюгин      &  -  &  -  &  -     &  -     &  -   &  -   &  -   &   -   &  18   &   3    & 30 &   51\\
\hline
16. & Алексей Извалов        &  -  &  -  &  -     &  -     &  -   &  -    &  -   &   -   &  -   &  46   &    &  46\\
\hline
17. & Евгений Машеров       &  -  &  -  &  -    &  -    &  -   &  -   &  17   &   15   &  8   &  5   &    &  45\\
\hline
18. & Андрей Бежан           &  -  &  6  &  26   &  -    &  5   &  -   &  5   &   -   &  -   &  -    &    &   42\\
\hline
19. & Сергей Аракчеев       &  -  &  -  &  -     &  -     &  -   &  -    &  35   &   4   &  -   &   -    &    &  39\\
\hline
20. & Сергей Беляев          &  -  &  -  &  -    &  -     &  -   &  -   &  24   &  14   &  -   &  49    &    &  38\\
\hline
21. & Вячеслав Пономарев  &  20  &  11  &  -    &  3   &  -   &  -   &  -   &   -  &  -   &  -    &    &   34\\
\hline
22. & Павел Егоров            &  20  &  -  &  13     &  -     &  -   &  -    &  -   &   -   &  -   &  -   &    &  33\\
\hline
22. & Владимир Трушков    &  -  &  12  &  18   &  -    &  3   &  -    &  -   &   -   &  -   &  -   &    &   33\\
\hline
24. & Стас Грицюк             &  -  &  -  &  -     &  -     &  -   &  -    &  27   &   6   &  -   &  -   &    &   33\\
\hline
25. & Кирилл Веденский      &  -  &  -  &  -     &  -     &  -   &  -    &  -   &   -   &  -   &   -    & 30 &   30\\
\hline
26. & Маша Никулина        &  5  &  7  &  -    &   4    &  8   &  -    &  -   &   -   &  -   &  -    &    &   24\\
\hline
26. & Алексей Кутузов       &  -  &  -  &  -     &  -     &  -   &  -    &  24   &   -   &  -   &  -    &    &  24\\
\hline
26. & Галина Крюкова        &  -  &  -  &  -    &  -    &  -   &  -    &  -   &   13   &  11   &  -    &    &  24\\
\hline
29. & Татьяна Шемелова     &  -  &  -  &  -     &  -     &  -   &  -    &  15   &   -   &  4   &  -   &    &   19\\
\hline
30. & Иван Держанский      &  -  &  -  &  -     &  -     &  -   &  -    &  16   &   -   &  -   &  -    &    &   16\\
\hline
\end{tabular}

 Профиль  
                  
 
 Re: Обсуждение и разбор марафонских задач
Сообщение07.10.2009, 23:18 
Заслуженный участник


27/06/08
4058
Волгоград
До утра (а может и до завтрашнего вечера) еще не поздно прислать мне решение MM111.
Устная же задачка. Хотя и с подвохом.

 Профиль  
                  
 
 Re: Обсуждение и разбор марафонских задач
Сообщение08.10.2009, 19:11 
Заслуженный участник


27/06/08
4058
Волгоград
===============

Задача ММ111 утратила статус конкурсной и может свободно обсуждаться на форуме.

Результат Задачи ММ111 учитывается дважды: в тематическом конкурсе и в основном Марафоне.

ММ111 (Ш-1) (3 балла)

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

Примечание:
Ходы должны делаться по всем правилам шахматной игры.

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

Решение

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

Достижение указанной позиции возможно не быстрее, чем за 6 ходов. Всего возможно 4 варианта:
1.Kf3 Kf6
2.Kd4(Ke5) Kd5(Ke4)
3.Kc6 Kc3
4.K:b8 K:b2
5.Л:b2 Л:b8
6.Лa1 Лa8
При оценивании минимального количества ходов, необходимых для достижения указанной позиции, учитываем следующие соображения:
возможны ходы только конями и ладьями;
последнее взятие делает ладья;
если ладьями (ладьёй) берётся два коня одной стороны (например, белых), то белым потребуется не менее 8 ходов для достижения конями последней горизонтали;
если ладьёй берётся ровно один конь А (например, g1), то на это понадобится более 12 полуходов:
не менее 4 полухода на достижения этим конём противоположной горизонтали,
не менее 2 полухода ладьи (взятие и возвращение на исходное поле, или отход и возвращение на исходное поле со взятием) плюс один полуход противоположной стороны,
на взятие одним конём другого и постановка под бой конём А не менее 6 полуходов с обоих сторон (например, вот так
Kc3 Kf6
Kd5 K:d5
. . . Kb4
. . . Kc6).
Таким образом, минимально возможное количество ходов равно 6 и возможно только при взятии с каждой стороны ладьями ровно по одной фигуре - коню, два других коня должны браться на своих исходных полях, причём конями противоположной стороны, делающих для этого по 4 хода, значит, должны занимать исходное поле того же цвета. Получается один из четырёх указанных вариантов.
Заметим, что симметричное относительно вертикальной оси симметрии развитие партии невозможно из-за шахов королям с полей f6 и f3.

Обсуждение

Задача планировалась, как разминочная. но маленький нюанс (см. замечание в конце решения) ускользнул от внимания некоторых конкурсантов, насчитавших 8 способов получения требуемой позиции за 6 ходов.

Награды

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

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

 Профиль  
                  
 
 Re: Обсуждение и разбор марафонских задач
Сообщение11.10.2009, 15:57 
Заслуженный участник


27/06/08
4058
Волгоград
Задача ММ112 утратила статус конкурсной и может свободно обсуждаться на форуме.

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

Светлой памяти C5 ЕГЭ посвящается.

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

Решить уравнение при всех возможных наборах значений параметров a и b:
$$11x+a^2-2a+b^2+4b+|2x+a^2-2a+4b+b^2|+|-3x+2+a^2-2a-4b-b^2|+|-x-4b-b^2+a^2-2a|+18|x-2|=20$$

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

Решение

График функции $$f(x)=11x+a^2-2a+b^2+4b+|2x+a^2-2a+4b+b^2|+|-3x+2+a^2-2a-4b-b^2|+|-x-4b-b^2+a^2-2a|+18|x-2|-20,$$ очевидно, представляет собой ломаную. Поскольку $18 > 11+2+3+1$, независимо от того, с каким знаком раскрываются
абсолютные величины, при $x<2$ функция убывает, а при $x>2$ - возрастает.
Поэтому разрешимость уравнения равносильна условию $f(2) \le 0$.
После замены переменных $c=(a-1)^2+(b+2)^2, \ d=(a-1)^2-(b+2)^2$ получим $-3+c+|c-1|+|d-1|+|d+1|\le 0$.
Учитвыя, что $c-1+|c-1| \ge 0$ и $|d-1|+|d+1| \ge 2$, приходим к выводу, что условие $f(2)<0$ не выполняется никогда, а $f(2)=0$ выполняется тогда и только тогда, когда $c \le 1$ и $-1 \le d \le 1$.
Возвращаясь к параметрам $a$ и $b$ и принимая во внимание, что $(a-1)^2+(b+2)^2 \le 1$ влечет $|(a-1)^2-(b+2)^2| \le 1$,
окончательно получаем
Ответ: $x=2$ при $(a-1)^2+(b+2)^2 \le 1$; при остальных $a$ и $b$ нет решений.

Обсуждение

Любопытно выглядит (а заодно подтверждает правильность наших выкладок) график $f(2)$, рассматриваемой как функция от $a$ и $b$:

Изображение

Награды

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

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

-- 11 окт 2009, 19:00 --

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

Текущее положение участников
в XII туре Математического марафона

$\begin{tabular}{|l|l|r|r|r|} 
\hline 
№& Участники& 111 & 112 & \Sigma \\ 
\hline 
1.& Анатолий Казмерчук & 3 & 6 & 9 \\ 
\hline
1.& Сергей Половинкин & 3 & 6 & 9 \\ 
\hline
3.& Виктор Филимоненков & 2 & 6 & 8 \\ 
\hline
3.& Алексей Волошин & 2 & 6 & 8 \\ 
\hline
5.& Николай Дерюгин & 3 & 4 & 7 \\ 
\hline
6.& Андрей Халявин & 0 & 6 & 6 \\ 
\hline
6.& Владислав Франк & 0 & 6 & 6 \\ 
\hline
6.& Кирилл Веденский & 0 & 6 & 6 \\ 
\hline
9.& Эдвард Туркевич & 2 & 3 & 5 \\ 
\hline
10.& Александр Расстригин & 3 & 0 & 3 \\ 
\hline
\end{tabular}$

 Профиль  
                  
 
 Re: Обсуждение и разбор марафонских задач
Сообщение23.10.2009, 16:49 
Заслуженный участник


27/06/08
4058
Волгоград
Задача ММ113 утратила статус конкурсной и может свободно обсуждаться на форуме.

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

Результат Задачи ММ113 учитывается дважды: в тематическом конкурсе и в основном Марафоне.

ММ113 (Ш-3) (10 баллов)

На множестве полей шахматной доски определим структуру графа $G_N$ следующим образом:
две вершины (два поля) будем считать смежными, если конь может за один ход переместиться из одной вершины в другую.
Аналогично определим граф слона $G_B$, граф ладьи $G_R$, граф ферзя $G_Q$ и граф короля $G_K$.
Для каждого из этих графов:
1. Найти
а) количество ребер;
б) количество компонент связности;
в) радиус и диаметр каждой компоненты;
г) наибольшую клику.
2. Выяснить является ли граф:
а) двудольным;
б) эйлеровым;
в) гамильтоновым;
г) планарным?

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

Решение

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

1.а. Количество ребер большинства графов легче всего найти как полусумму степеней всех вершин. Разумеется, при этом следует использовать симметричность доски.
Например, для графа коня искомое число ребер равно $\frac12(4\cdot2+8\cdot3+20\cdot4+16\cdot6+16\cdot8)=168$.
Для графа ферзя проще просто просуммировать количества ребер в графах ладьи и слона.

1.б. У графа слона две компоненты связности (черные и белые поля). Остальные графы, очевидно, связны.

1.в. Диаметр и радиус графов ладьи и ферзя, а также каждой компоненты связности графа слона, очевидно, равны 2.
Тривиально проверяется, что из каждого из полей d4, d5, e4, e5 король может добраться до любого поля не более чем за 4 хода. Поэтому радиус графа короля - 4.
В то же время, на маршрут от любого края до противоположного края доски королю понадобится 7 ходов. Поэтому диаметр графа короля - 7.
Наиболее содержательная задача - нахождение диаметра и радиуса графа коня. Ее можно решить, найдя поиском в ширину эксцентриситеты всех вершин графа коня.
Поиск в ширину можно провести в табличке 8х8 клеток вручную: помещаем 0 в начальную клетку; ставим 1 во все клетки, смежные начальной; ставим 2 во все свободные клетки, смежные клеткам. помеченным 1; и т.д.
В последней заполненной клетке будет записан эксцентриситет начальной вершины.
Разумеется, нет никакой необходимости применять данный алгоритм ко всем 64-м вершинам графа коня. По соображениям симметрии достаточно обследовать поля a1, b1, b2, c1, c2, c3, d1, d2, d3, d4.

1.г. Наибольшие клики в графах слона (большая диагональ) ладьи (любая горизонталь или вертикаль) и ферзя содержат по 8 вершин.
Наибольшая клика в графе короля (любой квадрат 2х2) содержит 4 вершины.
Поскольку среди любых трех полей найдутся, по крайней мере, два одноцветных, в графе коня не может быть клики, содержащей более двух вершин.

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

2.б. Граф ладьи, степень каждой вершины которого равна 14, эйлеров. В остальных графах есть вершины нечетных степеней.

2.в. Граф слона не связен и потому не гамильтонов. Гамильтонов цикл в графе коня и в остальных графах (один для всех) приведены на рисунках, заимствованных у Николая Дерюгина.
Изображение Изображение

2.г. Ни один из графов не планарен. В графах слона, ладьи и ферзя есть пятивершинные клики, а в графах короля и коня легко отыскать подграфы, стягиваемые, например, к $K_{3,3}$.

Ответ:

$\begin{tabular}{|l|c|c|c|c|c|c|c|c|c|} 
\hline 
& Edges & Components & Diameter & Radius & Clique & Bichrom & Euler & Hamilton & Planar \\ 
\hline 
G_N & 168 & 1 & 6 & 4 &  2 & + & - & + & - \\ 
\hline
G_B & 280 & 2 & 2 & 2 & 8 & - & - & - & - \\ 
\hline 
G_R & 448 & 1 & 2 & 2 & 8 & - & + & + & - \\ 
\hline 
G_Q & 728 & 1 & 2 & 2 & 8 & - & - & + & - \\ 
\hline 
G_K & 210 & 1 & 7 & 4 & 4 & - & - & + & - \\ 
\hline \end{tabular}$

Обсуждение

Большинство пунктов задачи тривиальны. цена в 10 баллов отражает не сложность, а количество задачек, объединенных под общей шапкой ММ113. Правильность такого подхода косвенно подтвердили и сами участники, большинство из которых не обошлось без ошибок. Значительная часть этих ошибок была устранена марафонцами еще до публикации разбора задачи, а остальные нашли отражение в призовых баллах за задачу.
Наиболее содержательный пункт задачи (о гамильтоновости графа коня) является, к сожалению, и наиболее известным. Поэтому я вполне согласен (что бывает со мной редко :)) с теми участниками, которые не слишком высоко оценили эстетическую сторону задачи, (хотя и с теми, кому задачка понравилась, тоже спорить не буду :)).

Награды

За решение задачи ММ113 Алексей Волошин получает 11 призовых баллов (1 балл добавлен за доскональное обоснование каждого пункта), Сергей Половинкин, Анатолий Казмерчук и Виктор Филимоненков получают по 10 призовых баллов, Николай Дерюгин и Кирилл Веденский получают по 9 призовых балла, а Эдвард Туркевич - 8 призовых баллов.

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

-- 23 окт 2009, 19:11 --

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

Текущее положение участников
в XII туре Математического марафона

$\begin{tabular}{|l|l|r|r|r|r|} 
\hline 
№& Участники& 111 & 112 & 113 & \Sigma \\ 
\hline 
1.& Анатолий Казмерчук & 3 & 6 & 10 & 19 \\ 
\hline
1.& Сергей Половинкин & 3 & 6 & 10 & 19 \\ 
\hline
1.& Алексей Волошин & 2 & 6 & 11 & 19 \\ 
\hline
4.& Виктор Филимоненков & 2 & 6 & 10 & 18 \\ 
\hline
5.& Николай Дерюгин & 3 & 4 & 9 & 16 \\ 
\hline
6.& Кирилл Веденский & 0 & 6 & 9 & 15 \\ 
\hline
7.& Эдвард Туркевич & 2 & 3 & 8 & 13 \\ 
\hline
8.& Андрей Халявин & 0 & 6 & 0 & 6 \\ 
\hline
8.& Владислав Франк & 0 & 6 & 0 & 6 \\ 
\hline
10.& Александр Расстригин & 3 & 0 & 0 & 3 \\ 
\hline
\end{tabular}$

 Профиль  
                  
 
 Re: Обсуждение и разбор марафонских задач
Сообщение26.10.2009, 09:31 
Заслуженный участник


27/06/08
4058
Волгоград
Задача ММ114 утратила статус конкурсной и может свободно обсуждаться на форуме.

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

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

Спорный участок имеет форму правильного треугольника периметром 100 м. Х, отстаивающий свое право собственности, решил для надежности обнести участок забором и приобрел 100 м сетки-рабицы. Но к тому моменту, когда X закупил сетку, состоялся суд, присудивший разделить спорный участок между X и Y. Линия раздела прошла по прямой через центр участка. А Y тут же оградил свою часть. Когда X оградил свою, у него осталось 47 метров неиспользованной сетки.
Найти площади участков, доставшихся X и Y.

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

Решение

Приведу решение Эдварда Туркевича, замечательное своей краткостью.

Разобьем участки, доставшиеся X и Y на треугольники с общей вершиной в центре участка. Поскольку у всех треугольников одинаковые высоты, то площади участков, доставшихся X и Y делятся в том же отношении, что и линия раздела делит периметр всего участка. X не мог повторно оградить линию раздела - нетрудно проверить, что в этом случае он использовал бы не менее 66.(6) м сетки. Линия раздела может делить периметр всего участка в отношении от 4:5 до 5:4. Из соображения непрерывности соотношение 53:47 возможно.

Ответ: $\frac{1325\sqrt3}9, \ \frac{1175\sqrt3}9$

Обсуждение

Сергей Половинкин звметил, что решение, аналогичное приведенному, проходит для многоугольного участка любой формы, при условии, что этот в многоугольник можно вписать окружность. Он же верно догадался, что упоминание вписанной окружности, было явной подсказкой. Справедливость этой догадки подтвердили участники, приславшие верные, но довольно громоздкие решения :)

Награды

За правильное решение задачи ММ114 Сергей Половинкин получает 8 призовых баллов (1 балл добавлен за обобщение задачи), Алексей Волошин, Анатолий Казмерчук, Дмитрий Пашуткин, Эдвард Туркевич, Илья Гермашев, Николай Дерюгин и Виктор Филимоненков получают по 7 призовых баллов.

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

 Профиль  
                  
 
 Re: Обсуждение и разбор марафонских задач
Сообщение27.10.2009, 01:54 
Заслуженный участник


27/06/08
4058
Волгоград
================

Текущее положение участников
в XII туре Математического марафона

$\begin{tabular}{|l|l|r|r|r|r|r|} 
\hline 
№& Участники& 111 & 112 & 113 & 114 & \Sigma \\ 
\hline 
1.& Сергей Половинкин & 3 & 6 & 10 & 8 & 27 \\ 
\hline
2.& Анатолий Казмерчук & 3 & 6 & 10 & 7 & 26 \\ 
\hline
2.& Алексей Волошин & 2 & 6 & 11 & 7 & 26 \\ 
\hline
4.& Виктор Филимоненков & 2 & 6 & 10 & 7 & 25 \\ 
\hline
5.& Николай Дерюгин & 3 & 4 & 9 & 7 & 23 \\ 
\hline
6.& Эдвард Туркевич & 2 & 3 & 8 & 7 & 20 \\ 
\hline
7.& Кирилл Веденский & 0 & 6 & 9 & 0 & 15 \\ 
\hline
8.& Илья Гермашев & 0 & 0 & 0 & 7 & 7 \\ 
\hline
8.& Дмитрий Пашуткин & 0 & 0 & 0 & 7 & 7 \\ 
\hline
10.& Андрей Халявин & 0 & 6 & 0 & 0 & 6 \\ 
\hline
10.& Владислав Франк & 0 & 6 & 0 & 0 & 6 \\ 
\hline
12.& Александр Расстригин & 3 & 0 & 0 & 0 & 3 \\ 
\hline
\end{tabular}$

 Профиль  
                  
 
 Re: Обсуждение и разбор марафонских задач
Сообщение13.11.2009, 17:27 
Заслуженный участник


27/06/08
4058
Волгоград
Задача ММ115 утратила статус конкурсной и может свободно обсуждаться на форуме.

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

Задача ММ15 составлена специально для Математического марафона Сергеем Половинкиным.

Призовые баллы за решение ММ115 учитываются дважды: в тематическом конкурсе и в основном Марафоне.

ММ115 (Ш-3) (10 баллов)

На шахматной доске расставлены кони.
Изображение
Разрешается менять цвет фигур одновременно в клетках на одной вертикали, горизонтали или диагонали (в частности, в одной угловой клетке - считается, что она сама - диагональ). Можно ли получить одноцветный квадрат 5X5 в каком-либо месте доски?

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

Решение

Приведу решение Анатолия Казмерчука (по сути совпадающее с авторским).

Каждый из 16-и квадратов 5х5 содержит одно из четырех множеств полей:
1) b3, b4, c2, c5, d2, d5, e3, e4 (сиреневый восьмиугольник);
2) b5, b6 ,c4, c7, d4, d7, e5, e6 (зеленый восьмиугольник);
3) d3, d4, e2, e5, f2, f5, g3, g4 (желтый восьмиугольник);
4) d5, d6, e4, e7, f4, f7, g5, g6 (синий восьмиугольник).

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

Изображение

Обсуждение

Некоторые участники нашли (в каждом квадрате 5х5) другие конфигурации клеток, обладающие теми же свойствами, что конфигурация, используемая в приведенном решении. А именно:
каждая конфигурация содержащие нечетное число черных коней;
четность числа черных коней, принадлежащих конфигурации, инвариантна относительно допустимых преобразований.
(Для некоторых других квадратов 5х5 конфигурацию на левом рисунке надо повернуть на 90 градусов.)

ИзображениеИзображение

Алексей Волошин показал, что исходная позиция не позволяет получить не только квадрат 5х5, и прямоугольник 4х5 (4 горизонтальных ряда), заполненный одноцветными конями. В то же время, прямоугольник 5х4 (и даже 8х4) получить можно.

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

Награды

За составление (и исследование) задачи ММ115 Сергей Половинкин получает 12 призовых баллов. За правильное решение и обобщение задачи Алексей Волошин получает 11 призовых баллов. За правильное решнеие Анатолий Казмерчук, Эдвард Туркевич и Дмитрий Пашуткин получают по 10 призовых баллов. Николай Дерюгин получает 4 призовых балла, а новичок Марафона SiO2 - 1 призовой балл.

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

Отмечу, что эта задача получила наивысшую оценку участников (Браво, Сергей!) за всю историю Марафона. Задачи, оцененные на 5 баллов, в Марафоне уже были, но те пятерки были "средними арифметическими" одной оценки (максимум двух). Этой же задаче пятерки выставили сразу 5 марафонцев!

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 861 ]  На страницу Пред.  1, 2, 3, 4, 5, 6, 7 ... 58  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group