Какое минимальное количество взвешиваний позволит определить, какая пара наклеек была поменяна местами, если есть

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

Карамель

Для решения данной задачи нам понадобится использовать метод двоичного поиска.

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

Действуем следующим образом:
1. Разделяем все гири на две равные группы по 4 гири в каждой и называем их группа A и группа B. Взвешиваем эти две группы.

Если взвешивание показывает, что группы A и B имеют одинаковый вес, значит пара гирь, которую ищем, находится в оставшихся 4-х неразличимых гирах.

2. Разделяем оставшиеся 4 гири на 2 группы по 2 гири в каждой и называем их группа C и группа D. Взвешиваем эти две группы.

Если взвешивание показывает, что группа C легче, значит пара гирь, которую ищем, находится в группе C.

3. Разделяем группу C на две гири и называем их Ci и Cj. Взвешиваем гири Ci и Cj.

Если взвешивание показывает, что гиря Ci легче, значит гиря Ci была поменяна местами с другой гирей.

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

Итак, у нас есть 1 взвешивание групп A и B, 1 взвешивание групп C и D, а затем еще 1 взвешивание гирь Ci и Cj. Таким образом, минимальное количество взвешиваний, позволяющее определить пару гирь, которая была поменяна местами, равно 3.

Поэтому, результатом является число 3.
Знаешь ответ?
Задать вопрос
Привет!
hello