Задача:
На складе есть N ящиков с товарами, пронумерованных от 1 до N. Известно, что один из ящиков содержит драгоценности, а остальные пустые. Все ящики внешне идентичны, поэтому определить по внешнему виду, в каком из них находятся драгоценности невозможно. Требуется решить задачу с помощью наименьшего количества взвешиваний, используя двухчашечные весы.
Решение:
1. Первым шагом необходимо разделить все ящики на две группы примерно одинакового размера.
2. Положите одну группу на одну чашу весов, а другую группу на другую чашу.
3. Для следующего шага выберите группу, в которой будет находиться ящик с драгоценностями.
4. Разделите выбранную группу на две новые группы примерно одинакового размера и повторите шаги 2-3.
5. Продолжайте делить группы на две новые группы и взвешивать их, пока не найдете ящик с драгоценностями.
Объяснение:
Разделяя группу ящиков на две примерно одинаковых части и взвешивая их, мы эффективно уменьшаем количество возможных ящиков с драгоценностями в два раза на каждом шаге. В результате, после log2(N) шагов мы сможем определить ящик с драгоценностями. Log2(N) – это минимальное количество взвешиваний, необходимое для решения задачи.