Найти фальшивую монету, головоломка) Опции

[King]

Итак, с нами расплатились 12-ю монетами, но есть подозрения, что одна из этих монет фальшивая, причем неизвестно, легче она настоящих или тяжелее.
Есть весы - две чашечки без гирь. Имеют три положения: больше, меньше или равно.
Требуется найти эту монету за три взвешивания.

Повторяю, вес монеты неизвестен!

ЗЫ: я убил почти 50 минут на поиск решения, хотя задача не такая уж и сложная.

[King]

Ну что, никто не отгадал?

[Мася]

Надо разделить все монеты на три кучки ( по 4 монеты). Взвесить две кучки, если они по весу равны, значит фальшивка в той, которую отложили. Ну, или в меньшей по весу, соответственно. Потом эту кучку , разделить пополам ( 4 / 2 = 2). По той же схеме.... Меньшую по весу кучку разбиваем по 1 монете... оп-ля... так ?

[Norua]

Надо разделить все монеты на три кучки ( по 4 монеты). Взвесить две кучки, если они по весу равны, значит фальшивка в той, которую отложили. Ну, или в меньшей по весу, соответственно. Потом эту кучку , разделить пополам ( 4 / 2 = 2). По той же схеме.... Меньшую по весу кучку разбиваем по 1 монете... оп-ля... так ?

Таг точно Старая загадка.

[Мася]

Давай ещё !!!

Таг точно Старая загадка.

Да? Я не слышала... ну, значит я младше старой загадки !!! Что не может не радовать !

[DimaM3]

Загадка:

Есть у женщины на теле, у мужчины в голове, применяется в хоккее и на шахматной доске

В Google ответа нет)

[VGS]

По поводу первой задачи-у доченьки в 5-м классе подобные задачки

Сообщение отредактировал VGS - Apr 27 2009, 21:49

[Мася]

Загадка:

Есть у женщины на теле, у мужчины в голове, применяется в хоккее и на шахматной доске

В Google ответа нет)

КОМБИНАЦИЯ !!!!

ЗЫ: Похожая загадка была

Сообщение отредактировал Мася - Apr 27 2009, 21:56

[DimaM3]

КОМБИНАЦИЯ !!!!

ЗЫ: Похожая загадка была

От Елена, все вы знаете)) К гадалке не ходи - к Елене хади

[Мася]

От Елена, все вы знаете)) К гадалке не ходи - к Елене хади

да ладно вам... мозгам встряску хоть иногда делать надо....

ЗЫ: УЖАСТЬ, смайл не тот поставила

Сообщение отредактировал Мася - Apr 27 2009, 22:18

[Norua]

да ладно вам... мозгам встряску хоть иногда делать надо....

Ну тогда достаточно просто сильно потрясти головой )

[Мася]

Ну тогда достаточно просто сильно потрясти головой )

шутники...

[semesh]

Надо разделить все монеты на три кучки ( по 4 монеты). Взвесить две кучки, если они по весу равны, значит фальшивка в той, которую отложили. Ну, или в меньшей по весу, соответственно. Потом эту кучку , разделить пополам ( 4 / 2 = 2). По той же схеме.... Меньшую по весу кучку разбиваем по 1 монете... оп-ля... так ?

Таг точно Старая загадка.

Все бы хорошо, но: причем неизвестно, легче она настоящих или тяжелее. Вес монеты не известен!

Я тоже так сначало решил

[King]

Товарищи, ответ дан неверный. Я тоже думал, что задача решается за ТРИ минуты. Напоминаю, что относительный вес фальшивой монеты нам неизвестен.
Т.е., она может быть как легче, так и тяжелее.

[Мася]

Товарищи, ответ дан неверный. Я тоже думал, что задача решается за ТРИ минуты. Напоминаю, что относительный вес фальшивой монеты нам неизвестен.
Т.е., она может быть как легче, так и тяжелее.

во , млиннн

[VGS]

Все бы хорошо, но: причем неизвестно, легче она настоящих или тяжелее. Вес монеты не известен!

