I) Для начала рассмотрим случай, когда весы никогда не врут.
Пронумеруем шары и расположим их в таблице 3x3:
Все взвешивания будем производить таким образом: разбиваем шары на 3 группы по 3 шара в каждом, на одну чашку весов кладём первую группу, на другую — вторую, а третью группу оставляем.
Одно взвешивание определяет, в какой группе лёгкий шар: если весы в равновесии, то в третьей, иначе — в легчайшей.
Если сначала взвесить шары по строкам таблицы: (1, 2, 3), (4, 5, 6), (7, 8, 9), а затем по столбцам: (1, 4, 7), (2, 5, 8), (3, 6, 9), то видим, что эта пара взвешиваний даст нам строку и столбец, в котором находится лёгкий шар, т.е. однозначно его определит.
II) Проанализируем, что дало нам такой замечательный результат. Его дало нам то свойство, что каждая группа первого взвешивания пересекается с каждой группой второго взвешивания ровно по одному шару. Назовём это свойство "ортогональностью" пары взвешиваний.
Вспоминая, как считается определитель матрицы 3x3, мы можем легко представить ещё одну ортогональную пару взвешиваний:
(1, 5, 9), (2, 6, 7), (3, 4, 8)
и
(1, 6, 8), (2, 4, 9), (3, 5, 7).
Оказывается, они ортогональны не только друг другу. Все четыре выписанных взвешивания попарно ортогональны, а значит, любая пара из этих четырёх позволит нам определить лёгкий шар при условии, что весы не врут.
III) Что же будет, если одно из взвешиваний пары врёт? Поскольку теперь мы неправильно определим группу, в которой находится лёгкий шар, мы обязательно определим лёгкий шар неправильно. Случайного правильного определения быть не может.
IV) Теперь рассмотрим исходную задачу с четырьмя выписанными взвешиваниями. Будем удалять из этой четвёрки по одному взвешиванию и анализировать оставшиеся три. Если мы удалили неправильное взвешивание, то осталось три правильных, и какую бы пару из них мы ни взяли, получится один и тот же шар, и этот шар действительно будет легчайшим. Если же мы удалили правильное взвешивание, то у нас остаётся одно неправильное взвешивание и два правильных. Проанализируем попарно все три взвешивания. Пара правильных взвешиваний даст нам правильный шар в то время как любая другая пара (неправильное+правильное) обязательно даст другой шар (см. п. III). По этой несогласованности мы и определим, что данная тройка взвешиваний содержит неправильное. Единственная согласованная тройка даст нам правильный ответ.
19.10.2014, 15:19 
