Наведіть алгоритм вирішення наступного завдання:
Вісім куль однакового розміру. Сім з них мають однакову вагу, восьма кулька трохи важче інших. Потрібно знайти цю кульку, виконавши мінімальну кількість зважувань за допомогою чашкових ваг.
Ответы
Ответ:
1) Разделить шары на 3 группы. Группа 1: 3ш, Группа 2: 3ш, Группа 3: 2ш.
2) Взвесить первую группу и узнать, сбалансирован ли вес.
3) Взвесить вторую группу и узнать, сбалансирован ли вес.
4) Взвесить третью группу и узнать, сбалансирован ли вес.
5) Найти группу, где вес не сбалансирован.
6) Возьмите не сбалансированную группу
7.1) Если группа из 3 шаров: возьмите еще 1 шар из сбалансированной группы и разделите эту группу на 2 группы (по 2 шара). Взвесьте обе группы и определите группу с тяжелым шаром. Затем в группе с тяжелым шаром замените любой из шаров на шар в сбалансированной группе. Если после этого вес стал сбалансированным, то замененный шар и является тяжелым. Если вес все еще не сбалансирован, значит оставшийся после замены шар является тяжелым.
7.2) Если группа из 2 шаров, возьмите 1 шар из сбалансированной группы и положите на весы вместо любого из шаров. Если после этого вес стал сбалансированным, то замененный шар и является тяжелым. Если вес все еще не сбалансирован, значит оставшийся после замены шар является тяжелым.
8) Минимальные взвешивания: 4 (если группа из двух шаров) и 6 (если группа из 3 шаров).
Примечание:
Если разделить 8 шаров на 4 группы по 2 шарика, то минимальное количество взвешиваний будет равным 5. Если мы будем взвешивать шары по 3 шара в группе, то может так случится, что мы наткнемся на тяжелый шар, который будет в группе из двух шаров, из-за этого минимальное количество взвешиваний будет 4.