Кин-дза-дза!

не кратных даже вот попробуйте определить log3 12.Целое то не получиться и до 3 далеко

это примерно 2.15

Разумеется, надо округлять логарифм в большую сторону.

ну а попробуйте тогда с 27 монетами
log3 27=3

Пришелец Прораб


А ведь ты прав! log3 N взвешиваний потребуется только в самом благоприятном случае, когда фальшивка каждый раз оказывается в отложенной части (в первый раз - в девятке, во второй раз - в тройке, в третий раз - единственная). А в остальных случаях требуется ещё одно взвешивание, т.к. остаются 2 подозрительные.

Таким образом, нам потребуется:

log3 N взвешиваний, с вероятностью 1/3^N
log3 N + 1, во остальных случаях.

В среднем, log3 N + 1-1/3^N
При N -> бесконечности, log3 N +1

Пусть N=12, тогда log3 N + 1-1/3^12 = 3.262

Т.е. мой метод даёт почти всегда решение за три взвешивания и лишь с малой вероятностью могут потребоваться 4.

Тогда нужно применить другой метод.

Кстати, Пришелец Прораб, а вы не рассмотрели случай, когда на чашах весов в первый или второй раз будет равенство. В этом случае ваше решение не проходит:

берётся 6 монет на одну чашу ложатся 3 и на другую три, если какая-нибудь перевешивает
значит та монета которую мы ищем в этой шестерки,иначе в другой.Потом из той 6 где мы выивили монету берется 3 монеты
и берется 3 монеты из той 6 в которой все монеты равны,сравнивается и из этого мы можем сделать два вывода:
1)если опять неравенство на весах то монета в этой 3 или же в другой.
2)мы узнаем точно в какую сторону отличается монета так как эта тройка либо перевесит либо наоборот.Соответсвенно монета либо тяжелее либо легче.
А дальше ваще просто есть 3 монеты и последняя попытка и мы знаем например што монета оказалась тяжелее.Сравниваются две из этой тройки находиться тяжелая либо они равны значит это та монета которую мы не сравнивали.Спасибо за вниманию.

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

Моё решение строится на том, что мы делим N не пополам, а на три части. Третью часть откладываем, а две оставшихся трети раскладываем на разные чаши весов. Если весы не показывают равенство, то количество монет на каждой чаше опять делим на три части. Треть откладываем, треть оставляем, а остальные перекладываем с одной чаши на другую.

Господин ПЖ писал(а):Смотрите, если в первый раз равенство, то мы знаем, что фальшивка в другой шестёрке, но не имеем уже информации, какая тройка из неё тяжелее, а какая легче, на чём строится ваше решение. То же самое, если равенство во втором взвешивании...

Никак нет.Если мы взвешиваем первые две тройки и они получаются равны то значит монета в другой шестерки так?.Из этой шестерки мы выбираем 3 монеты на свой вкус приравниваем и все равно мы может сделать два вывода:
1)если равенство на весах значит монета в оставшейся тройке.
2)мы же знаем что при первом взвешивании монеты равны значит если перевешывают то монета в этой тройке и она тяжелее,потому как остальные все равны значит легче.
Ну дальше из трёх находим одну.
Единственный вариант когда при первом взвешивании равны и при втором равны тогда у нас остается три монеты но мы не знаем легче они или тяжелее .Тогда потребуется четвертое взвешивание.

Тогда потребуется четвертое взвешивание.

Выходит, мы так и не решили исходную задачу...
Надо ведь строго за 3 взвешивания. Ни мой ни твой метод этого не гарантируют.

Давайте последовательно.

Мы делим количество монет на 3 кучки.
Две одинаковые и одну либо больше на одну монету, либо меньше на одну монету, либо такую же.

Взвесив равные кучки мы определяем есть ли монета в отложенной кучке. Если есть (т.е. взвешиваемые кучки равны), то все клевою, а если нет, то сложнее ибо мы не знаем в какой из кучек монета, так как не знаем легче фальшивая монета или тяжелее.
Действительно Log3 получается только, если мы знаем легче или тяжелее фальшивая монета.
В случае равенства кучек можно обойтись еще одним взвешиванием с отложенной кучкой, после которого мы точно знаем в какую сторону отклонение.
А вот в случае 26 монет у нас только 8 эталонных монет - значит при плохом варианте остаются непроверенными 10.
И мы по-прежнему не знаем кто тяжелее.

Насчет задачи с 12 монетками среди которых 1 фальшивая.

На досуге занялся этой задачей, но начал решать ее немного по другому. Сначала я рассмотрел аналогичную задачу для меньшего числа монет. Т.е. найти фальшивую монету не более чем за 3 взвешивания, если количество монет:
3
4
5
...
12

Задачу удалось решить для количества монет 3...10. Для 11 и 12 монет задача уже не решается за 3 взвешивания. Точнее, решается, но только с определенной вероятностью - если "повезет" - с 3, если нет - с 4 взвешиваний.

