Проект основателей компании «Ваш репетитор»
ERUDITOR.RU

65. Фальшивая монета

Из 12 монет одна фальшивая. Она имеет массу, отличную от массы настоящих монет (но неизвестно — легче или тяжелее). Необходимо за три взвешивания на равновесах определить фальшивую.
Прим. ред.
Известная классическая задача. Те, кто увлекается задачками, её знает. Кто не увлекается — за разумное время её не решит.
2008-08-28

Обсуждение


Задачи :: фальшивая монета
↓↓ 0 ↑↑   САН (7 / 34)   29 авг 2008 17:02   »»


САН: Вы уверены в правильности постановки задачи?
По моему, не зная знака отличия (тяжелее или легче), задачка решается только для 11 монет. (зная знак для 27)
Взвешиваем 3 и 3 монеты, затем тройку из первого взвешивания и тройку из оставшихся. если хоть в одном взвешивании было отклонение, томы определили тройку с фальшивой монетой и знак. Дальше одним взвешиванием нашли фальшивую.
В случае, если оба взвешивания равны, то фальшивая монета в оставшихся. Если монет было 12, то одним взвешиванием нужно найти фальшивую из трех, не зная знака - это невозможно! а из двух -легко. Т.е. монет должно быть 11.
З.Ы. Я сам хотел выложить эту задачку (никак не получалось зарегистрироваться, Вы опередили :-)), но в чуть усложненном варианте:
сколько взвешиваний нужно для 11 монет (в Вашем варианте уже содержится подсказка, что их 3)
↓↓ 0 ↑↑   ssparh (4 / 4)   30 мар 2007 10:58   «« #2 »»   Ответить


для ssparh
Задача корректна и имеет однозначное решение.
↓↓ 0 ↑↑   САН (7 / 34)   30 мар 2007 16:25   «« #3 »»   Ответить


© Константин Кноп:
http://www.computerra.ru/offline/1997/228/969/
↓↓ 0 ↑↑   eruditor (129 / 439)   31 мар 2007 02:23   «« #4 »»   Ответить


Не слабо!
А я решал задачу не имея представления о теории информации и криптографии, без нумерации и используя только логику.
↓↓ 0 ↑↑   САН (7 / 34)   02 апр 2007 09:45   «« #5 »»   Ответить


А где в решении они используются?
↓↓ 0 ↑↑   eruditor (129 / 439)   02 апр 2007 09:50   «« #6 »»   Ответить


Константин Кноп
"Постскриптум

Эти с виду игрушечные задачи имеют самое непосредственное отношение к теории информации и криптографии."
Я так понимаю, что задачи, представленные на на "Эрудиторе" должны быть "по-зубам" ученику 7-го класса. Чтобы воспользоваться алгоритмом, приведённым в статье, необходимо , для начала, этот алгоритм вывести.
↓↓ 0 ↑↑   САН (7 / 34)   02 апр 2007 10:00   «« #7 »»   Ответить


кто-нибудь предложит логичное решение?
↓↓ 0 ↑↑   САН (7 / 34)   04 апр 2007 17:14   «« #8 »»   Ответить


А что, кноповское - нелогичное?
↓↓ 0 ↑↑   eruditor (129 / 439)   04 апр 2007 17:54   «« #9 »»   Ответить


Условие задачи поставлено неправильно.
С данными задачи, игнорируя Кноповское решение и полагаясь только на логику, невозможно на все 100% решить задачу.

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

----------------------------------------------
Задача усложняется если мы не знаем: фальшивая монета - легкая или тяжелая?

делим монеты, также, на 4 группы по три монеты

1.1 1-е взвешивание: между собой две группы (3-3), если равны -> 1.2.1 не равны -> 1.2.2

1.2.1 2-е взвешивание: если предыдущие группы были равны, то значит они эталонные. берем любую другую группу монет и взвешиваем с одной из эталонных (3-3),
если они равны -> 1.3.1.1, если неравны -> 1.3.1.2
1.2.2 2-е взвешивание: если предыдущие группы были неравны, то значит в одной из них фальшивка (другие две группы эталонные(метод исключения)), сравниваем с эталонной (3-3), если они равны -> 1.3.1.1, если неравны -> 1.3.2.3
(Важное уточнение: когда взвешиваем неравные группы монет, необходимо заметить с какой группой мы взвешиваем эталон (легкой или тяжелой),
если при взвешивании с легкой группой весы равны, значит тяжелая группа с фальшивкой, либо наоборот. здесь мы определили свойство фальшивки - она тяжелее(легче) настоящей монеты)

