Определите две тяжелые монеты: олимпиадная задача

Отметим, что взвешивание любой группы монет может показать один из трех исходов: $0$, $1$ или $2$ легкие монеты среди взвешенных. Действительно, эти исходы соответствуют показаниям весов в $10k$, $10k-1$ и $10k-2$ граммов, где $k$ – количество монет на весах, а ничего другого при взвешивании $k$ монет весы показать не могут. Теперь докажем, что менее чем тремя взвешиваниями обойтись не получится. Всего пар монет, которые могут быть легкими, $24$: по $3$ пары соседних монет в каждой строчке и в каждом столбце. Так как одно взвешивание дает три разных исхода, то два взвешивания дадут лишь $3^2 = 9$ различных исходов.

Покажем, как определить легкие монеты за три взвешивания.

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

1. Первый случай (легкие монеты в одной группе), второе взвешивание. Оставим на рисунке только те монеты, которые могут оказаться легкими, разобьем их на две группы и пронумеруем. Взвесим одну из групп. Здесь возможны три случая: обе легкие монеты в группе $A$, обе легкие монеты в группе $B$, по одной легкой монете в каждой из групп.

Хотя в этом взвешивании группы не симметричны, ситуации с обеими монетами в одной группе разбираются аналогично. Возможные пары легких монет: $(X_1, X_2)$, $(X_2, X_3)$ и $(X_3, X_4)$, где $X$ – группа с легкими монетами. Поэтому третьим взвешиванием взвесим монеты $X_1$ и $X_2$. Либо они обе легкие, и тогда мы их нашли, либо среди них одна легкая, и тогда легкие монеты – это $X_2$ и $X_3$, либо среди них легких нет, и тогда легкие монеты – $X_3$ и $X_4$.

Если легкие монеты в разных группах, то это могут быть «горизонтальные» пары $(A_1, B_2)$, $(A_2, B_3)$ или $(A_3, B_4)$. Тогда третьим взвешиванием взвесим монеты $A_1$, $B_2$ и $A_2$. Если среди них две легкие, то это $A_1$ и $B_2$. Если одна, то легкие монеты – это $A_2$ и $B_3$, если легких нет – то $A_3$ и $B_4$. 2) Второй случай (легкие монеты в разных группах), второе взвешивание. Оставим на рисунке только те монеты, которые могут оказаться легкими, разобьем их на две группы и пронумеруем. Взвесим одну из групп. Так как группы симметричны, то возможны два различных случая: легкие монеты в одной группе и легкие монеты в разных группах.

Ситуация, когда обе легкие монеты в одной группе, разбирается точно так же, как и в третьем взвешивании первого случая, но монеты $X_3$ и $X_4$ легкими оказаться не могут.

Если легкие монеты в разных группах, то это либо пара $(A_3, B_4)$, либо пара $(A_4, B_3)$. Чтобы найти легкие монеты, третьим взвешиванием достаточно взвесить одну из этих пар.