Математический факультетИнформация для студентовЭлектронная библиотека
Карта сайтаКарта сайта
Недавние измененияНедавние изменения
ПоискПоиск
  
Вы посетилиВы посетили
История страницыИстория страницы
  
Вход/выходВход


Содержание

ММ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

Вторым измерением 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

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

: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

И в случае нейтрального результата второго измерения на подозрении остаются 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 подготовлен Алексеем Изваловым.


 

 


Страница: [[marathon:problem_126]]

marathon/problem_126.txt · Последние изменения: 2011/01/10 21:22 (внешнее изменение)
Powered by DokuWiki  ·  УКЦ ВГПУ 2006