27 сентября 2010

Разбор задачи ММ126 математического марафона

ММ126 (4 балла)

Есть 8 шаров, среди которых 6 заряжены нейтрально, один - положительно и один - отрицательно. Есть прибор, который, будучи поднесённым к группе шаров, покажет их общий заряд (он покажет 0 и если в группе нет ни одного заряженного шара, и если они там оба).
За какое наименьшее число измерений можно найти положительный и отрицательный шары в группе?

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

Решение

Сначала оценим снизу необходимое число измерений. Поскольку вариантов выбора положительного и отрицательного шара из 8 будет $8\cdot 7 = 56$, а одно измерение может сократить количество вариантов не более чем втрое, то менее чем за $\lceil\log_3{56}\rceil=4$ измерения задачу решить нельзя.

Первое измерение нужно спланировать так, чтобы при каждом его исходе оставалось не более 27 вариантов.

Если выбрать для него 1 или 2 шара, прибор покажет 0 в 42 или в 32 случаях. При выборе трёх шаров для первого измерения (скажем, шары 1, 2 и 3), нейтральный заряд будет зафиксирован в 26 случаях, ещё по 15 вариантов распределения зарядов среди шаров дадут положительное и отрицательное показания. Эти случаи удобно рассмотреть в виде таблицы. Кадая её ячейка – это показание прибора в случае возможной пары шаров, заряженных положительно (по вертикали) и отрицательно (по горизонтали).

Изображение

Вторым измерением 26 вариантов, давших нейтральное показание, нужно разбивать на 9+9+8.

Покажем, что это невозможно. Включения шаров из групп 1-3 и 4-8 независимо влияет на количества возможных показаний прибора. Если из шаров 1-3 выбрать в измеряемую группу 0 или 3 шара, то среди исходов измерения 6 раз встретится 0, и ни разу – плюс или минус. Для краткости запишем это так: 0 (-), 0 (+), 6 (0). Если же выбрать 1 или 2 шара, то среди исходов будут 2(-), 2(+), 2 (0)

Если из шаров 4-8 для измерения брать 0 или 5 шаров, то среди сиходов будут 0 (-), 0 (+), 20 (0). Если брать 1 или 4 шара, то 4 (-), 4 (+), 12 (0). И 2 или 3 шара, включённые в измеряемую группу, покажут 6(+), 6(-), 8(0).

Таким образом, наилучшее, чего можно добиться вторым измерением – это разбитие 26 вариантов на 8+8+10, выбрав, к примеру, 1, 7 и 8 шары

Изображение

Значит, измерение первым действием трёх шаров к цели за 4 шага не приведёт. Попробуем измерить сначала 4 шара. Получаем следующее распределение исходов:

Изображение

Довольно перспективный расклад: 16(+), 16(1), 24(0). Более того, в случае нейтрального результата в измерении 1, вторым замером эти 24 варианта разбиваются на 8+8+8 (и только так, расклады 9+9+6 и 9+8+7 невозможны), взяв шары №№3, 4, 5, 6.

Изображение

И в случае нейтрального результата второго измерения на подозрении остаются 8 упорядоченных пар (положительный шар; отрицательный шар): (1;2), (2;1), (3;4), (4;3), (5;6), (6;5), (7;8), (8;7), Их можно разделить на 3+3+2, замерив шары 1, 3, 5. В таком случае прибор покажет:
«+» при (1;2), (3;4) или (5;6) – здесь для 4го измерения выберем пару №№1,4,
«–» - при (2;1), (4;3) или(6;5) – и здесь тоже,
и «0» при (7;8) или (8;7) – а тут достаточно узнать знак шара №8.

Итак, оставшимся четвёртым измерением можно однозначно найти искомые заряды.

Но в случае положительного результата второго измерения на подозрении будут такие 8 пар:
(3;1), (3;2), (4;1), (4;2), (5;7), (5;8), (6;7), (6;8). Применив соображения, аналогичные доказательству невозможности разбить 26 вариантов на 9+9+8, приходим к выводу, что невозможно выбрать такую группу шаров, чтобы третьим измерением разбить эти 8 вариантов на 3+3+2.

