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

САН: Вы уверены в правильности постановки задачи?
По моему, не зная знака отличия (тяжелее или легче), задачка решается только для 11 монет. (зная знак для 27)
Взвешиваем 3 и 3 монеты, затем тройку из первого взвешивания и тройку из оставшихся. если хоть в одном взвешивании было отклонение, томы определили тройку с фальшивой монетой и знак. Дальше одним взвешиванием нашли фальшивую.
В случае, если оба взвешивания равны, то фальшивая монета в оставшихся. Если монет было 12, то одним взвешиванием нужно найти фальшивую из трех, не зная знака - это невозможно! а из двух -легко. Т.е. монет должно быть 11.
З.Ы. Я сам хотел выложить эту задачку (никак не получалось зарегистрироваться, Вы опередили :-)), но в чуть усложненном варианте:
сколько взвешиваний нужно для 11 монет (в Вашем варианте уже содержится подсказка, что их 3)

для ssparh
Задача корректна и имеет однозначное решение.

Не слабо!
А я решал задачу не имея представления о теории информации и криптографии, без нумерации и используя только логику.

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

Эти с виду игрушечные задачи имеют самое непосредственное отношение к теории информации и криптографии."
Я так понимаю, что задачи, представленные на на "Эрудиторе" должны быть "по-зубам" ученику 7-го класса. Чтобы воспользоваться алгоритмом, приведённым в статье, необходимо , для начала, этот алгоритм вывести.

Условие задачи поставлено неправильно.
С данными задачи, игнорируя Кноповское решение и полагаясь только на логику, невозможно на все 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).
--------------------------------------------------------------------------------------------------

однозначное решение.
Взвешиваем по 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. Фсё.

Ещё раз классика!
Решил эту задачу, учась в девятом классе, за что получил 5 в четверти :) Только вот искать надо из 13(!) монет. Решение есть точно. Прекрасно помню его до сих пор :) Так что Кноп - не авторитет :)

хе только верно то для рассуждения 2 , а для 1 : "Если равны, то очевидно - фальшивка (Ф) в оставшихся, берем оттуда 2 и взвешиваем с 2мя хорошими, ну думаю дальше фсё ясно..."
а если опять равны, то остается 2 монеты как узнать, которая Ф!

seba Что не ясно?
"1. Если равны, то очевидно — фальшивка (Ф) в оставшихся, берем оттуда 2 и взвешиваем с 2мя хорошими, ну думаю дальше фсё ясно..."
После первого взвешивания остается 4 монеты, среди них фальшивая, и за 2 взвешивания ее легко определить. Пронумеруем 9, 10, 11, 12 (монеты 1...8 точно не фальшивые)
2-е взвеш.: 1, 2 = 9, 10. Фальш. 11 или 12.
3-е взвеш.: 1 = 11 — фальш. 12; или 1><11 — фальш. 11.
Или
2-е взвеш.: 1, 2 >< 9, 10 Фальш. 9 или 10.
3-е взвеш.: 1 = 9 — фальш. 10; или 1><9 — фальш. 9.
Все ясно?
Задача интересная и настолько трудно ее решить, что в готовом решении не так просто разобраться. Браво, igar!
Разберусь, откуда взялось в решении "2.2. Взвешиваем 156 и 278."
Что, только именно эти номера? Нет, ведь номера монетам присвоены безосновательно, случайно. Нужно знать алгоритм формирования 2-х троек для 2-го взвешивания.
Формируем 1-ю тройку.
1. Берем любую монету (ее обозначение) с любой стороны неравенства 1234>5678 (после 1-го взвешивания), в решении igar с левой стороны (цифра 1).
2. Добавляем к ней любые 2 монеты с другой стороны неравенства, в решении 5 и 6. Формируем 2-ю тройку.
3. Берем любую из оставшихся монет с той же стороны, что и в п.1 (с левой, 2, 3, или 4), в решении монета 2.
4. Добавляем к ней оставшиеся 2 монеты с той же стороны, что и в п.2, в решении 7 и 8.
В стороне остались 2 монеты (в решении 3 и 4), среди кот. вполне может оказаться фальшивая в том случае, если 156 = 278. Одна из них — 3 — сравнивается с не фальшивой (выбор из 1, 2, 5, 6, 7, 8). 1 = 3 — фальш. 4; 1>< 3 — фальш. 3.
Для примера можно для 2-го взвеш. сформировать такие тройки: 624 и 513.
Еще один тонкий момент в решении — почему при: "156>278, => Ф среди 178"? Применяем метод исключения. Может ли быть фальшивой монета 2? При первом взвеш. 1234>5678 она находится в тяжелой группе, т. е. если она фальшивая, то она тяжелее остальных. А в неравенстве 156>278 монета 2 оказалась в легкой группе, что противоречит первому взвеш. Если она фальшивая, то она не может при одном взвешивании быть тяжелее остальных, а при другом взвешивании оказаться легче. Следовательно, она не фальшивая. По аналогии можно проследить положение монет 5 и 6, они тоже поменяли знаки неравенства. Не поменяли знак только монеты 1, 7 и 8. Значит, фальшивая монета среди них.
Такое формирование троек дает возможность обойти последний подводный камень — неопределенность знака отличия веса фальшивой монеты (см. решение). Эту проблему невозможно обойти при первом взвешивании тройками.

