Задача про бракованные аймаки

Помогите наказать хитрого перекупщика.

Катя Павловская для Skillbox

Александр Бабаскин

Автор статей о программировании. Изучает Python, разбирает сложные термины и объясняет их на пальцах новичкам. Если что-то непонятно — возможно, вы ещё не прочли его следующую публикацию.

Два предпринимателя посмотрели презентацию Apple и заказали новые аймаки на чипе M1. Первый предприниматель купил десять компьютеров пяти разных цветов: 2 жёлтых, 2 серых, 2 розовых, 2 зелёных и 2 фиолетовых. Второй — заказал 100 аймаков, которые ему доставили в 10 одинаковых контейнерах.

Обоим попался хитрый перекупщик. Он вскрывал компьютеры и заменял чип М1 на подделку — Pirat1. Первому предпринимателю он заменил 2 чипа в аймаках одного цвета, а второму — в 10 аймаках из одного контейнера.

Пиратский чип не отличить по дизайну, но его можно вычислить по массе — он весит на 1 грамм меньше чипа М1. Если сразу не обнаружить подмену, то через 3 дня аймак на чипе Pirat1 перестанет работать. Масса одного аймака на М1 — 4 кг 480 г.

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

Подсказка

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

В условиях подобных задач нужно обращать внимание на такие моменты:

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

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

Если у вас точные весы и много объектов, разбитых по группам, вы можете выбрать разные объекты из всех групп и за одно взвешивание определить разницу масс.

Решение

Взвешиваем аймаки первого предпринимателя

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

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

Ситуация №1: пиратские чипы оказались в фиолетовых аймаках

Если выявится разница в 1 грамм, то бракованный чип окажется на более лёгкой чаше весов — в том аймаке, который взвешивается без пары.

Ситуация №2: пиратские чипы в зелёных аймаках

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

Ситуация №3: пиратские чипы в жёлтых аймаках

Теперь взвешиваем аймаки второго предпринимателя

Пронумеруем контейнеры от 1 до 10 и возьмём из каждого столько аймаков, сколько указано на контейнере. Из первого достанем 1 компьютер, из второго — 2 и так далее. Всего у нас получится 55 аймаков, которые мы будем взвешивать на точных весах.

Взвесим 55 аймаков, вынутых в разном количестве из каждого контейнера

Вес одного аймака — 4480 грамм. Если бы во всех компьютерах стоял чип М1, то их общий вес составил бы 246 400 грамм. Для расчёта мы умножили вес одного аймака на 55:

4480 грамм * 55 штук = 246 400 грамм

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

Если попался 1 бракованный аймак, то общий вес будет на 1 грамм меньше, то есть 246 399 грамм.
Если нашлось 5 бракованных компьютеров, то разница составит 5 грамм. Общий вес будет 246 395 грамм.
Если выявилось 10 бракованных устройств, то общий вес будет на 10 грамм меньше нормы — 246 390 грамм.

Надеюсь, вы без проблем справились с задачей и наказали хитрого перекупщика.