Я тоже так сначало решил

Из 3-х "кучек" две будут одинаково весить независимо от того, легче или тяжелее фальшивая монета

[semesh]

Из 3-х "кучек" две будут одинаково весить независимо от того, легче или тяжелее фальшивая монета

Это уже будет 2 взвешивания. Задача не решена!

[King]

Даю маленькую подсказку.
Первое решение разделить монеты на три кучи по 4 штуки стратегически правильное

[semesh]

Здесь скорее всего относительное взвешивание

[kevindark]

Следующий шаг - разделение оставшейся кучки пополам? )

[Norua]

Товарищи, ответ дан неверный. Я тоже думал, что задача решается за ТРИ минуты. Напоминаю, что относительный вес фальшивой монеты нам неизвестен.
Т.е., она может быть как легче, так и тяжелее.

Э... Да, так сложнее... Надо думать.

[King]

В идеале, когда мы взвесили 2 кучки по 4 монетки они должны быть равны по весу. Тогда мы точно знаем, что фальшивая монета в третьей нетронутой кучке.

Кстати, при 12 монетах и трех взвешиваниях мы не только сможем определить фальшивую монету, но и точно узнать - легче она или тяжелее.
Задача, кстати, решается и с 13 монетами. Но при 13-и мы не сможем узнать относительный вес, только выделить.

Самая жесть, когда весы остаются в таком положении / при первом взвешивании)

Сообщение отредактировал King - Apr 27 2009, 22:39

[semesh]

В идеале, когда мы взвесили 2 кучки по 4 монетки они должны быть равны по весу. Тогда мы точно знаем, что фальшивая монета в третьей нетронутой кучке.

Кстати, при 12 монетах и трех взвешиваниях мы не только сможем определить фальшивую монету, но и точно узнать - легче она или тяжелее.
Задача, кстати, решается и с 13 монетами. Но при 13-и мы не сможем узнать относительный вес, только выделить.

Самая жесть, когда весы остаются в таком положении / при первом взвешивании)

Потом взвешиваем по-одной

В идеале, попадуться 2 одинакового веса. Потом Потом одну оставляем, а третью взвешиваем, вуаля!

Сообщение отредактировал semesh - Apr 27 2009, 22:43

[King]

Потом взвешиваем по-одной

Попробуй, если уложишься в ТРИ взвешивания

[Norua]

Ну я пока вдуплил как сделать за два взвешивания на одной чаше. Но поцесс технологически сложен. За три как-то туго.

[VGS]

1. кидаем по 4 монеты. Вес равный.
2. добавляем по одной монете в каждую чашу.
3. если равновесие сохраняется, значит монета-одна из двух оставшихся. Берём любую и взвешиваем с одной из монет, которая на весах. Если вес одинаковый-значит фальшивка осталась не взвешенной?

[semesh]

Попробуй, если уложишься в ТРИ взвешивания

Если снова одинаковы - фальшива та что осталась Если нет, то та которую положили

[King]

Если снова одинаковы - фальшива та что осталась Если нет, то та которую положили

А то, что мы не знаем, легче ли фальшивка оригинала или тяжелее, не?

[semesh]

1. кидаем по 4 монеты. Вес равный.
2. добавляем по одной монете в каждую чашу.
3. если равновесие сохраняется, значит монета-одна из двух оставшихся. Берём любую и взвешиваем с одной из монет, которая на весах. Если вес одинаковый-значит фальшивка осталась не взвешенной?

И так можно

А то, что мы не знаем, легче ли фальшивка оригинала или тяжелее, не?

Изначально лежит одна настоящая

[King]

Друзья, задача нетривиальна, как может показаться на первый взгляд. Даже камрад Саша Мась (его проекты - УБН, Инфостор и др.) решал с другом ее 45 минут. Правда, они алгоритм нарисовали, сколько максимум можно взять монет при N взвешиваниях. А Саша, между прочим, призер городской олимпиады по математике