Для 11 и 12 монет неопределенность слишком высока, чтобы фальшивку можно было гарантированно определить за 3 взвешивания. Правда, строго доказать не берусь. Интуитивно это будет понятно, если вы проделаете ту же работу, что и я - т.е. решите задачи с меньшим числом монет.

Кстати, для случая 10 монет решение будет достаточно интересным.

А я, кажется, вспомнил как решал!

1. Делим 12 монет на 3 части по 4 штуки. Одну часть откладываем, 2 других располагаем на разные чаши весов.

2. Если на весах равенство, переходим к п. 7, иначе отложенную часть считаем эталонной.

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

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

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

6. Если на весах равенство - фальшвая монета - отложенная, если неравенство осталось прежним, то фалишивая монета та, которую мы не трогали на "подозрительной" чаше весов, а если неравенство поменяло знак, то фальшивая монета - та, которую мы переместили.

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

8. Если на весах равенство - фальшивая монета та, что мы отложили. В противном случае мы имеем ситуацию, аналогичную п.5.

Введу обозначения:
0 - монетка, про которую мы не знаем - фальшивая она или настоящая.
+ - настощая монета
@ - фальшивая монета

В начале мы имеем:
0000 0000 000@

1)
Допустим в певром взвешивании мы получили следующий результат:
0000>0000
++++ (четыре оставшиеся монеты - настоящие)

Результат возможен в 2-х случаях:
1. Фальшивая монета тяжелее. Тогда имеем:
000@>0000

2. Фальшивая монета легче. Тогда имеем:
0000>000@

2)
Допустим при втором взвешивании мы пользуемся приемом :
Снимаем с одной чаши весов (которая тяжелее) 1 монету, с другой - 2 монеты, и докладываем туда одну монету из эталонной части. Одну монету тяжелой части обмениваем с одной монетой с лёгкой.

Допустим также, что в результате всех этих перестановок фальшивая монета осталась на весах и неравенство на весах сохранило знак. Итак, что мы получили:

000>00+
+ (снятая с левой чащи монета)
++ (снятые с правой чаши монеты)
+++ (монеты, отложенные с первого раза)

Результат возможен в 2-х случаях:
1. Фальшивая монета тяжелее. Тогда имеем:
00@>00+

2. Фальшивая монета легче. Тогда имеем:
000>0@+

3)
А вот теперь самое веселое.

Как за 1 взвешивание определить, какая из 5 оставшихся монет фальшивая? По-моему, это невозможно.

Рассмотрим 1-й слйчай:

1-е взвешивание:

(ON - монета номер N)

О1О2О3О4 легче О5О6О7О8

2-е:

O1O2O5 легче O3O6O9 (O9 - эталонная, O3 и O5 поменяли местами, O4, O7 и O8 - отложили)

Теперь мы знаем, что фальшивка среди монет O1, O2 и О6

О1 откладываем, О6 перемещаем:

Пусть О2О6 легче О11О12, тогда О2 - фальшивка
Пусть О2О6 тяжелее О11О12, тогда О6 - фальшивка
Пусть О2О6 = О11О12, тогда О1 - фальшивка

Если O1O2O5 тяжелее O3O6O9

То фальшивка среди перемещённых монет O3 и O5 и у нас есть одно взвешивание, чтобы определить какая именно.

Если O1O2O6 = O3O5O9

то фальшивка среди отложенных O4, O7 и O8.

О7 откладываем и сравниваем

О4О8 и О11О12 (мы помним, что О4 с эталоном было легче О7О8)

Далее О4О8 легче/равно/тяжелее О11О12 решается аналогично,

Остаётся 3-й случай О1О2О3О4 = О5О6О7О8

Тогда фальшивка среди О9О10О11О12

И есть 2 взвешивания.

Сравним

О1О9 и О11О12

Если О1О9 = О11О12, то О10 - фальшивка
Если О1О9 легче О11О12, то

сравним О9О11 и О1О2

Если О9О11 легче О1О2, то О9 - фальшивка
Если О9О11 тяжелее О1О2, то О11 - фальшивка
Если О9О11 = О1О2, то О12 - фальшивка

Аналогично поступаем, если О1О9 тяжелее О11О12

Все, разобрался.

В общем, путем переброса монет можно уменьшить неопределенность. Я сам пользовался этим приемом для 10 монет. А вот использовать это прием дважды для 12 - не догадался.

Виктор, молодец.

А вот несложная задачка о переливании пустого в порожнее.

Имеется 9-литровое ведро и 5-литровая канистра. Надо только с их помощью точно отмерить 3 литра.

Господин ПЖ
Налить в ведро 9 л. и из него вылить 5 л. в канистру. В ведре останется 4 л.
Опорожнить канистру (0 л.) и вылить в нее из ведра оставшиеся 4 л.
Потом опять налить в ведро 9 л. и из него долить в канистру 1 л.
(ээээ... в ведре-8, в канистре-5.)
Освободить канистру. Из ведра залить ее полностью. 8-5=3 л. останется в ведре. Вот.