1.3.1.1 3-е взвешивание: если они равны, то значит в последней оставшейся группе из 3-х монет есть фальшивка, проводим последнее взвешивание двух монет (1-1).
итог1

1.3.1.2 3-е взвешивание: взвешивание двух монет (1-1). если весы показали, что они не равны, тогда невозможно сказать, которая из двух монета фальшивая.
итог2

1.3.2.3 3-е взвешивание: определив таким образом свойство монеты - тяжесть(легкость), взвешиваем две монеты группы (1-1).
если равны -> итог 1, неравны -> итог 3.


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

в итоге верный результат можно дать с 80% точностью (итог1(3 раза) и итог3 против итога 2).
--------------------------------------------------------------------------------------------------
↓↓ 0 ↑↑   The i (0 / 1)   15 апр 2007 00:25   «« #10 »»   Ответить


Что значит "игнорируя Кноповское решение"?
↓↓ 0 ↑↑   eruditor (129 / 439)   15 апр 2007 13:31   «« #11 »»   Ответить


повторюсь: задача имеет однозначное решение. Без составления таблиц.
↓↓ 0 ↑↑   САН (7 / 34)   23 апр 2007 16:24   «« #12 »»   Ответить


однозначное решение.
Взвешиваем по 4.
1. Если равны, то очевидно - фальшивка (Ф) в оставшихся, берем оттуда 2 и взвешиваем с 2мя хорошими, ну думаю дальше фсё ясно...
2. Если не равны:
Пронумеруем:
2.1. 1234>5678.
2.2. Взвешиваем
156 и 278.
2.2.1. 156=278, тогда очевидно, что Ф среди 34...
2.2.2. 156>278, => Ф среди 178 (додумайте сами), причем 1 м.б. только тяжелее, а 78 - легче, взвешивая 7 и 8 находим Ф.
2.2.3. 156<278, аналогично Ф среди 256. Фсё.
↓↓ 0 ↑↑   igar (10 / 119)   26 июн 2007 13:33   «« #13 »»   Ответить


Ещё раз классика!
Решил эту задачу, учась в девятом классе, за что получил 5 в четверти :) Только вот искать надо из 13(!) монет. Решение есть точно. Прекрасно помню его до сих пор :) Так что Кноп - не авторитет :)
↓↓ 0 ↑↑   -V@Ndal- (7 / 31)   27 дек 2008 07:26   «« #14 »»   Ответить


Абсолютно верно igar!
↓↓ 0 ↑↑   seba (0 / 6)   08 янв 2009 17:50   «« #15 »»   Ответить


хе только верно то для рассуждения 2 , а для 1 : "Если равны, то очевидно - фальшивка (Ф) в оставшихся, берем оттуда 2 и взвешиваем с 2мя хорошими, ну думаю дальше фсё ясно..."
а если опять равны, то остается 2 монеты как узнать, которая Ф!
↓↓ 0 ↑↑   seba (0 / 6)   08 янв 2009 19:47   «« #16 »»   Ответить


Поправим: 1. Если равны, то очевидно - фальшивка (Ф) в оставшихся, берем оттуда 3 и взвешиваем с 3мя хорошими, ну думаю дальше фсё ясно... :-) + 2 пункт igar'a - ТЕПЕРЬ ПРАВИЛЬНО!
↓↓ 0 ↑↑   seba (0 / 6)   08 янв 2009 19:59   «« #17 »»   Ответить


Мне в 10-м задачу другую задали:Найти максимальное число монет, для которых это возможно.
Что 13 понятно сразу, но как всегда нет оценки. более-менее математически доказал только уже в 11-м. Так почему нельзя для 14-и?
↓↓ 0 ↑↑   Paha (0 / 62)   09 янв 2009 01:54   «« #18 »»   Ответить


Почему нельзя для 14-и
Вот почему : Разобьем на три четвертки и одну двойку и попробуем решить.
Взвешиваем по 4:
1. Если не равны уже обсуждалось см. выше
2. Если равны: берем 3 из оставшейся четверки и взвешиваем с 3 хорошими, если не равны, то повезло;
иначе: имеем три монеты без признака фальшивости ( легче или тяжелее фальшивая монета ) из которых одним
взвешиванием фальшивку не найти!
↓↓ 0 ↑↑   seba (0 / 6)   25 янв 2009 20:13   «« #19 »»   Ответить


А формулировка правильная?
Я думаю что даже имея две монеты(настоящую и фальшивку) и взвесив их мы не определим какая фальшивка так как мы не знаем какая монета тяжелее. Мы лишь будем знать, что одна перевесит другую.
↓↓ 0 ↑↑   Rus_17-91 (0 / 12)   03 май 2009 21:37   «« #20 »»   Ответить


