Матпраздник 2021 год · учебный сезон 2020/21 · Математика · 6 кл., №6

Условие

На витрине ювелирного магазина лежат $15$ бриллиантов. Рядом с ними стоят таблички с указанием масс, на которых написано $1, 2, \ldots, 15$ карат. У продавца есть чашечные весы и четыре гирьки массами $1$ $2$ $4$ и $8$ карат. Покупателю разрешается только один тип взвешиваний: положить один из бриллиантов на одну чашу весов, а гирьки — на другую и убедиться, что масса на соответствующей табличке указана верно. Однако за каждую взятую гирьку нужно заплатить продавцу $100$ монет. Если гирька снимается с весов и в следующем взвешивании не участвует, продавец забирает её. Какую наименьшую сумму придётся заплатить, чтобы проверить массы всех бриллиантов?

О задаче · 6 класс

Олимпиада: Математический праздник
Год: 2021 (учебный сезон 2020/21)
Предмет / класс: Математика · 6 класс
Вариант: Классический

Какие гирьки нужны для бриллианта в $7$ карат? А в $8$ Попробуй сам выбрать порядок взвешиваний в модели «Гирьки у жадного продавца» — она посчитает, сколько придётся заплатить. Какую сумму у тебя получилось сделать меньше всего?

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

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

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

Самостоятельное исследованиеГирьки у жадного продавца

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

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

Гирьки у жадного продавца

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

Если модель не открылась (выключен JavaScript или страница загрузилась не полностью), условие, подсказки и разбор доступны и без неё.

Как исследовать без модели

Выпиши массы 1…15 как суммы гирек 1, 2, 4, 8. Расставь их в таком порядке, чтобы соседние суммы отличались как можно меньше, и посчитай покупки.

Подсказка 1

Для каждой массы набор гирек один: $7=1+2+4$ $13=1+4+8$ и так далее. Платим каждый раз, когда кладём на весы гирьку, которой не было в прошлом взвешивании. Как сделать, чтобы между взвешиваниями набор менялся как можно меньше?

Подсказка 2

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

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

Какие гирьки на весах

Каждая масса от $1$ до $15$ записывается единственным способом как сумма разных гирек $1, 2, 4, 8$ (это двоичная запись): например, $11=8+2+1$ $6=4+2$ Значит, для каждого бриллианта набор гирек известен. Свобода только в одном — в каком порядке взвешивать.

Пример на 800 монет

Будем менять набор каждый раз ровно на одну гирьку:

1,\ 3,\ 2,\ 6,\ 7,\ 5,\ 4,\ 12,\ 13,\ 15,\ 14,\ 10,\ 11,\ 9,\ 8.

Например, после $1$ (гирька $1$ ) кладём ещё $2$ — взвешиваем $3$ убираем $1$ — взвешиваем $2$ кладём $4$ — взвешиваем $6$ Покупки происходят при переходах к $1, 3, 6, 7, 12, 13, 15, 11$ — всего $8$ раз, то есть $800$ монет.

Порядок взвешиваний: соседние наборы отличаются одной гирькой, новых гирек — 8.

Оценка: считаем действия

Назовём действием момент, когда мы что-то покупаем или что-то отдаём. Такие моменты: перед первым взвешиванием (обязательно покупаем), между соседними взвешиваниями (их $14$ наборы разные, значит, что-то меняется) и в конце (оставшиеся гирьки уходят продавцу). Всего моментов $16$ и в каждом хотя бы одна гирька покупается или отдаётся.

Каждую купленную гирьку мы потом отдаём ровно один раз. Значит, отдач столько же, сколько покупок, и всего гирек «туда и обратно» не меньше $16$ Покупок — половина, то есть не меньше $8$

Ответ

Меньше $8$ покупок не бывает, а $8$ достигается. Наименьшая сумма —

8\cdot 100=800\text{ монет}.

Такой порядок, где соседние наборы отличаются ровно одной гирькой, называется кодом Грея.

Проверка

Проверим перебором. Компьютер перебрал все порядки $15$ взвешиваний (динамикой по наборам уже взвешенных бриллиантов) и нашёл наименьшее число покупок — $8$ На тысячах случайных порядков он проверил, что покупок и отдач всегда поровну, а вместе их не меньше $16$

Ответ

$800$ монет.

Ответ

$800$ монет.

Главная идея

Порядок взвешиваний выбираем так, чтобы набор гирек менялся каждый раз на одну (код Грея) — тогда $8$ покупок. Меньше нельзя: в $16$ моментах (начало, $14$ переходов, конец) обязательно что-то покупается или отдаётся, а покупок и отдач поровну.

Признак: нужно перебрать все наборы, платя за изменения. Ищи порядок, где соседи отличаются минимально, а для оценки посчитай обязательные «события».

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

Взвешивать по порядку $1, 2, 3, \ldots, 15$ — так придётся много раз покупать одни и те же гирьки. Другая ошибка в оценке — сказать «гирек всего четыре, значит, 400 монет»: гирьку, которую забрали, приходится покупать снова.

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

Математический праздник 2021 года · классический вариант · 6 класс, задача 6 [8 баллов] · автор задачи А. В. Грибалко.

Условия 2021 года (сайт праздника) ↗ · Бланк 6 класса (PDF) ↗ · Решения организатора (PDF) ↗ · Сайт Математического праздника ↗

Условие — с сайта праздника. Подсказки, решение, рисунки и модель — Popov Academy. Задача сначала решена самостоятельно, затем ответ сверен с решением организатора: Ответ совпадает с ответом в решениях организатора (book.pdf 2021).

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

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

Поиск и алгоритмы · Продвинутая подготовка

Запись числа как суммы 1, 2, 4, 8 (двоичная запись)
Оценка через подсчёт событий

Приёмы решения: Оценка и достижимость · Последовательный подсчёт без повторов

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