Тема: Логические загадки-3

[Арвинд›]

ОК, спрашиваю.
Дано: 12 с виду одинаковых монет. Рычажные весы (они, напомню, позволяют сравнить веса того, что на их чашах). Известно, что есть одна фальшивая монета. Она отличается по весу от остальных. Неизвестно, в какую сторону - т.е. легче она или тяжелее остальных.
Вопрос: за какое минимальное число взвешиваний можно найти эту монету? Как именно уложиться в это число?
Сразу подсказка: как правило, если только человек не гений, он с ходу указывает решение, на единицу длиннее оптимального.

               

               

[KATEHOK›]

Положить по 4 монеты на каждую чашу весов. Потом поменять одну (неважно какую именно) из четверок с теми 4 монетами, которые не участвовали в предыдущем взвешивании. Убираем те 2 четверки, вес которых равный. Оставшуюся четверку делим пополам. Взвешиваем и убираем ту пару, которая отличается в ту же сторону, что и 2 убранных четверки. Точно так же определяем, какая из 2 оставшихся монет настоящая (она отличается от фальшивой в ту же сторону).
Всего 3 + 2 = 5 взвешиваний.

               

               

[Mifnar Daegor›]

У меня получается три или четыре взвешивания...
Сначала делишь их пополам - по 6 на каждую чашу весов. Запоминаешь, какая меньше весит, какая больше. Отлаживаешь одну кучку в сторону (например ту, которая весит меньше). Делим пополам ту кучку, которая весит больше, и получается по три манеты на каждой чаше. Если не равны - значит фальшивая здесь, и весит она больше. Сметаем три правильные монетки (которые сверху), покупаем на них арбуз и продолжаем проверять  
У нас осталось три монетки - ложим две из них на разные чаши весов - если они одинаковые - то третья оставшаяся фальшивая, если нет - то соответственно та, что тяжелее.

Если те, что весят больше при втором взвешивании (3х3) показывают одинаковый результат, берём кучку, которая весила меньше, и повторяем второе (3х3) и третье взвешивание (1х1 +1 в стороне)

Итого получаем максимум четыре, а при использовании логики (фальшивые монеты обычно легче   ) и/или везения получаем три взвешивания.

Но наверно есть какой-нибудь путь круче алгоритма бинарного поиска  

Предпологая что каким-то образом гении находят монетку за два взвешивания  

А пророки - те вообще не взвешивают  

               

               

[Арвинд›]

Mifnar Daegor, предложенный ответ - это все-таки 4 взвешивания. Вариант "если повезет" не принимается.
Как правило, путь из четырех взвешиваний находят легко (по крайней мере люди моего круга общения).
Мораль: ищите алгоритм, который за 3 (три) взвешивания гарантированно укажет фальшивую монету. Напомню, она может быть легче или тяжелее остальных.
Если у кого есть свежие варианты из 4 или даже 5 взвешиваний - пишите, это поможет в решении. Вариант, предложенный Катенком, хоть и длиннее, но содержит несколько иные идеи, чем те, что использовал Mifnar Daegor, так что оба предложения ценны.

PS Доказательства того, что это невозможно сделать за 2 раза, не требую, т.к. и я его не имею. Задачу я решал сам, спросить было некого, а рюхать этот момент самостоятельно меня заломало - какие-то моменты наметил, остальное обозвал "интуитивно понятным"  

               

               

[Љ™›]

Chitatel
http://ega-math.narod.ru/Quant/Shestpl.htm (http://ega-math.narod.ru/Quant/Shestpl.htm)

               

               

[Арвинд›]

Љ™, спасибо. Собственно, мне была понятна невозможность обойтись двумя взвешиваниями - как раз по указанным там причинам. Другое дело, что понимание "почему" и доказательство - сильно разные вещи. Там все доказано очень понятно, думаю, любой сможет разобраться.
Интересно, авторских методик "трех взвешиваний" никто уже не предложит? Тогда ищите новые вопросы...

               

               

[Vovka39›]

Доказать невозможность обойтись двумя - довольно просто. Результатов двух взвешиваний может быть только 3², что меньше 12 - количества вариантов для фальшивой монеты.

               

               

[Арвинд›]

Что ж, никто больше не знает никаких логических задачек?  

               

               

[Снорри›]

Судя по всему, нет. .

Жалко, хороший тред загибается.

Читатель, неужели у тебя тоже ничего нет?

               

               

[Vovka39›]

Ну давайте, я зададу.
В помещении находятся одиннадцать человек: три мудреца, всегда говорящих правду; семь хитрецов, говорящих как захочется, и Вы, О задающий вопросы. Можно ли определить хотя бы одного хитреца?

               

               

[Арвинд›]

  Насколько я понимаю, ничего не мешает хитрецу отвечать на любые вопросы так, как если бы он был мудрецом... Значит, нам может помочь только то, что мы знаем их количество? Но если три хитреца договорятся изображать трех мудрецов - их на чистую воду, боюсь, не выведешь...
Из семи может выйти две такие тройки + один лишний. Может быть, его и стоит ловить?
Короче, пока никаких идей. Будем думать. Спасибо  

               

               

[Љ™›]

Каждому задаем по 10 вопросов вида "Мудрец ли человек № x".

Мудрецы ответят одинаково: да они ответян на вопрос про себя и про остальных мудрецов.
Хитрецы, чтобы выдать себя за мудрецов, должны ответить "да" на вопросы про себя и про 2 других.
Короме того, хитрецы должны разбиться на тройки с одинаковыми ответами (поскольку мудрецов трое), а это невозможно, так как хитрецов 7 человек, следовательно мы сможем определить хотя бы одного хитреца.

               

               

[Арвинд›]

Похоже на правду, Vovka39?
Љ™, загадки есть?



               

               

[Снорри›]

У меня есть. Надо?

               

               

[Љ™›]

kidd 79ый
Давай


               

               

[Снорри›]

Хорошо.

Есть два стакана неизвестного объема - в одном некоторое количество пива, в другом - столько же водки. Из первого стакана берем ложечку пива и вливаем во второй стакан (с водкой). Тщательно размешиваем. Потом из второго стакана ( с водкой и чуточкой пива) берем такое же количество имеющейся там смеси и вливаем в первый стакан. Тоже тщательно размешиваем.

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

Вопрос: чего больше: водки в пиве или пива в водке?



               

               

[Vovka39›]

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


               

               

[Bard›]

я считаю,что пива в водке! не знаю почему но у меня привычка ошибаться...

               

               

[Арвинд›]

Цитата:
Потому что ответ, что одинаково, даже с доказательством, будет явно преждевременным.
 Не, Vovka39 , тут явно ожидается ответ "одинаково". И доказать это нетрудно. Только хотелось бы красиво, а не в лоб...

               

               

[Mifnar Daegor›]

Сейчас решим!

Допустим в каждом стакане по сто грамм. Ложка - пять грамм. Берём 5 грамм пива и вливаем в водку - итого у нас 105 грамм, пять из которых - пиво. В одном грамме жидкости - 5/105=0,0476 грамма пива.

Берём пять грамм жидкости, в которой содержится 0,238 грамм пива и вливаем в пиво.

В стакане с водкой и каплей пива остаётся 4,762 грамма пива.

а в стакан с пивом попадают опять же 4,762 грамма водки, то есть и там и там поровну...

Странно, а я думал что чего-то будет меньше, а чего-то больше...