А если знать (допустим что фальшивка тяжелее) то, сначала взвешиваем 3 монеты с одной и 3 с другой стороны, если одна из сторон перевесит, то убираем с каждого края по одной монете и когда останется по одной с каждой стороны то мы определим какая фальшивая. А если после первого взвешивания не одна сторона не перевесит то монеты стоит добавлять.
↓↓ 0 ↑↑   Rus_17-91 (0 / 12)   03 май 2009 21:42   «« #21 »»   Ответить


Решение здесь
Решение задачи на моём блоге
http://mathandprog.blogspot.com/2009/08/12.html
↓↓ 0 ↑↑   da80 (0 / 1)   19 авг 2009 21:39   «« #22 »»   Ответить


не асилил! слишкам многа букаф!)
надоело читать всякие бредни! 4+4+4! найти фальшивую не прблема одним взвешиванием! далее 2+2 здесь или сразу высянится она или же потом еще разок 1+1!
↓↓ 0 ↑↑   lavsvip (-124 / 40)   18 окт 2010 17:02   «« #23 »»   Ответить


Можно и 14 монет разрулить
Но извращённым способом. Или имея в запасе ещё одну, точно настоящую монетку...
↓↓ 0 ↑↑   SergeyASh (4 / 36)   28 ноя 2010 06:24   «« #24 »»   Ответить


решение есть абсолютно точно (кноповские таблицы не смотрел)
Можно и 14 монет разрулить //SergeyASh : (48 дн. назад)
Но извращённым способом. Или имея в запасе ещё одну, точно настоящую монетку..

выкладывайте...
допустим образовалось неравенство(ЭБ=Эталон, либо больше, ЭМ=эталон, либо меньше) ЭБ ЭБ ЭБ ЭБ > ЭМ ЭМ ЭМ ЭМ ,
тогда отложенная группа монет (Э Э Э Э) (если б равенство, то в отложенной фальш, берем три от туда приравниваем с эталоном: равенство:отложеная монетка фальш, неравенство: запоминаем знак, сравниваем две любые из этих трех:равенство, отложенная фальш, неравенство: фальш та, которая с запомненым знаком оказалась)
Формируем группы таким образом: откладываем ЭБ ЭБ ЭМ , сравниваем (ЭБ ЭБ ЭМ ЭМ) (Э Э ЭМ Э). 1) равенство: взвешиваем две ЭБ из отложенной, какая больше та и фальш, равены, фальш третья. 2) Больше: взвешиваем две ЭБ из первой группы, какая больше та и фальш, равенство фальш ЭМ из второй группы. 3)Меньше: взвешиваем две ЭМ из первой какая меньше, та и фальш, равенство, фальш ЭМ из второй группы. вроде все, и знаем точно знак фальшивки. По хорошему бы все манетки пронумеровать ЭБ1 ЭБ2... но это не принцепиально
↓↓ 0 ↑↑   Blabber (0 / 14)   15 янв 2011 17:42   «« #25 »»   Ответить


Правильный ответ
делим монеты на две части по 6. находим фальшивую она будет легче. потом еще делим по 3 и снова находим фальшивую сторону она тоже будет легче. в конце берем оставшиеся 3 монеты и взвешиваем только 2, а 1 оставляем с краю, если на весах одна легче, то она и есть фальшивая, на если они равны, то фальшивая лежит с краю не на весах.
↓↓ 0 ↑↑   rad (0 / 2)   28 апр 2011 18:57   «« #26 »»   Ответить


Нам неизвестна масса монетки. Ты не можешь с 1ого взвешивания сразу определить какая сторона фальшивая.
↓↓ 0 ↑↑   borjomi (0 / 5)   26 сен 2013 00:48   «« #28 »»   Ответить


а для 46 монет? как доказать, что за 3 взвешивания не возможно? так же по трисекциям?
↓↓ 0 ↑↑   wert (0 / 1)   27 май 2013 09:25   «« #27 »»   Ответить


Если монет N, то число вариантов расположения фальшивой монеты 2N (N, если она легче и еще N, если она тяжелее).
Весы имеют 3 состояния. За n взвешиваний переберем 3^n состояний. Значит в любом случае 3^n>=2N. Если взвешиваний 3, то 3^3=27. Для 13 монет может подойти (2*13=26<27), а больше — нет.
↓↓ 0 ↑↑   Михаил (-4 / 8)   12 мар 2014 10:40   «« #33 »»   Ответить


