Как найти минимальное количество взвешиваний для определения тяжелого шарика?

Что проверяют

Логику и умение уточнить условия до решения: точно ли тяжёлый шарик один, известно ли, что он именно тяжелее, нет ли у весов гирь. Для тестировщика это ещё и проверка, перебираете ли вы граничные случаи. Следом просят объяснить, почему групп три, а не две.

Как отвечать

Условие по умолчанию: чашечные весы без гирь, шариков n, ровно один тяжелее остальных.

Ключевая мысль: у взвешивания три исхода, а не два. Левая чаша тяжелее, правая тяжелее или равновесие. Значит, каждое взвешивание сокращает число кандидатов втрое:

• алгоритм: делите шарики на три группы так, чтобы на чашах лежало поровну, а третья группа была не больше них. Перевес указывает на группу, равновесие на ту, что лежит в стороне;
• формула: минимум взвешиваний равен ceil(log3(n)). Для 3 шариков одно, от 4 до 9 два, от 10 до 27 три, от 28 до 81 четыре;
• нижняя граница: за k взвешиваний можно различить не больше 3^k исходов, поэтому быстрее не выйдет ни при какой стратегии;
• неровное число: 8 шариков раскладываются как 3, 3 и 2. Если 3 против 3 в равновесии, остаются два, и второе взвешивание 1 против 1 решает задачу. Если перевес, из трёх кладёте на чаши два.

Проверьте ответ вслух на маленьких n: одному шарику нужно ноль взвешиваний, двум одно, трём тоже одно. Интервьюеры ценят это больше, чем выученную формулу.

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

Где спотыкаются

Делят пополам и получают log2(n). Для 8 шариков выходит три взвешивания вместо двух, потому что исход «равновесие» не используется.

Кладут на чаши неравное количество шариков. Тогда перевес ничего не говорит.

Не уточняют условие. Задача про «тяжелее» и задача про «отличается» решаются по-разному, и молчаливое допущение выглядит как невнимательность.