Частный случай (если типа повезло) не считается. А если не повезло?
Вот если положили по 4 монеты и весы перестали находиться в равновесии? Как тогда?

Сообщение отредактировал King - Apr 27 2009, 22:51

[kevindark]

Так... если положение "/", то мы точно знаем, что "левая" монета в одной из этих кучек.

Блин, монеты походу надо бирками обклеить и потом перевешать в разных комбинациях, записывая соотношение при взвешивании.

Сообщение отредактировал kevindark - Apr 27 2009, 22:48

[semesh]

Откуда мы знаем, что она настоящая?

Ну допустим так совпало, при взвешивании 3-й кучки, первые две монеты на разных весах показали равенство в весе Забираем одну и ложим третью. Если снова равенство - значит фальшивка та что не взвешивалась. Если нет - то та которую только что взвесили, третья. Фух!

[VGS]

А если вес неравный?


Откуда мы знаем, что она настоящая?

А если вес не равный, значит одна из двух монет (последних)-фальшивая.
Стало быть берём одну из этих двух монеток и взвешиваем с любой из первых восьми(4+4)
Если первая по весу одинаковая-значит вторая-фальшивка.

[King]

Блин, монеты походу надо бирками обклеить и потом перевешать в разных комбинациях, записывая соотношение при взвешивании.

Про бирки - это очень правильная идея!
Я бы предложил их даже пронумеровать

Хыхы, ну все, кому-то бессонница гарантированна ))

Сообщение отредактировал King - Apr 27 2009, 22:55

[Мася]

Про бирки - это очень правильная идея!
Я бы предложил их даже пронумеровать

Хыхы, ну все, кому-то бессонница гарантированна ))

тот, вариант, который ты предлагаешь, даёт тот же ответ : фальшивка легче оригинала.

[kevindark]

Я, короче, нифига не математик, поэтому у меня мозги сломаются чето высчитывать. Но походу мне кажется, что нужно после первого взвешивания менять монеты из всех кучек местами, зная, что те из них, которые взяты из оставшейся кучки - стопудово нормальные. Опять же, с ламерской точки зрения гуманитария, по идее 2 оставшихся взвешиваний для этого должно хватить, поскольку, раз уж мы с одного хода определили 4 нормальных (треть всех), то за два оставшихся доберемся до искомой (сорри, если это точно ламерски)

[Мася]

Нумеруем.. взвешиваем по четыре монеты ( по одной из каждой кучки)
Если результаты взвешивания были: слева легче, равно, справа легче, то фальшивая та монета "N", которая легче остальных.

Сообщение отредактировал Мася - Apr 27 2009, 23:02

[King]

Нумеруем.. взвешиваем по четыре монеты ( по одной из каждой кучки)
Если результаты взвешивания были: слева легче, равно, справа легче, то фальшивой может быть только монета "N", которая легче остальных.

Лена, мы не знаем, легче монета или тяжелее. Вот не знаем и пипец)

Сообщение отредактировал King - Apr 27 2009, 23:01

[VGS]

Про бирки - это очень правильная идея!
Я бы предложил их даже пронумеровать

Хыхы, ну все, кому-то бессонница гарантированна ))

Кака бессонница?!!! Пост 26+пост33!!!

Сообщение отредактировал VGS - Apr 27 2009, 23:02

[Мася]

Лена, мы не знаем, легче монета или тяжелее. Вот не знаем и пипец)

ну, кому как, а мне бессонная ночь обеспечена.... Вот и встряхнула мозги

[semesh]

Взвешиваем два раза по две монеты, второй раз меняя 2 монеты местами.

например:

1,2 против 3,4
1,3 против 2,4

получили результат

1,2 < 3,4
1,3 < 2,4
фальшивая монета №1


Если наоборот, то фальшивая монета которая ушла

Если разніе значения больше менше - неповезло

Кака бессонница?!!! Пост 26+пост33!!!

нет пост 32

[King]

Кака бессонница?!!! Пост 26+пост33!!!

Вы не хотите внимательно исследовать все случаи, а не самые простые "частные"

