===== ММ126 =====
**Конкурсная задача ММ126** (4 балла)
Есть 8 шаров, среди которых 6 заряжены нейтрально, один - положительно и один - отрицательно. Есть прибор, который, будучи поднесённым к группе шаров, покажет их общий заряд (он покажет 0 и если в группе нет ни одного заряженного шара, и если они там оба).
За какое наименьшее число измерений можно найти положительный и отрицательный шары в группе?
**Решение**
Сначала оценим снизу необходимое число измерений. Поскольку вариантов выбора положительного и отрицательного шара из 8 будет 8*7 = 56, а одно измерение может сократить количество вариантов не более чем втрое, то менее чем за ceil(log3(56)) = 4 измерения задачу решить нельзя.
Первое измерение нужно спланировать так, чтобы при каждом его исходе оставалось не более 27 вариантов.
Если выбрать для него 1 или 2 шара, прибор покажет 0 в 42 или в 32 случаях. При выборе трёх шаров для первого измерения (скажем, шары 1, 2 и 3), нейтральный заряд будет зафиксирован в 26 случаях, ещё по 15 вариантов распределения зарядов среди шаров дадут положительное и отрицательное показания. Эти случаи удобно рассмотреть в виде таблицы. Кадая её ячейка - это показание прибора в случае возможной пары шаров, заряженных положительно (по вертикали) и отрицательно (по горизонтали).
{{:marathon:mm126-1.png|:marathon:mm126-1.png}}
Вторым измерением 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 шары
{{:marathon:mm126-2.png|:marathon:mm126-2.png}}
Значит, измерение первым действием трёх шаров к цели за 4 шага не приведёт. Попробуем измерить сначала 4 шара. Получаем следующее распределение исходов:
{{:marathon:mm126-3.png|:marathon:mm126-3.png}}
Довольно перспективный расклад: 16(+), 16(1), 24(0). Более того, в случае нейтрального результата в измерении 1, вторым замером эти 24 варианта разбиваются на 8+8+8 (и только так, расклады 9+9+6 и 9+8+7 невозможны), взяв шары №№ 3, 4, 5, 6.
{{:marathon:mm126-4.png|:marathon:mm126-4.png}}
И в случае нейтрального результата второго измерения на подозрении остаются 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 укладываемся.
**Обсуждение**
Собственно задачу я сформулировал как модификацию известной задачи о поиске радиоактивных шаров (http://intelmath.narod.ru/radiation.html). Введение зарядов, с одной стороны, удваивает возможные расположения шаров для заданного n, а с другой - предоставляет возможность каждым измерением делить это количество не на 2, а на 3.
Однако из-за того, что не непосредственно разделяем созможные варианты ответа на группы, а посредством выбора некоторой группы шаров, точное деление на 3 оказывается возможным далеко не всегда. И основной сложностью в этой задаче является именно доказательство невозможности уложиться в 4 измерения. При этом ветка, показывающая невозможность начинается после нулевого результата первого измерения и ненулевого - второго, а не после обоих нулевых результатов, как писали некоторые участники марафона.
Интересным был подход рассмотреть задачу как систему линейных уравнений с 8 неизвестными, в которую каждое новое измерение добавляет уравнение. Однако автор решения не учёл, что сами переменные могут принимать только 3 допустимых значения.
Напрашивается обобщение задачи: за сколько измерений можно найти положительный и отрицательный шар для произвольного общего количества шаров n?
Оценкой снизу для искомой функции f2(n) будет ceil(log3n(n-1)), сверху в первом приближении можно взять n-1 - достаточно проверить все шары, кроме одного.
Для небольших n можно построить таблицу:
^ n ^ f2(n)} ^
| 2 | 1 |
| 3 | 2 |
| 4 | 3 |
| 5 | 3 |
| 6 | 4 |
| 7 | 4 |
| 8 | 5 |
| 9 | 5 |
| 10 | 5 |
| 11 | 5 |
| 12 | 6 |
Сергей Половинкин, помимо таблицы, строит алгоритм нахождения заряженных шаров для произвольного n и показывает, что f2(n)=[log2n] + [log2n/3] + 1.
Я предлагаю создать отдельную тему для обсуждения алгоритмов решения этой и аналогичных задач, опубликовав полный алгоритм там
**Награды**
Виктор Филимоненков и Алексей Волошин за правильное решение задачи получают по 4 балла. Сергей Половинкин, проведя очень интересное обобщение, в доказательстве невозможности решить текущую задачу за 4 измерения, привёл пример ветки, которая на самом деле за 4 измерения решается. Таким образом, он получает 3+2 (бонус за развитие темы)=5 баллов. Анатолий Казмерчук получает 3 балла, Эдвард Туркевич получает 2 балла, Николай Дерюгин и Евгений Гужавин получают по 1 баллу.
**Эстетическая оценка задачи 4.4**
Обзор задачи ММ126 подготовлен Алексеем Изваловым.
----