1.Кладем по 6 монеток на обе стороны весов. Потом СНИМАЕМ с каждой стороны ПО ОДНОЙ монетки. Если после снятия первых двух весы показали равенство, значит одна из двух снятых — фальшивая. Если нет, снимаем ещё по одной с каждой стороны, потом ещё по одной и т.д. До тех пор, пока не установится равновесие. Короче, при одном из пяти снятий устанавливается равновесие, и ОДНА из ДВУХ СНЯТЫХ ЯВЛЯЕТСЯ ФАЛЬШИВОЙ !!! Ну, или одна из двух последних, оставшихся на весах
2.Дальше — проще. Любую из двух выявленных сравниваем с эталоном (любой из прочих 10). Если равенство, то оставшаяся фальшивая. Если нет, то положенная на весы.
Зачем третье взвешивание?
↓↓ 0 ↑↑   mskeltMinskBelarus (0 / 1)   08 окт 2013 04:33   «« #29 »»   Ответить


Браво, вы решили задачу в семь взвешиваний! ;-)
↓↓ 0 ↑↑   Кузнецов Сергей Германович (264863 / 13798)   08 окт 2013 21:34   «« #30 »»   Ответить


А разве фальшивая монета не может быть одинакового веса с настоящей?
↓↓ 0 ↑↑   Бехтиев Илья Викторович (1369 / 23227)   15 окт 2013 11:29   «« #31 »»   Ответить


В условии же сказано:
<< Из 12 монет одна фальшивая. Она имеет массу, отличную от массы настоящих монет (но неизвестно — легче или тяжелее). >>
↓↓ 0 ↑↑   Кузнецов Сергей Германович (264863 / 13798)   19 окт 2013 10:24   «« #32 »»   Ответить


В свое время, когда я размышлял над этой задачей, я вышел на более общую:

С каким максимальным количеством монеток можно решить эту задачу за n взвешиваний

При решении этой задачи получается, что, к примеру, за три взвешивания можно определить фальшивку из 13 монеток, за 4 взвешивания — 40, а, скажем, за семь взвешиваний (на идеальных весах): 1093.
↓↓ 0 ↑↑   Абрамов Виктор Алексеевич (62840 / 2408)   12 мар 2014 12:16   «« #34 »»   Ответить


↓↓ 0 ↑↑   Permafrost (0 / 2)   03 дек 2015 17:32   «« #35 »»   Ответить


↓↓ 0 ↑↑   Permafrost (0 / 2)   03 дек 2015 17:57   «« #36 »»   Ответить


Разбиваем монеты на 3 группы по 4.

Ветка 1:

1. Взвешиваем группы 1 и 2. Их вес отличается.


2. Снимаем 3 монеты с чаши №1. Кладём в неё 3 монеты из оставшейся группы, и оставшуюся с первого взвешивания монету из чаши 1 меняем местами с любой монетой из чаши 2. Если монета находится в тройке монет оставшихся с первого взвешивания в чаше 2, то на весах ничего не изменится. Если на весах снова будет не равно, но чаши примут положение противоположное первому взвешиванию, значит она — одна из двух монет, которые мы поменяли местами. Если же весы уравнялись, то монета — в группе тех трёх, что были сняты с весов.

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


Ветка 2:

1. Взвесили две группы монет по 4 штуки и они равны. Монета — в третьей.

2. Взвешиваем 2 любые монеты.

3. Снимаем любую из них и кладём третью. Если на весах было равно, а стало не равно, то нужная монета — только что положенная. Если было равно и ничего не изменилось — та, которую не взвешивали. Если было не равно, а стало равно — снятая. Было не равно и осталось не равно — та, которую взвешивали оба раза.
↓↓ 0 ↑↑   Гидон (0 / 19)   08 апр 2016 12:07   «« #37 »»   Ответить


Увидел интересное предложение среди комментариев — узнать для какого максимального кол-ва монет можно это сделать, ну тут ход мыслей ясен — 1).мы делим на 3 группы, и взвешивая 2 из них, можем сделать вывод о соотношении всех трех. 2). Сделать это мы можем только 3 раза. 3). В конечном итоге мы должны придти к взвешиванию одиночных монет, таким образом получить максимальное количество монет для которых это возможно , можно 3 раза умножив единицу на 3, то есть 1*3*3*3 = 27 монет. Теперь пойдем обратным путем и убедимся в том что это так — 1). взвешиваем по 9 монет и понимаем в какой из трех групп находится фальшивка, 2). Взвешиваем по 3 монеты и понимаем в какой из трех групп находится фальшивка, 3). взвешиваем по одной монете и понимаем какая монета фальшивая.
↓↓ 0 ↑↑   Марк Мурадян (0 / 10)   05 сен 2016 21:33   «« #38   Ответить



Ваше имя
Email
Текст ответа
© 2006-2017   Авторы