Примерьте роль королевского казначея и постарайтесь максимально облегчить себе работу.
Представьте, что вы работаете в королевской казне и целыми днями ищете поддельные монеты. По виду они не отличаются от настоящих, но вес фальшивок всегда немного больше.
Из инструментов у вас только старые весы с двумя чашами и без гирь.
– 1 –
Вам принесли 21 монету, одна из них поддельная и весит больше остальных. За сколько взвешиваний можно её найти?
Решение
Сначала на каждую чашу нужно выложить по 7 монет. Если какая‑то из чаш будет ниже другой, то подделка в ней. Если чаши останутся в равновесии, то фальшивка обнаружится в кучке, которая не лежала на весах.
После того, как стало известно, где лежит подделка, нужно сделать следующее: разделить эту кучку и положить на каждую чашу по 3 монеты, а одну оставить на столе. Если чаши будут в равновесии, то оставшаяся монета — фальшивая. В этом случае на проверку понадобится всего два взвешивания.
Если какая‑то чаша перевесит, то подделка — одна из трёх монет на ней.
Тогда останется сделать последнее, третье взвешивание: взять кучку из трёх подозрительных монет, по одной положить на чаши весов, одну оставить на столе. Если весы будут в одинаковом положении, то фальшивка на столе, а если одна из чаш перевесит, то нужная монета на ней.
Ответ: поддельную монету можно обнаружить за три взвешивания.
– 2 –
Теперь у вас на столе 200 монет, и снова одна из них фальшивая и более тяжёлая, чем все остальные. Сколькими взвешиваниями можно обойтись в этом случае?
Решение
Эта задача решается похожим способом. Только теперь монеты нужно разделить на три части так, чтобы их количество было примерно одинаковым в каждой из кучек, в двух из них монет должно быть поровну. Получается 67, 67 и 66 монет.
Если выложить на весы по 67 монет и одна из чаш перевесит, то более тяжёлую кучку нужно поделить на 22, 22 и 23 монеты. Затем взвесить части из 22 монет.
Если весы опять не будут уравновешены, то группу нужно поделить на кучки по 7, 7 и 8 монет. Теперь придётся снова взвесить кучки по 7 монет; если одна перевесит, то её нужно поделить на кучки из 3, 3 и 1 монеты.
Получаются условия, как в первой задаче, и тогда останется сделать ещё два взвешивания, чтобы найти фальшивку. В итоге понадобится минимум пять взвешиваний.
Столько же взвешиваний потребуется на проверку, если весы на первом шаге будут в равновесии. Тогда фальшивка окажется в кучке из 66 монет, её нужно поделить на три равные части по 22 монеты. Затем сделать ещё одно взвешивание и найти кучку с подделкой. Её останется разделить на кучки по 7, 7 и 8 монет и дальше действовать таким же образом, как и в первом случае.
Ответ: поддельную монету можно обнаружить за пять взвешиваний.
Головоломки составлены на основе материалов из книги Жан‑Клода Байифа «Логические задачи».
Читать далее →
Свежие комментарии