Question

Наведіть алгоритм вирішення наступного завдання: Вісім куль однакового розміру. Сім з них мають однакову вагу, восьма кулька трохи важче інших. Потрібно знайти цю кульку, виконавши мінімальну кількість зважувань за допомогою чашкових ваг.

Answer 1

Ответ:

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.

Answer 2

Ця задача є класичним завданням на знаходження важчого предмета за допомогою обмеженої кількості зважувань на чашкових вагах. Для вирішення цієї задачі потрібно виконати всього три зважування.

Ось алгоритм:

1. Розділімо восьму кульки на три групи: по три кульки в першій і другій групі, і дві кульки в третій групі.

2. Зважуємо першу і другу групи на чашкових вагах.

   a. Якщо ваги вирівнюються, це означає, що важкі кульки знаходяться в третій групі, і ви перейдете до кроку 3.

   b. Якщо одна з груп важча, це означає, що важка кулька знаходиться в цій групі. Позначте цю групу (позначимо її як "Група А"). Ви знайшли важку кульку і можете завершити задачу.

3. Тепер ми знаємо, що важка кулька знаходиться в третій групі. Розділімо цю групу на дві кульки і взважуємо їх на чашкових вагах.

   a. Якщо ваги вирівнюються, то важка кулька - це одна з кульок, яку ви не взважували в третій групі. Позначте цю кульку як важку і завершите задачу.

   b. Якщо одна з кульок вагча, то ви знайшли важку кульку.

Цей алгоритм гарантує знаходження важкої кульки за трьома зважуваннями.