Проект основателей компании «Ваш репетитор»
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 (128 / 439)   31 мар 2007 02:23   «« #4 »»   Ответить


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


А где в решении они используются?
↓↓ 0 ↑↑   eruditor (128 / 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 (128 / 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 (128 / 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 ↑↑   Кузнецов Сергей Германович (266621 / 13838)   08 окт 2013 21:34   «« #30 »»   Ответить


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


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


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

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

При решении этой задачи получается, что, к примеру, за три взвешивания можно определить фальшивку из 13 монеток, за 4 взвешивания — 40, а, скажем, за семь взвешиваний (на идеальных весах): 1093.
↓↓ 0 ↑↑   Абрамов Виктор Алексеевич (64580 / 2465)   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 »»   Ответить


На самом деле задача решаема даже для 13 шариков. Но если изначально знать, что 13 максимум, то задача, как бы это странным не казалось, решается легче, потому что много ложных путей изначально отсекаются.
Кто хочет решить эту задачу после этой подсказки, не читайте мой следующий пост ;-)
↓↓ 0 ↑↑   Дима (0 / 3)   24 авг 2017 15:17   «« #39 »»   Ответить


Общего решения для n взвешиваний пока не нашёл, но вот для 13, причём 13 максимальное число для трёх взвешиваний. Доказательтво ниже
Для начала пронумеруем шарики от 1 до 13 и введём сокращеия:
- нормальный шрик (НШ)
- фальшивый шарик (ФШ)
- левая половина весов (ЛП)
- правая половина весов (ПП)

При (1.) взвешивании помещаем на ЛП шарики [1, 2, 3, 4], а на ПП шарики [5, 6, 7, 8]. Теперь есть три возможных исхода:
1) ЛП оказалась тяжелее ПП. Из этого следует:
а) шарики [9, 10, 11, 12, 13] настоящие
б) один из шариков 1-8 фальшивый, причём если фальшивым является один из шариков 1-4, то он легче настоящих, а если один из шариков 5-8, то тяжелее.
При (2.) взвешивании помещаем на ЛП [1, 2, 3, 5], на ПП [4, 9, 10, 11]. Здесь опять есть три возможных исхода:
1.1) ЛП оказалась тяжелее ПП. Из этого следует:
а) шарик 4 был при (1) взвешивании на "тяжёлой" половине, а теперь на "лёгкой". Из этого следует, что он настоящий, потому что фальшивый должен каждый раз быть легче или каждый раз быть тяжелее остальных.
б) так как остальные шарики на ПП тоже настоящие, а весы не находятся в равновесии, то очевидно, что ФШ лежит на ЛП и он тяжелее НШ.
в) из шариков [1, 2, 3, 5] при первом взвешивании на "тяжёлой" ЛП находились шарики [1, 2, 3], то есть один из них ФШ и он тяжелее НШ.
При (3.) взвешивании помещаем на ЛП шарик [1], а на ПП шарик [2]. Тот, который тяжелее и есть ФШ. Если весы в равновесии, то шарики [1, 2] настоящие, а фальшивый шарик номер 3.
1.2.) ЛП оказалась легче ПП. Из этого следует:
а) шарики [1, 2, 3] при (1) взвешивании на "тяжёлой" половине, а теперь на "лёгкой". Из этого следует, что они настоящие, потому что фальшивый должен каждый раз быть легче или каждый раз быть тяжелее остальных.
б) один из шариков 4 или 5 ФШ, так как 4 оба раза был на "тяжёлой", а 5 оба раза на "лёгкой" стороне весов, а все остальные шарики при этом взвешивании НШ и весы не в равновесии.
При (3.) взвешивании помещаем на ЛП шарик [4], а на ПП шарик [1] (он точно настоящий!). Если 4 тяжелее, то он ФШ, если вес одинаков, то ФШ номер 5. Легче нормально он быть не может, поэтому такой исход исключён!
1.3) ЛП и ПП находятся в равновесии. Из этого следует:
а) шарики [1, 2, 3, 4, 5] настоящие
б) один из шариков [6, 7, 8] фальшивый. Так как при первом взвешивании они все лежали на ПП, которая была легче ЛП, то ФШ легче НШ.
При (3.) взвешивании помещаем на ЛП шарик [6], а на ПП шарик [7]. Тот, который легче и есть ФШ. Если весы в равновесии, то шарики [6, 7] настоящие, а фальшивый шарик номер 8.
2) ЛП оказалась легче ПП. Здесь можно было опять подробно описать, как в предыдущем примере,но я поступлю как математик: приведу этот пример к предыдущему, доказав его тем самым.
Мы просто перенумеруем шарики таким образом: 1 → 5; 2 → 6; 3 → 7; 4 → 8; 5 → 1; 6 → 2; 7 → 3; 8 → 4. Также преименовываем ЛП в ПП, а ПП в ЛП. Теперь исход в точности выпоняет условие пункта 1., который решается в три взвешивания.
3) ЛП и ПП в равновесии. Из этого следует:
а) шарики 1-8 НШ
б) один из шариков 9-13 ФШ
При (2.) взвешивании помещаем на ЛП [1, 2, 3] (они точно все настоящие), на ПП [9, 10, 11]. Здесь опять есть три возможных исхода:
3.1.) ЛП оказалась тяжелее ПП. Из этого следует, что один из шариков [9, 10, 11] ФШ, и он легче НШ.
При (3.) взвешивании помещаем на ЛП шарик [9], а на ПП шарик [10]. Тот, который легче и есть ФШ. Если весы в равновесии, то шарики [9, 10] настоящие, а фальшивый шарик номер 11.
3.2.) ЛП оказалась легче ПП. Из этого следует, что один из шариков [9, 10, 11] ФШ, и он тяжелее НШ.
При (3.) взвешивании помещаем на ЛП шарик [9], а на ПП шарик [10]. Тот, который тяжелее и есть ФШ. Если весы в равновесии, то шарики [9, 10] настоящие, а фальшивый шарик номер 11.
3.3.) весы в равновесии. Из этого следует:
а) шарики [9, 10, 11] тоже НШ
б) один из шариков [12, 13] ФШ
При (3.) взвешивании помещаем на ЛП шарик [1] (он настоящий), а на ПП шарик [12]. Если весы в равновесии, то ФШ с номером 13, если не в равовесии, то ФШ имеет номер 12.

