Задачи олимпиад по математике

главная страница сайта Приглашение в мир математики
ММ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 подготовлен Алексеем Изваловым.

Задайте вопрос на блоге о математике