Что делать, если мы взвесили две кучки по 4 шт., и весы отклонились? Причем мы не знаем, в какой из двух куч фальшивая монета. Знаем только, что в этих двух.

[Norua]

Про бирки - это очень правильная идея!
Я бы предложил их даже пронумеровать

А, ну тогда проще. Скатываемся в троичную систему Записваем от 1-го до 12-и в троичной, меняем 2 на 0 а 0 на 2, и т.д. Долго объяснять, но суть в этом?

[VGS]

Объединяю два своих поста в один:
1. кидаем по 4 монеты. Вес равный.
2. добавляем по одной монете в каждую чашу.
3. если равновесие сохраняется, значит монета-одна из двух оставшихся. Берём любую и взвешиваем с одной из монет, которая на весах. Если вес одинаковый-значит фальшивка осталась не взвешенной
А если вес не равный, значит одна из двух монет (последних)-фальшивая.
Стало быть берём одну из этих двух монеток и взвешиваем с любой из первых восьми(4+4)
Если первая по весу одинаковая-значит вторая-фальшивка.

[King]

Объединяю два своих поста в один:
1. кидаем по 4 монеты. Вес равный.

Кидаем по 4 монеты. Вес неравный. Дальше?

А, ну тогда проще. Скатываемся в троичную систему Записваем от 1-го до 12-и в троичной, меняем 2 на 0 а 0 на 2, и т.д. Долго объяснять, но суть в этом?

Самый простой вариант - тупо перебором и комбинированием. Но вообще есть алгоритм для N взвешиваний

Кстати, есть миф, что людей, которые решали эту задачу в течение двух часов - брали работать на Лондонскую фондовую биржу

Сообщение отредактировал King - Apr 27 2009, 23:18

[VGS]

Кидаем по 4 монеты. Вес неравный. Дальше?


Самый простой вариант - тупо перебором и комбинированием. Но вообще есть алгоритм для N взвешиваний

Изначально ты высказывал такую теорию:
В идеале, когда мы взвесили 2 кучки по 4 монетки они должны быть равны по весу. Тогда мы точно знаем, что фальшивая монета в третьей нетронутой кучке.


Целенаправленно ввёл в заблуждение

Сообщение отредактировал VGS - Apr 27 2009, 23:20

[King]

Изначально ты высказывал такую теорию:
В идеале, когда мы взвесили 2 кучки по 4 монетки они должны быть равны по весу. Тогда мы точно знаем, что фальшивая монета в третьей нетронутой кучке.

Я сказал, что это идеальный частный случай. Мы задачу решаем или как?)

[Norua]

Самый простой вариант - тупо перебором и комбинированием. Но вообще есть алгоритм для N взвешиваний

Кстати, есть миф, что людей, которые решали эту задачу в течение двух часов - брали работать на Лондонскую фондовую биржу

Перебор не перебор, но к третьему взвешиванию мы знаем номер фальшивки Вариант с одной чашей и двумя взвешиваниями изящней. Люблю физику )

[kevindark]

Так, допустим у нас кучки 1234, 5678, 9,10,11,12. Перевес /

Мы знаем, что 9-10-11-12 - правильные монеты.

На второе взвешивание берем в левую чашу например монету 1 и 3 штуки из правой чаши. Например, 6-7-8. В правой остается монета 5, плюс мы к ней добавим 3 монеты из стопудово честных. Получается, что если перевес останется, то левандосовская либо монета 1 (тяжелая), либо монета 8 (легкая). Если выровнялось, то выходит, что гнали монеты, которые мы забрали из левой чаши. А если перекосило в другую сторону, получается, что козлина, которую мы ищем, находится среди 6-7-8.

Если перевес остался - берем наманую монету и вешаем с 1. Если ровно - фальшивая 8. Если перекос - все понятно, причем даже станет понятно, легкая она или тяжелая. Если ищем среди 2-3-4, то знаем, что фальшивая тяжелее, так как весы выровнялись, значит берем 2 и 3 и смотрим. Если ровно - мы искали 4. Если перевес - мы искали тяжелую. Ну с монетами 6-7-8 та же херня тока наоборот.

