|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Andrew Ezhguroff 2:5020/400 05 Oct 2001 02:17:09
To : Sergey Konuhov
Subject : 1 из 13 (было "Интересная задача")
--------------------------------------------------------------------------------
Привет! "Sergey Konuhov" <Sergey.Konuhov@p14.f59.n5022.z2.fidonet.org>
сообщил(а) нам:
> е выходит, что-то...
> Вот если после двух сравнений веса, он получается одинаковым, то
информация о
> том, легче или тяжелее фальшивая монета еще не проявляется, и это
единственная
> затычка (добавляет еще одно взвешивание) для случаев первоначального
деления на
> три или четыре части.
Смысл задачи как раз в том, что при следующем взвешивании результаты
предыдущих взвешиваний не учитываются. И никакого деления вообще не
производится.
Сначала определим, сколько теоретически можно найти монет за 3 взвешивания.
Весы могут принимать одно из трех положений: равновесие (=), левая чашка
внизу (Л) и правая чашка внизу (П). Соответственно при трех взвешиваниях
имеем 27 вариантов. Hо т.к. мы не знаем соотношение весов, то зеркальные
варианты объединяем в комбинации. Так одной комбинацией являются варианты
ЛП= и ПЛ=, или П=П и Л=Л... Всего получаем 14 (для N взвешиваний -
(3^N+1)/2) комбинаций, каждая из которых соответствует одной монете:
1 - ===, монета на весы не кладется
2 - Л==/П==, монета кладется только в первом взвешивании
...
5 - ЛЛ=/ПП=, монета кладется в первом и втором взвешивании на одну чашку
...
8 - ЛП=/ПЛ=, монета кладется в первом и втором взвешивании на разные чашки
...
11 - ЛЛП/ППЛ, монета кладется в первом и втором взвешивании на одну чашку и
в третьем на другую
...
14 - ЛЛЛ/ППП, монета кладется три раза на одну чашку.
Hо пытаясь разложить монеты по чашкам получаем, что при каждом взвешивании
придется класть на весы по 9 монет, что невозможно. Соответственно вариант
14 придется исключить.
Получаем, что за 3 взвешивания можно определить фальшивую монету из 13.
С уважением, Андрей.
P.S. А одну из 14 можно определить, если при взвешиваниях добавить заведомо
настоящую пятнадцатую монету.
--- ifmail v.2.15dev5
* Origin: COMSTAR Telecommunications (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