Таким образом, 4 измерения может и не хватить. Построим метод, дающий гарантированный результат за 5 замеров. В текущей ветке 8 вариантов легко разделить трёхкратной дихотомией.

В случае же, если после первого замера будет ненулевй исход (скажем, «+»), положительный шар находится среди 4 шаров, а отрицательный – среди остальных 4 шаров. На нахождение каждого дихотомией потребуется по 2 замера – итого в 5 укладываемся.

Обсуждение

Собственно задачу я сформулировал как модификацию известной задачи о поиске радиоактивных шаров. Введение зарядов, с одной стороны, удваивает возможные расположения шаров для заданного n, а с другой – предоставляет возможность каждым измерением делить это количество не на 2, а на 3.
Однако из-за того, что не непосредственно разделяем созможные варианты ответа на группы, а посредством выбора некоторой группы шаров, точное деление на 3 оказывается возможным далеко не всегда. И основной сложностью в этой задаче является именно доказательство невозможности уложиться в 4 измерения. При этом ветка, показывающая невозможность начинается после нулевого результата первого измерения и ненулевого - второго, а не после обоих нулевых результатов, как писали некоторые участники марафона.

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

Напрашивается обобщение задачи: за сколько измерений можно найти положительный и отрицательный шар для произвольного общего количества шаров n?

Оценкой снизу для искомой функции $f_2(n)$ будет $\lceit log_3n(n-1)\rceil$, сверху в первом приближении можно взять n-1 – достаточно проверить все шары, кроме одного.

Для небольших n можно построить таблицу:
\displaystyle \begin{array}{|c|c|} \hline \mathrm {n} & \mathrm {f_2(n)} \\ \hline \mathrm {2} & \mathrm {1} \\ \hline \mathrm {3} & \mathrm {2} \\ \hline \mathrm {4} & \mathrm {3} \\ \hline \mathrm {5} & \mathrm {3} \\ \hline \mathrm {6} & \mathrm {4} \\ \hline \mathrm {7} & \mathrm {4} \\ \hline \mathrm {8} & \mathrm {5} \\ \hline \mathrm {9} & \mathrm {5} \\ \hline \mathrm {10} & \mathrm {5} \\ \hline \mathrm {11} & \mathrm {5} \\ \hline \mathrm {12} & \mathrm {6} \\ \hline \end{array}

Сергей Половинкин, помимо таблицы, строит алгоритм нахождения заряженных шаров для произвольного n и показывает, что $f_2(n)=[ \log_2 n ] + [ \log_2 \frac n3 ] + 1$.
Я предлагаю создать отдельную тему для обсуждения алгоритмов решения этой и аналогичных задач, опубликовав полный алгоритм там

Награды

Виктор Филимоненков и Алексей Волошин за правильное решение задачи получают по 4 балла. Сергей Половинкин, проведя очень интересное обобщение, в доказательстве невозможности решить текущую задачу за 4 измерения, привёл пример ветки, которая на самом деле за 4 измерения решается. Таким образом, он получает 3+2 (бонус за развитие темы)=5 баллов. Анатолий Казмерчук получает 3 балла, Эдвард Туркевич получает 2 балла, Николай Дерюгин и Евгений Гужавин получают по 1 баллу.

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

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

Разбор задачи ММ126 подготовлен Алексеем Изваловым.
0 comments
Labels: , ,

Разбор задачи ММ125 математического марафона

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

Оценка за решение задачи ММ125 учитывается дважды в основном Марафоне и в тематическом конкурсе.

ММ125 (КГ-8) (4 балла)

Верно ли, что группа автоморфизмов структурного графа любого n-угольника изоморфна подгруппе группы диэдра n-й степени?

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

Решение

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

Рассмотрим правильный (можно любой выпуклый, но так удобнее) пятиугольник ABCDE. Точку пересечения диагоналей BD и CE обозначим через A', точку пересечения AD и CE - через B', и т. д.
У структурного графа пятиугольника ABCDE есть пять автоморфизмов, соответствующих поворотам и пять автоморфизмов, соответствующих отражениям пятиугольника. Каждый из них внешние вершины переводит во внешние, а внутренние - во внутренние. Но кроме этого, существует "выворачивающий" автоморфизм, который меняет местами вершины A и A', B и B', C и С', D и D', E и E'. В композиции с поворотами и отражениями это даёт ещё десять автоморфизмов. Итого - 20 автоморфизмов, в то время как группа диэдра 5-й степени содержит всего 10 элементов.

