|
|
 |
Условие
В каждом из $16$ отделений коробки $4\times 4$ лежит по золотой монете. Коллекционер помнит, что какие-то две лежащие рядом монеты (соседние по стороне) весят по $9$ грамм, а остальные по $10$ грамм. За какое наименьшее число взвешиваний на весах, показывающих общий вес в граммах, можно определить эти две монеты?Решение
Отметим, что взвешивание любой группы монет может показать один из трех исходов: $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)$. Чтобы найти легкие монеты, третьим взвешиванием достаточно взвесить одну из этих пар.
