разминка для мозгов.
вот, решаем-решаем, не можнм решить:
"Есть 12 одинаковых внешне монеток. Одна из них фальшивая - либо легче, либо тяжелее. Нужно за три взвешивания на обычных весах найти фальшивую и сказать, она легче или тяжелее."
"Есть 12 одинаковых внешне монеток. Одна из них фальшивая - либо легче, либо тяжелее. Нужно за три взвешивания на обычных весах найти фальшивую и сказать, она легче или тяжелее."
Г
Гуж
делим на 3 кучки по 4 монеты
1.взвешиваем(1) 1-ю и 2-ю
2. если вес равный убираем эти монеты и дальше работаем с кучкой 3
Иначе, с более легкой из них
3.делим оставшиеся четыре монеты на 2 кучки по 2 и взвешивем (2-раз)
4. выбираем более легкую, остается 2 монеты.
5. взвешиваем (3-раз) и определяем фальшивую.
:-)
1.взвешиваем(1) 1-ю и 2-ю
2. если вес равный убираем эти монеты и дальше работаем с кучкой 3
Иначе, с более легкой из них
3.делим оставшиеся четыре монеты на 2 кучки по 2 и взвешивем (2-раз)
4. выбираем более легкую, остается 2 монеты.
5. взвешиваем (3-раз) и определяем фальшивую.
:-)
s
sandro
Гуж,
в условии задачи не сказано, что фальшивая монета легче
в условии задачи не сказано, что фальшивая монета легче
U
15262333
[Сообщение удалено пользователем 14.12.2003 22:00]
Г
Гуж
Угу. Если не известно, что легче, то решения просто нет. :-)
U
15262333
Решение возможно, но оно некорректно. В том смысле, что может повезти, а может и нет.
S
Smasher
Задачка неслабая но решение имеет в любом случае:
======================================
Математическая головоломка месяца: август 2002 - решение
Какая из монеток фальшивая?
Несколько человек, среди которых Мигель Тенорио и Дейвид Стентон, решили эту задачу при помощи четырех взвешиваний. На самом деле задача решается с помощью трех взвешиваний. Вот как это происходит:
Пронумеруем монеты: 1 2 3 4 5 6 7 8 9 10 11 12, и разделим их на три группы:
A [1 2 3 4]
B [5 6 7 8]
C [9 10 11 12]
1. Взвесим монеты группы A и B. Если их вес окажется одинаковым, то мы узнаем, что фальшивая монета находится в группе C, а монеты в A и B - настоящие. Теперь давайте предположим, что это условие выполняется.
2. Возьмем три любые монеты из группы A или B (все они настоящие) и взвесим с тремя монетами из C - к примеру, будем взвешивать монеты [1 2 3] и [9 10 11]. Здесь может быть два варианта:
a. Монеты имеют одинаковый вес - таким образом, монета номер 12 фальшивая, затем третье взвешивание этой монеты с любой другой определяет, тяжелее она или легче;
b. Монеты имеют разный вес, поэтому одна из монет, имеющих номер 9, 10 или 11 - фальшивка. (И если группа [9 10 11] легче, чем группа [1 2 3], то фальшивая монета легче, чем подлинная. Если группа [9 10 11] тяжелее, то вес фальшивки больший). В третьем взвешивании возьмем две монеты из группы [9 10 11] и сравним их вес. Если их вес одинаков, то подделка - оставшаяся третья монета. Если нет, то Вы можете определить подделку, так как уже знаете, тяжелее или легче она по сравнению с другими монетами.
Теперь давайте вернемся первому шагу и рассмотрим другой - более сложный вариант хода событий.
1. Мы сравнили вес монет групп A и B, он оказался разным, поэтому фальшивка находится в группе A или группе B. Кроме этого, теперь мы знаем, что монеты в группе C - подлинные*;
2. Предположим, что монеты группы A [1 2 3 4] тяжелее монет группы B [5 6 7 8]. Разделим группу A таким образом, чтобы мы взвешивали монеты [1 2] и [3 4]. К ним добавим по одной монете из группы B - на левую чашу весов, и С - на правую. Таким образом мы сравниваем вес монет [1 2 5] и [3 4 12]. Мы знаем, что монета номер 12 настоящая. В этой ситуации возможно три варианта.
1. Монеты [1 2 5] тяжелее. Но мы знаем, что монеты с номерами 3,4 и 5 - настоящие, так как мы положили их на разные чаши весов, и баланс при этом не менялся: монеты 3 и 4 были переложены с левой чаши на правую, а номер 5 - с правой на левую. Таким образом, фальшивая монета находится под номером 1 или 2. Теперь мы также знаем, что вес фальшивки больше. Последнее взвешивание монет 1 и 2 точно устанавливает подделку - более тяжелую монету.
2. Монеты [3 4 12] тяжелее. Это означает, что поддельная монета была перемещена. Вероятно, что подделка - номер 3 или 4, и вес монеты больше. Подделкой также может быть монета номер 5, тогда вес фальшивки меньше. Последнее взвешивание монет 3 и 4 дает точный ответ. Если вес этих монет оказывается одинаковым, то подделка - номер 5. Если нет, то значит вес фальшивки больше массы номеров 3 и 4.
3. Монеты с номерами [1 2 5] и [3 4 12] уравновешиваются. Это означает, что фальшивки нет на чашах весов, поэтому она должна находиться сред трех оставшихся монет групп А и В, то есть номеров [6 7 8]. Но мы знаем, что вес подделки меньше, так как при первом взвешивании номера [1 2 3 4] были тяжелее группы [5 6 7 8]. Третье взвешивание, в котором на чаши весов кладется по одной монете, определяет подделку. Если мы сравним вес номеров 6 и 7, и он окажется одинаковым, то подделка - 8. В противном случае фальшивой является более легкая монета.
Более подробно решение задачи описано в книге: Мачалевиц, Збинев и Фогель, Дэйвид Б, Как решать: современная эвристика, Спрингер, Берлин, Нью-Йорк, 2000 г. (ISBN: 3-540-66061-5)
======================================
(c)
======================================
Математическая головоломка месяца: август 2002 - решение
Какая из монеток фальшивая?
Несколько человек, среди которых Мигель Тенорио и Дейвид Стентон, решили эту задачу при помощи четырех взвешиваний. На самом деле задача решается с помощью трех взвешиваний. Вот как это происходит:
Пронумеруем монеты: 1 2 3 4 5 6 7 8 9 10 11 12, и разделим их на три группы:
A [1 2 3 4]
B [5 6 7 8]
C [9 10 11 12]
1. Взвесим монеты группы A и B. Если их вес окажется одинаковым, то мы узнаем, что фальшивая монета находится в группе C, а монеты в A и B - настоящие. Теперь давайте предположим, что это условие выполняется.
2. Возьмем три любые монеты из группы A или B (все они настоящие) и взвесим с тремя монетами из C - к примеру, будем взвешивать монеты [1 2 3] и [9 10 11]. Здесь может быть два варианта:
a. Монеты имеют одинаковый вес - таким образом, монета номер 12 фальшивая, затем третье взвешивание этой монеты с любой другой определяет, тяжелее она или легче;
b. Монеты имеют разный вес, поэтому одна из монет, имеющих номер 9, 10 или 11 - фальшивка. (И если группа [9 10 11] легче, чем группа [1 2 3], то фальшивая монета легче, чем подлинная. Если группа [9 10 11] тяжелее, то вес фальшивки больший). В третьем взвешивании возьмем две монеты из группы [9 10 11] и сравним их вес. Если их вес одинаков, то подделка - оставшаяся третья монета. Если нет, то Вы можете определить подделку, так как уже знаете, тяжелее или легче она по сравнению с другими монетами.
Теперь давайте вернемся первому шагу и рассмотрим другой - более сложный вариант хода событий.
1. Мы сравнили вес монет групп A и B, он оказался разным, поэтому фальшивка находится в группе A или группе B. Кроме этого, теперь мы знаем, что монеты в группе C - подлинные*;
2. Предположим, что монеты группы A [1 2 3 4] тяжелее монет группы B [5 6 7 8]. Разделим группу A таким образом, чтобы мы взвешивали монеты [1 2] и [3 4]. К ним добавим по одной монете из группы B - на левую чашу весов, и С - на правую. Таким образом мы сравниваем вес монет [1 2 5] и [3 4 12]. Мы знаем, что монета номер 12 настоящая. В этой ситуации возможно три варианта.
1. Монеты [1 2 5] тяжелее. Но мы знаем, что монеты с номерами 3,4 и 5 - настоящие, так как мы положили их на разные чаши весов, и баланс при этом не менялся: монеты 3 и 4 были переложены с левой чаши на правую, а номер 5 - с правой на левую. Таким образом, фальшивая монета находится под номером 1 или 2. Теперь мы также знаем, что вес фальшивки больше. Последнее взвешивание монет 1 и 2 точно устанавливает подделку - более тяжелую монету.
2. Монеты [3 4 12] тяжелее. Это означает, что поддельная монета была перемещена. Вероятно, что подделка - номер 3 или 4, и вес монеты больше. Подделкой также может быть монета номер 5, тогда вес фальшивки меньше. Последнее взвешивание монет 3 и 4 дает точный ответ. Если вес этих монет оказывается одинаковым, то подделка - номер 5. Если нет, то значит вес фальшивки больше массы номеров 3 и 4.
3. Монеты с номерами [1 2 5] и [3 4 12] уравновешиваются. Это означает, что фальшивки нет на чашах весов, поэтому она должна находиться сред трех оставшихся монет групп А и В, то есть номеров [6 7 8]. Но мы знаем, что вес подделки меньше, так как при первом взвешивании номера [1 2 3 4] были тяжелее группы [5 6 7 8]. Третье взвешивание, в котором на чаши весов кладется по одной монете, определяет подделку. Если мы сравним вес номеров 6 и 7, и он окажется одинаковым, то подделка - 8. В противном случае фальшивой является более легкая монета.
Более подробно решение задачи описано в книге: Мачалевиц, Збинев и Фогель, Дэйвид Б, Как решать: современная эвристика, Спрингер, Берлин, Нью-Йорк, 2000 г. (ISBN: 3-540-66061-5)
======================================
(c)
Г
Гуж
Мдаа... за 10 минут до такого не додумаешься :-)
S
Smasher
Я тоже не додумался :-)
U
15262333
м-даааа...
думать ушёл...
[Сообщение изменено пользователем 14.12.2003 22:00]
думать ушёл...
[Сообщение изменено пользователем 14.12.2003 22:00]
S
Smasher
Я как Шерлок Холмс - если расскажу откуда станет неинтересно :-)
Честно могу сказать что до самого сложного шага не додумался (как водится, за 10 минут :-) )
Мастер спорта, а что сообщение-то стер как задачку месяц решал? ;-) Мы-то все видели ;-)
Честно могу сказать что до самого сложного шага не додумался (как водится, за 10 минут :-) )
Мастер спорта, а что сообщение-то стер как задачку месяц решал? ;-) Мы-то все видели ;-)
Авторизуйтесь, чтобы принять участие в дискуссии.