Обсуждение

Группа автоморфизмов структурного графа пятиугольника является единственным исключением. Для остальных многоугольников ответ на вопрос задачи положителен. Это следует из того, что при n, отличном от 5, любой автоморфизм структурного графа выпуклого n-угольника задает автоморфизмом циклического подграфа, образованного вершинами, соответствующими вершинам исходного многоугольника, и, в свою очередь, однозначно определен автоморфизмом этого подграфа. Рассуждение такого рода содержится в решении Анатолия Казмерчука. Однако Анатолий исходил из неверного тезиса об обязательном изоморфизме групп автоморфизмов структурного и сопровождающего графов и поэтому прозевал случай n = 5.
Отмечу, что, кроме упомянутого случая n = 5, группы автоморфизмов структурного и сопровождающего графов выпуклого n-угольника не изоморфны еще и при n = 3.

Задача ММ125 оказалась в некотором смысле парадоксальной. Я считал ее весьма легкой (это отражено и в цене задачи). Мое мнение, с одной стороны, подтверждается мнениями ряда участников Марафона, отметивших простоту ММ125, а с другой стороны, опровергается количеством марафонцев, осиливших эту задачу.

Награды

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

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

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

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

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

Текущее положение участников
в XIII туре Математического марафона
$\begin{tabular}{|l|l|r|r|r|r|r|r|} \hline №& Участники& 121 & 122 & 123 & 124 & 125 & \Sigma \\ \hline 1.& Алексей Волошин & 8 & 4 & 3 & 4 & 4 & 23 \\ \hline 1.& Анатолий Казмерчук & 8 & 4 & 5 & 4 & 2 & 23 \\ \hline 3.& Сергей Половинкин & 8 & 4 & 5 & 2 & 0 & 19 \\ \hline 4.& Николай Дерюгин & 6 & 4 & 5 & 2 & 0 & 17 \\ \hline 5.& Виктор Филимоненков & 0 & 0 & 5 & 4 & 4 & 13 \\ \hline 6.& Эдвард Туркевич & 0 & 0 & 5 & 4 & 0 & 9 \\ \hline 6.& Дмитрий Пашуткин & 0 & 0 & 5 & 0 & 4 & 9 \\ \hline 8.& Евгений Машеров & 0 & 0 & 3 & 2 & 0 & 5 \\ \hline 9.& Mathusic & 0 & 0 & 0 & 4 & 0 & 4 \\ \hline \end{tabular}$
0 comments
Labels: , ,

Разбор задачи ММ124 математического марафона

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

ММ124 (4 балла)

Пусть S_n = 2 + 3 + 5 + 7 +\dots+ p_n - сумма n первых простых чисел.
Доказать, что S_n является простым тогда и только тогда, когда существует такое простое число q, что S_n + q кратно 2, 3, 5, \dots, p_n.

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

Решение

Приведу решение Виктора Филимоненкова.

1. Пусть такое число q для $S_n$ существует. Тогда $S_n$ не делится ни на одно из чисел $2, 3, \dots, p_n$. Действительно, если $S_n = p \cdot b$, где p - одно из первых n простых, и $S_n + q$ кратно p, то и q кратно p, а поскольку q простое, то q = p. Тогда $S_n + q = p*(b+1)$ - делится на $2\cdot 3\dots p_n$, в то время как $p\cdot b = 2+3+...+p_n$. То есть сумма n чисел, не меньших 2, лишь на одно слагаемое меньше их произведения, что для суммы первых протсых чисел, очевидно, не верно начиная с $S_3$ (для $S_1$ и $S_2$ утверждение доказывается непосредственно).

Но раз $S_n$ не делится на $2, 3, \dots, p_n$, то оно простое. Действительно, $S_n < n\cdot p_n$, а поскольку $n < p_n$, то $S_n$ не делится на все простые, меньшие квадратного корня из $S_n$, то есть простое.

