Скрудж Макдак знает что из 27 золотых монет одинаковых на вид одна фальшивая и весит меньше остальных за Какое минимальное количество времени на чашечных весах без гирь он сможет найти фальшивку
За 3. Как сделать: 3 раза делим все монеты на 3 равные части и сравниваем две части. Если одна из них легче, то там фальшивка, если одинаковой массы, то фальшивка в непроверенной части. После каждого взвешивания число монет, которые потенциально могут быть фальшивыми, уменьшается втрое, и через 3 взвешивания останется только 1 монета. Почему нельзя меньше: Пусть можно за 2. Каждое взвешивание имеет 3 возможных исхода: левая чаша тяжелее, одинаково, правая тяжелее. Поэтому возможно только 3^2 = 9 возможных исходов двух взвешиваний. Но так как фальшивая монета может любой из 27 монет, то по принципу Дирихле какие-то две из этих возможностей кодируются одним и тем же набором исходов взвешиваний, и определить, какая из этих двух монет фальшивая, нельзя.
Answers & Comments
Verified answer
Ответ ответ ответ ответ ответ ответ ответVerified answer
За 3.Как сделать: 3 раза делим все монеты на 3 равные части и сравниваем две части. Если одна из них легче, то там фальшивка, если одинаковой массы, то фальшивка в непроверенной части. После каждого взвешивания число монет, которые потенциально могут быть фальшивыми, уменьшается втрое, и через 3 взвешивания останется только 1 монета.
Почему нельзя меньше: Пусть можно за 2. Каждое взвешивание имеет 3 возможных исхода: левая чаша тяжелее, одинаково, правая тяжелее. Поэтому возможно только 3^2 = 9 возможных исходов двух взвешиваний. Но так как фальшивая монета может любой из 27 монет, то по принципу Дирихле какие-то две из этих возможностей кодируются одним и тем же набором исходов взвешиваний, и определить, какая из этих двух монет фальшивая, нельзя.