Мне в 10-м задачу другую задали:Найти максимальное число монет, для которых это возможно.
Что 13 понятно сразу, но как всегда нет оценки. более-менее математически доказал только уже в 11-м. Так почему нельзя для 14-и?

Почему нельзя для 14-и
Вот почему : Разобьем на три четвертки и одну двойку и попробуем решить.
Взвешиваем по 4:
1. Если не равны уже обсуждалось см. выше
2. Если равны: берем 3 из оставшейся четверки и взвешиваем с 3 хорошими, если не равны, то повезло;
иначе: имеем три монеты без признака фальшивости ( легче или тяжелее фальшивая монета ) из которых одним
взвешиванием фальшивку не найти!

А формулировка правильная?
Я думаю что даже имея две монеты(настоящую и фальшивку) и взвесив их мы не определим какая фальшивка так как мы не знаем какая монета тяжелее. Мы лишь будем знать, что одна перевесит другую.

Формулировка чего? Что вы имеете в виду?
Если безотносительно условия задачи, имея только эти 2 монеты, определить фальшивую монету невозможно.Такая ситуация возникает в решении данной задачи, нужно только перефразировать условие: есть 12 монет, известно, что 10 из них (с 1-й по 10-ю) не фальшивые.
Фальшивой может оказаться 11-я или 12-я.
Решение.
Взвешиваем одну из не фальшивых, например, 1-ю, с 11-ой. Если они весят одинаково, то фальшивая 12-я. В противном случае (неравный вес) — 11-я.
Вопросы?

А если знать (допустим что фальшивка тяжелее) то, сначала взвешиваем 3 монеты с одной и 3 с другой стороны, если одна из сторон перевесит, то убираем с каждого края по одной монете и когда останется по одной с каждой стороны то мы определим какая фальшивая. А если после первого взвешивания не одна сторона не перевесит то монеты стоит добавлять.

Решение здесь
Решение задачи на моём блоге
http://mathandprog.blogspot.com/2009/08/12.html

не асилил! слишкам многа букаф!)
надоело читать всякие бредни! 4+4+4! найти фальшивую не прблема одним взвешиванием! далее 2+2 здесь или сразу высянится она или же потом еще разок 1+1!

Можно и 14 монет разрулить
Но извращённым способом. Или имея в запасе ещё одну, точно настоящую монетку...

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

