Задание №176899: Турнир городов

3) Перевесила «белая» чашка. Тогда одна фальшивая монета – на «чёрной» чашке.
Поэтому центральная монета настоящая. И все 12 белых монет тоже.
Обобщение. Отложим любую чёрную монету A и всех её соседей по диагонали. Из
оставшихся чёрных монет положим на одну чашу не менее 7, а на другую – столько же
белых. При равновесии все монеты на весах настоящие (их не меньше 14). Если
перевесят чёрные, то все чёрные монеты настоящие, а если белые, то все белые и A.
Способ 2. Положим на чаши 4 чёрные монеты, соседние с центральной, левые – на
левую, правые – на правую. При равновесии все чёрные монеты настоящие (так как две
фальшивые чёрные монеты не могут быть ни на разных чашах, ни обе вне чаш). Если
какая-то чаша перевесит, то настоящие – две монеты на этой чаше и все белые монеты.

б) Способ 1. Взвесим чёрные монеты
против белых на рисунке слева. В
случае равновесия 15 монет в нижних
трёх строках настоящие. Если чёрные
монеты тяжелее, не взвешиваемая
фальшивая монета может находиться только в квадратах, отмеченных крестиками на рис.

в центре. Следовательно, мы нашли 25 – 5 – 5 = 15 настоящих монет. Если белые
монеты тяжелее, ситуация показана на рисунке справа с тем же результатом.


Способ 2. Взвесим чёрные монеты
против белых на левом рисунке. В
случае равновесия все 16
взвешиваемых монет настоящие. Если
чёрные монеты тяжелее, не
взвешиваемая фальшивая монета может находиться только в двух квадратах,
отмеченных крестиками на центральном рисунке. Таким образом, найдены 25 – 8 – 2 = 15
настоящих монет. Если белые монеты тяжелее, получим тот же результат (правый
рисунок.

Способ 3. Из пятой строки две белые монеты положим на левую чашку, две чёрные – на

правую, а одну монету отложим. Остальные белые – на правую, чёрные – на левую
чашку.
При равновесии все монеты из первых трёх строк настоящие. Если какая-то чашка
перевесит, то настоящие – все 12 монет на ней и все монеты из пятой строки (итого 15
монет).

в) Априори любая из 25 монет подозрительна (может быть фальшивой). Взвешивание
может иметь 3 исхода, поэтому хотя бы при одном из них подозрительными останутся не
меньше 9 монет, то есть будет найдено не более 25 – 9 = 16 настоящих монет.

Замечание. Докажем, что даже 16 настоящих монет гарантированно найти нельзя.
Рассмотрим граф: вершины – клетки, рёбра соединяют пары клеток, имеющих

единственную общую вершину. Он распадается на две компоненты – чёрную и белую.
Взвешивание – разбиение вершин на три части: П – монеты на правой чашке, Л – на
левой, С – монеты на столе. В случае равновесия подозрительными остаются рёбра вида
ЛП и CC, покрасим их в красный цвет. Если перевесит правая чашка, подозрительны
ребра ЛЛ и ЛС (покрасим их в синий), если левая – ПП и ПС (в зелёный).
Пусть при любом исходе удаётся определить 16 настоящих монет. Тогда подграф,
порождённый рёбрами каждого цвета, должен содержать не более 9 вершин. Значит, есть
вершины, в которых сходятся разные цвета. Пусть в белой компоненте такая вершина
единственна. Удалив её со всеми входящими рёбрами, получим связный граф на 11
вершинах, который не может иметь все рёбра одного цвета. Противоречие.
Следовательно, в белой компоненте хотя бы две «нехороших» вершины. Аналогичное

верно и для чёрной компоненты.
Оценим двумя способами суммарное число вершин во всех трёх указанных подграфах. С
одной стороны, их не больше 3·9 = 27, с другой – не меньше чем 25 + 2 + 2 («нехорошие
вершины» подсчитаны как минимум дважды). Противоречие.

Базовый вариант, 10–11 классы