Зимний турнир Архимеда 2024 · 6–7 кл., №2.1

Условие

Монеты. Коробка с монетами разделена на ячейки, как показано на рисунке. В каждой ячейке лежит одна монета. Часть монет настоящие, а остальные фальшивые. Все настоящие монеты имеют одинаковую массу, все фальшивые — тоже, но фальшивая монета легче настоящей. Все монеты внешне не различимы.

Если в ячейке лежит настоящая монета, то такая ячейка имеет общую сторону ровно с двумя ячейками с настоящими монетами. Возможно ли за два взвешивания на чашечных весах без гирь найти все настоящие монеты (на каждую чашу весов можно положить не более одной монеты)? Если да, объясните, как это сделать, если нет, объясните почему.

Рисунок к условию

О задаче

Олимпиада: Турнир Архимеда, XXXIII зимний турнир
Предмет / классы: Математика · 6–7 классы, единый вариант
Дата: 21 января 2024

Исследуй задачу

Самостоятельное исследованиеДва взвешивания

Пробуй свои варианты. Разбор останется закрытым.

Попробуй обмануть противника

Два взвешивания

Выбери, какие монеты положить на весы. Хитрый противник ещё не решил, где настоящие монеты, и отвечает так, чтобы подходящих раскладок осталось как можно больше. Найди два взвешивания, после которых останется одна раскладка, а потом проверь, что способ работает и при других ответах весов.

Без JavaScript модель не работает. Нарисуй все раскладки настоящих монет и проверь свои взвешивания по таблице из разбора.

Здесь нужно доказательство. Сначала выясни, как вообще могут лежать настоящие монеты — вариантов немного. Потом попробуй в модели «Два взвешивания»: придумай взвешивания, которые не обманет даже хитрый противник.

Здесь ответ — «можно» и способ взвешивания. Подходит любой верный способ: проверь свой в модели «Два взвешивания».

Записать идею

Личный черновик для заметок и расчётов. Он никуда не отправляется и не проверяется.

Подсказка 1

Разбери два случая: центральная монета настоящая или фальшивая. У центральной ячейки четыре соседа, а у угловой — только два. Найди все раскладки настоящих монет, подходящие под правило.

Подсказка 2

Раскладок пять: четыре квадрата $2\times 2$ и кольцо из восьми монет вокруг центра. Посмотри на угловые монеты: в каждом квадрате ровно одна угловая, в кольце — все четыре. Что можно узнать, если положить угловые монеты на весы?

Разобрать решение по шагам

Центральная монета настоящая

Тогда среди её четырёх соседей (средних монет сторон) ровно две настоящие.

Могут ли это быть две противоположные, например верхняя и нижняя средние? У верхней средней монеты соседи — центр и два верхних угла, и ей нужен ещё ровно один настоящий сосед, скажем левый верхний угол. Но у левого верхнего угла соседи — верхняя средняя и левая средняя, значит, левая средняя тоже настоящая. Тогда у центра три настоящих соседа — противоречие.

Значит, две настоящие соседки центра — на соседних сторонах, например верхняя и левая. Верхней средней нужен ещё один настоящий сосед: левый или правый верхний угол. Правый не подходит: у него остался бы только один настоящий сосед, ведь правая средняя фальшивая. Значит, левый верхний угол настоящий, и получается квадрат $2\times 2$ в левом верхнем углу. Остальные монеты фальшивые: у левой средней уже есть два настоящих соседа (центр и левый верхний угол), значит, левый нижний угол фальшивый; у правого нижнего угла оба соседа фальшивые, значит, и он фальшивый. Проверка: у каждой из четырёх его монет ровно два настоящих соседа. Так же получаются квадраты в трёх других углах.

Центральная монета фальшивая

Тогда у средней монеты стороны настоящими соседями могут быть только два угла рядом с ней. Если она настоящая, оба этих угла тоже настоящие. А у угла всего два соседа — две средние монеты сторон; если угол настоящий, обе они настоящие.

По этой цепочке одна настоящая монета делает настоящими все восемь монет вокруг центра: получается кольцо. У каждой монеты кольца ровно два настоящих соседа — подходит. Случай «все монеты фальшивые» исключён условием: часть монет настоящие.

Итак, возможных раскладок ровно пять: четыре квадрата и кольцо.

Все пять раскладок, подходящих под правило: четыре квадрата

2\times 2

и кольцо.

Что отличает раскладки

Как это заметить: посмотрим на угловые монеты. В каждом квадрате $2\times 2$ ровно одна угловая монета — свой угол у каждого квадрата. В кольце настоящие все четыре угла. Значит, достаточно узнать, какой угол настоящий, или что настоящие все.

Сравним на весах противоположные углы:

1-е взвешивание: левый верхний угол против правого нижнего;
2-е взвешивание: правый верхний угол против левого нижнего.

Каждый исход — своя раскладка

Настоящая монета тяжелее фальшивой. Распишем, что покажут весы:

раскладка	1-е взвешивание	2-е взвешивание
квадрат слева вверху	левая чаша тяжелее	равновесие
квадрат справа внизу	правая чаша тяжелее	равновесие
квадрат справа вверху	равновесие	левая чаша тяжелее
квадрат слева внизу	равновесие	правая чаша тяжелее
кольцо	равновесие	равновесие

Все пять строк разные. Значит, по двум взвешиваниям мы точно узнаем раскладку, а с ней и все настоящие монеты. Ответ: да, можно.

Проверка

Почему пары монет нужно выбирать с умом: если сначала сравнить угол с соседней средней монетой (например, левую верхнюю с верхней средней), хитрый противник ответит «равновесие». Тогда подходящими останутся четыре раскладки, а одно взвешивание даёт только три исхода — различить их уже нельзя. В модели это можно проверить. Способ с противоположными углами работает при любых ответах весов.

Ответ

Можно. Настоящие монеты лежат либо квадратом $2\times 2$ в одном из углов, либо кольцом вокруг центра. Сравним левую верхнюю монету с правой нижней, затем правую верхнюю с левой нижней: каждой раскладке соответствует свой результат.

Ответ

Главная идея

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

Признак: «за $k$ взвешиваний найти». Сначала перечисли все возможные случаи и проверь, хватает ли исходов: два взвешивания дают до $3\cdot 3=9$ исходов, а случаев $5$ — шанс есть.

Где легко ошибиться

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

Источник и авторство

Турнир Архимеда · XXXIII Зимний турнир · 21 января 2024 · математика · единый вариант для 6 и 7 классов. Официальная задача 2.1, 6 баллов.

Условия задач (PDF организатора) ↗ · Условия и решения ↗ · Страница турнира ↗

Условие — из официального PDF, рисунок перерисован по нему. Подсказки, объяснение и модели — Popov Academy. Решение проверено; результат сопоставлен с официальными материалами.

Продолжить тему: Поиск и алгоритмы →

Тема, знания и приёмы

Поиск и алгоритмы · Начальный вход

Перебор случаев
Взвешивания

Приёмы решения: Разделение пространства поиска · Разбор случаев

Задать вопрос по задаче →