Вроде ниче не напутал.

Боря, ты засранец, я сто лет ручкой по листу не писал)

Сообщение отредактировал kevindark - Apr 27 2009, 23:30

[King]

Перевирая известного классика:
"Пишите, Шура, пишите" )))

Ты уже близок к финальному решению
У тебя получается 4 взвешивания итого. Но ход мыслей абсолютно верен)

Ладно, чтобы не мучался Второе взвешивание не по 4 монеты

Сообщение отредактировал King - Apr 27 2009, 23:57

[kevindark]

Не понял, почему 4??! три.. первым определяем эталонную кучку, вторым определяем одну из трех комбинаций, в которых есть левая монета, третьим определяем монету...

[King]

Не понял, почему 4??! три.. первым определяем эталонную кучку, вторым определяем одну из трех комбинаций, в которых есть левая монета, третьим определяем монету...

6-7-8 не найти за одно взвешивание....

[kevindark]

Как это не найти? Я ж написал как) Почему это может быть не так?

[King]

Как это не найти? Я ж написал как) Почему это может быть не так?

Смотри, 6-7-8 переставили, перекосило в другую сторону.
Как нам извлечь за одно взвешивание неправильную монету из 6-7-8?
Одна монета лишняя.

[kevindark]

Смотри, 6-7-8 переставили, перекосило в другую сторону.
Как нам извлечь за одно взвешивание неправильную монету из 6-7-8?
Одна монета лишняя.

Взвешиваем 6 и 7. Если ровно, 8 - фальшивка. При перекосе фальшивка та, что легче.

[King]

Взвешиваем 6 и 7. Если ровно, 8 - фальшивка. При перекосе фальшивка та, что легче.

Все верно, сорри, невнимательно прочитал один из постов (засыпал уже)

Поздравляем Кевина!

1-е взвешивание:
1-2-3-4 / 5-6-7-8

2-е взвешивание:
если
1-6-7-8 / 5-9-10-11, то
Либо монета 1, либо монета 5 фальшивые.

если
1-6-7-8 = 5-9-10-11, то
фальшивка в 2-3-4 и она тяжелее.

если
1-6-7-8 \ 5-9-10-11, то
фальшивка в 6-7-8 и она легче.

Дальше все просто.

Второй вариант решения:
Нумеруем шары 1, 2, 3, 4, ... 12.

Делим на три части по 4 шары: (1 2 3 4) (5 6 7 8 ) (9 10 11 12)
1. Взвешиваем первые две группы (1 2 3 4) и (5 6 7
Если они равны, то искомый шар точно в третьей группе.
2. Взвешиваем шары по два (9 10) и (1 12) - тут шар 1 точно не искомый. Если они равны, то искомый шар 12. Если нет, то запоминаем состояние весов (тяжелее/легче).
3. Взвешиваем шары (9 10). Если они равны, то искомый шар 11.
Если состояние весов не изменилось, то искомый шар 9. Если состояние весов изменилось, то искомый 10.

Если после первого взвешивания группы разного веса, то запоминаем состояние весов.
2. Взвешиваем по три шара (1 2 5) и (3 6 12). Если они равны, то шар 4 или 8 искомый. Шар 12 точно не искомый.
3. Взвешиваем шары (4 12). Если равны, то искомый шар 8. Если нет, то искомый шар 4. Finish.

Если состояние весов изменилось после второго взвешивания, то искомый шар 3 или 5.
3. Взвешиваем (3 12) получаем решение. Равны - искомый 5, неравны - искомый 3.
3. Если состояние не изменилось, то взвешиваем шары (1 12). Если равны - искомый 2, если нет - искомый 1.

Плюс второго алгоритма, что таким способом проще писать алгоритм для M шаров и N взвешиваний.

Сообщение отредактировал King - Apr 28 2009, 11:40

[Cy4enok]

А_А_А_А_А_А_А_ - мозК поламал!!!