выкладывайте...
допустим образовалось неравенство(ЭБ=Эталон, либо больше, ЭМ=эталон, либо меньше) ЭБ ЭБ ЭБ ЭБ > ЭМ ЭМ ЭМ ЭМ ,
тогда отложенная группа монет (Э Э Э Э) (если б равенство, то в отложенной фальш, берем три от туда приравниваем с эталоном: равенство:отложеная монетка фальш, неравенство: запоминаем знак, сравниваем две любые из этих трех:равенство, отложенная фальш, неравенство: фальш та, которая с запомненым знаком оказалась)
Формируем группы таким образом: откладываем ЭБ ЭБ ЭМ , сравниваем (ЭБ ЭБ ЭМ ЭМ) (Э Э ЭМ Э). 1) равенство: взвешиваем две ЭБ из отложенной, какая больше та и фальш, равены, фальш третья. 2) Больше: взвешиваем две ЭБ из первой группы, какая больше та и фальш, равенство фальш ЭМ из второй группы. 3)Меньше: взвешиваем две ЭМ из первой какая меньше, та и фальш, равенство, фальш ЭМ из второй группы. вроде все, и знаем точно знак фальшивки. По хорошему бы все манетки пронумеровать ЭБ1 ЭБ2... но это не принцепиально

Правильный ответ
делим монеты на две части по 6. находим фальшивую она будет легче. потом еще делим по 3 и снова находим фальшивую сторону она тоже будет легче. в конце берем оставшиеся 3 монеты и взвешиваем только 2, а 1 оставляем с краю, если на весах одна легче, то она и есть фальшивая, на если они равны, то фальшивая лежит с краю не на весах.

Нам неизвестна масса монетки. Ты не можешь с 1ого взвешивания сразу определить какая сторона фальшивая.

а для 46 монет? как доказать, что за 3 взвешивания не возможно? так же по трисекциям?

Если монет N, то число вариантов расположения фальшивой монеты 2N (N, если она легче и еще N, если она тяжелее).
Весы имеют 3 состояния. За n взвешиваний переберем 3^n состояний. Значит в любом случае 3^n>=2N. Если взвешиваний 3, то 3^3=27. Для 13 монет может подойти (2*13=26<27), а больше — нет.

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

Браво, вы решили задачу в семь взвешиваний! ;-)

А разве фальшивая монета не может быть одинакового веса с настоящей?

В условии же сказано:
<< Из 12 монет одна фальшивая. Она имеет массу, отличную от массы настоящих монет (но неизвестно — легче или тяжелее). >>

Если есть глаза — читай сначала условие, там не много, 1,5 строчки.

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

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

При решении этой задачи получается, что, к примеру, за три взвешивания можно определить фальшивку из 13 монеток, за 4 взвешивания — 40, а, скажем, за семь взвешиваний (на идеальных весах): 1093.

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

Ветка 1:

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


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

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


Ветка 2:

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

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

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

Решение проще, чем у igar, и, главное, нагляднее.

Увидел интересное предложение среди комментариев — узнать для какого максимального кол-ва монет можно это сделать, ну тут ход мыслей ясен — 1).мы делим на 3 группы, и взвешивая 2 из них, можем сделать вывод о соотношении всех трех. 2). Сделать это мы можем только 3 раза. 3). В конечном итоге мы должны придти к взвешиванию одиночных монет, таким образом получить максимальное количество монет для которых это возможно , можно 3 раза умножив единицу на 3, то есть 1*3*3*3 = 27 монет. Теперь пойдем обратным путем и убедимся в том что это так — 1). взвешиваем по 9 монет и понимаем в какой из трех групп находится фальшивка, 2). Взвешиваем по 3 монеты и понимаем в какой из трех групп находится фальшивка, 3). взвешиваем по одной монете и понимаем какая монета фальшивая.

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

Общего решения для 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. Она же является и практической границей, как доказывает пример, приведённый мной.

а если в вопрос задачи добавить определить — тяжелее монета или легче?
Решаемо?