Popov AcademyУсловие
Есть десять пронумерованных мешков с монетами, в каждом не меньше десяти монет. Ровно в одном мешке все монеты весят по г, в остальных — по г. На вид монеты одинаковы. Электронные весы точно показывают суммарную массу и выдерживают не меньше г. Разрешено одно взвешивание любого заранее выбранного набора монет. Как гарантированно определить мешок с лёгкими монетами?
О задаче · Подростки и взрослые
Записать идеюЕсть запись
Личный черновик для заметок и расчётов. Он никуда не отправляется и не проверяется.
Черновик не сохраняется: текст только в этой вкладке.
Черновик изменён в другой вкладке. Твой текущий текст пока сохранён здесь, автоматическая запись остановлена.
Подсказка 1
Не обязательно брать из всех мешков одинаковое количество монет.
Подсказка 2
Из мешка с номером возьмите монет. На сколько граммов он уменьшит ожидаемую массу, если именно он лёгкий?
Разобрать решение по шагам
Задайте разный вклад мешков
Берём одну монету из первого мешка, две из второго, и так далее до десяти из десятого. Всего получаем
монет. Если бы каждая весила г, общая масса была бы г.
Прочитайте отклонение
Пусть лёгкий мешок имеет номер . Из него взяты монет, каждая легче обычной ровно на г. Только они уменьшают сумму, поэтому весы покажут
граммов. Разница между и показанием однозначно даёт . Например, г указывают на седьмой мешок.
Проверьте гарантию
Возможные недостачи равны целым числам от до , и никакие два мешка не дают одну и ту же. Мы использовали только одно измерение, но у электронных весов много различимых числовых результатов. Это отличается от чашечных весов с тремя возможными ответами.
Ответ
Если весы показывают граммов, номер мешка — . Например, при это мешок .
Главная идея
Чтобы по одному измерению различить причины, назначьте им разные измеримые вклады.
Как заметить эту идею в другой задаче
Один объект отличается от остальных одинаковой добавкой или недостачей. Возьмите из групп разное число предметов, чтобы общий сдвиг однозначно закодировал номер группы.
Возможная ошибка
Брать по одной монете из каждого мешка: тогда любой лёгкий мешок уменьшит сумму на один и тот же грамм.
Источник и примечания
Источник и редакция
Классическая задача. Формулировка и разбор — Popov Academy.
Проверь себя
Если лёгких мешков ровно два, сохранится ли однозначность того же набора из ,…, монет?
Ответ к дополнительной задаче
Нет. Недостача станет суммой двух номеров. Мешки и дадут те же г недостачи, что мешки и . Такие результаты одним этим измерением не различить.
Тема, знания и приёмы
Поиск и алгоритмы · Начальный вход
- Код писать не нужно. Понадобятся точный план и проверка всех возможных случаев.
Приёмы решения: Последовательный подсчёт без повторов