2. Пусть, наоборот, $S_n$ простое. Покажем, что простое q существует. Рассмотрим арифметическую прогрессию с первым членом $-S_n$ и разностью $2 \cdot 3 \dots p_n$. Поскольку $S_n$ простое, то оно взаимно просто с $2 \cdot 3 \dots p_n$, и значит в этой прогрессии, по теореме Дирихле, есть бесконечное количество простых чисел. Любое из них годится в качестве q.

Обсуждение

Для меня было неожиданностью, что ряд опытных, искушенных марафонцев испытывали некоторые затруднения при решении этой, на мой взгляд, простой задачи. (Конечно, теорема Дирихле о простых числах в арифметической прогрессии - утверждение нетривиальное. Но зато широко известное :)). При желании, я мог придраться к большему числу решений. Читая утверждения типа "составное число, меньшее $p^2$, не может иметь делителей, больших p", я был близок к "кровопролитию". Но сдержался :)

В OEIS последовательность простых $S_n$ представлена под номером A013918.

Интересно, конечно ли множество n, для которых $S_n$. Интуиция подсказывает, что:
1) бесконечно;
2) доказательство первого пункта нетривиально :)

Награды

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

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

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

Обзор задачи ММ124 подготовлен Владимиром Лецко
0 comments
Labels: ,

18 сентября 2010

Разбор задачи ММ123 математического марафона

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

MM123 (5 баллов)

Квадратная монета со стороной 1 см бросается случайным образом на лист бумаги, разлинованный квадратными клетками со стороной 2 см. Какая вероятность того, что монета попадёт целиком в клетку?

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

Решение
Бросание монеты можно описать математически как случайный выбор пары координат x и y, а также угла поворота монеты $\alpha$

Понятно, что можно рассмотреть один квадрат со стороной 2 и координаты центра (точки пересечения диагоналей) монеты будут принимать значения от 0 до 2.
Выразим вероятность попадания монеты в ячейку от угла $\alpha$, который образует её сторона с горизонтальной линией разметки.
Всилу симметрии угол $\alpha$ можно выбирать из диапазона от 0 до $\frac{\pi}{4}$.

При угле $\alpha$ монету можно вписать в квадрат, со сторонами, параллельными сторонам ячейки и равными $\sin\alpha+\cos\alpha$ (такую картинку можно видеть в индийском доказательстве теоремы Пифагора). Центр этого квадрата совпадает с центром монеты. Пересечение описанного вокруг монеты квадрата с ячейкой равносильно пересечению самой монеты с ячейкой.

Решение задачи о бросании квадратной монеты

"Бесконфликтная" область для центра монеты будет иметь форму квадрата, расположенного в центре ячейки. Сторона этого квадрата составит $2-\sin\alpha-\cos\alpha$. Тогда вероятность того, что при данном угле $\alpha$ монета попадёт целиком в ячейку, равна отношению площадей "бесконфликтного" квадрата и всей ячейки$\frac{(2-\sin\alpha-\cos\alpha)^2}{4}$

Взяв среднее интегральное этой дроби по $\alpha$ от 0 до $\frac{\pi}{4}$ получим вероятность $\int\limits_{0}^{\frac{\pi}{4}}\frac{(2-\sin\alpha-\cos\alpha)^2}{4} \text{d}\alpha = \frac{5}{4}-\frac{7}{2\pi}\approx0,136$

Обсуждение

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

Ещё одна ассоциация с этой задачей - вычисление числа пи, бросая иголку на паркетный пол.

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

Ещё одна причина, не позволившая одному из участников набрать максимальное количество баллов - выбор таких пределов интегрирования $\alpha$, при которых учитывается возможность пересечения с ячейкой только одной диагонали монеты.

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

Собственно задача рождается, если, решив аналогичную задачу о бросании круглой монеты, задуматься: а что будет, если монета квадратная?

Награды

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

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


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

Обзор задачи ММ123 подготовлен Алексеем Изваловым
0 comments
Labels: , ,
Подписаться на: Сообщения (Atom)