Доказательство, что 13 шариков максимальное число для трёх взвешиваний:
Начнём с конца. Из каких комбинаций можно с помощью одного взвешивания узнать ФШ. Заметим, что при взвешивании мы можем положить максимально один шарик на каждую половину весов. Если шариков будет больше, то мыы не будем знать, который из них фальшивый даже после взвешивания, что протиоречит заданию, которое мы поставили: установить ФШ с помощью ОДНОГО взвешивания.
То есть два шарика, мы положим на весы и можем максимально один оставить, так как если оставленных будет больше и после взвешивания выяснится, что ФШ среди них, то мы опять не будем знать, который.
Получается, что перед последним взвешиванием может быть максимально 3 шарика, среди которых один фальшивый. Это теоретическая верхняя граница. Посмотрим, можно ли достичь её практически. Для начала пронумеруем шары 1, 2, 3. Формулировка "если известно" подразумевает, что эту информацию мы имеем на данный момент, например из предыдущих взвешиваний:
- Если известно, что ФШ тяжелее (легче) ФШ чем НШ, то задача с тремя шарами решается так: на ЛП помещается [1], на ПП [2]. Тот который тяжелее (легче) другого и является ФШ. Если весы в равновесси, то шарик 3 фальшивый.
- Если известно, что если ФШ один из [1, 2], то он тяжелее (легче) НШ-а, а если ФШ с номером 3, то легче (тяжелее). Тогда это решается так: на ЛП помещается [1], на ПП [2]. Тот который тяжелее (легче) другого и является ФШ. Если весы в равновесси, то шарик 3 фальшивый. То есть решение идентично предыдущему пункту. Разница в том, что в предыдущем пункте было всё равно какие шарики помещать на весы, а какой оставлять, то здесь нет!
Если перед последним взвешиванием всё ещё не известно, тяжелее ФШ или легче НШ, то эту проблему можно решить только для 2 шариков [1, 2] и одного шарика [3], про который мы точно знаем, чо он НШ. Это решается так: на ЛП помещается [1], на ПП [3]. Если весы в равновесии, то шарик [2] является ФШ, если не в равновесии, то шарик [1] является ФШ.
Задача с тремя шариками, один из которых ФШ, но неизвестно тяжелее он или легче НС, и произвольного количества НШ не решаема в одно взвешивание! В самом деле, как доказано выше при последнем взвешивании мы должны положить по одному шарику на каждую половину весов. Тогда если мы возьмём шарики [1] и [2], то в случае неравновесия мы всё ещё не знаем, который из них ФШ. Если же мы возьмём только шарик [1] и взвесим его с НШ, то в случае равновесия мы опять не будем знать, который из шариков [2] и [3] является ФШ.
Теперь решим следующую задачу: имеется n шариков (назовём это множеством М), один из которых фальшивый, и неизвестно тяжелее он или легче настоящего, и произвольное количество НШ. Каково максимальное значение n для решения задачи в два взвешивания. Для одного взвешивания n = 2 и поэтому при первом взвешивании мы можем оставить не взвешенными максимально 2 шарика, на тот случай, если весы будут в равновесии. Если при первом взвешивании мы поместим на весы k (k>=4) шариков из М, то возможно два варианта:
— все k шариков из М лежат на одной половине; на другой половине только НШ. Тогда если весы не в равновесии, то мы узнаём, что ФШ легче или тяжелее НШ. Но так как мы взвесили больше трёх шариков, то за одно взвешивание невозможно определить, который из k шариков фальшивый.
- m (1 <= m <= (k-1)) шариков лежит на ЛП и (k-m) на ПП. Если весы не в равновесии, то после взвешивания, мы знаем, что даже не узнаем, тяжелее ФШ чем НШ или легче.
Отсюда следует, что k может быть максимално равно трём, а с двумя шариками, которые мы не взвешиваем первый раз получсем n = k + 2 = 3 + 2 = 5. Именно этот случай описан в пункте 3.) в описании решения.
Это приводит нас к выводу, что при первом взвешивании может быть не взвешено максимально 5 шариков. Если мы оставим больше шариков и весы при первом взвешивании окажутся в равновесии (т.е. все шарики настоящие), то мы придём к задаче, в которой за два взвешивания надо, без знания тяжелее он или легче, определить ФШ из числа большего 5. Как было доказано выше это невозможно! С числом шариков, которые можно не взвешивать в первый раз мы определились: это 5. Теперь надо определить максимальное число шариков, которые можно взвешивать в первый раз. В сумме с пятью это даст нам верхнюю теоретическую границу для числа шариков. Реальная может быть ниже.
В решении я показал, что это решается для 8 шариков, то есть по 4 на каждую чашу весов. В сумме это даёт 8 + 5 = 13 шариков. Для того, чтобы найти фальшивый шарик из большго изначального количества, при первом взвешивании надо положить минимум 10 шариков на весы, то есть по пять на каждую половину. Но это невозможно по следующей причине: если весы после первого взвешивания не в равновесии, то один из 10 шариков фальшивый. Но это невозможно пределить за два взвешивания, потому что эта задача неразрешима даже в наиболее простом варианте: если известно, легче ФШ чем НШ или тяжелее. В этом случае шисло шариков максимально 9 (три в степени количества взвешиваний; в этом случае 2, то есть три в квадрате равно девяти), а здесь их уже десять.
Исходя из всего этого теоретическая граница равна 8 шарикам при первом взвешивании плюс 5 шарикам, не учавствовавшим в первом взвешивании, 8 + 5 = 13. Она же является и практической границей, как доказывает пример, приведённый мной.
↓↓ 0 ↑↑   Дима (0 / 3)   24 авг 2017 15:17   «« #40   Ответить



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