Форум умных людей

Есть 59049 монет (3¹⁰). Среди монет имеется одна фальшивая. Известно, что фальшивая монета немного тяжелее настоящей. Сколько нужно минимум взвешиваний на чашечных весах без гирь, чтобы определить фальшивую монету, если известно, что во время одного из взвешиваний весы могут показать неверный результат?

за 20 взвешиваний справлюсь :)

Многовато будет.

то есть, я хотел сказать, за 21   :-[

Это верхняя оценка. :)

как ты недооцениваешь верхнюю оценку :)

верхняя оценка - это 3*59049*59048/2  :)

Ну за 11 точно нельзя - это понятно.
Но 21 взвешивание - это слишком просто. Можно уменьшить число взвешиваний, гораздо уменьшить.

17 получается

Уже хорошо.
Но можно еще меньше.

чепырнацать!

а как можно доказать, что за 11 нельзя?

Одного взвешивания недостаточно для определения ошибочного взвешивания:
3¹<10+1
:)
Теоритически можно и за 13.
3³>10+3

Необходимо 11+k взвешиваний, где k - порядковый номер взвешивания, на котором произошла ошибка - в случае если ошибка будет. И 20 взвешиваний, если ее не будет.
Решение: Естественно, что для обычного определения тяжелой монеты надо 10 взвешиваний. Так как одно взвешивание может быть неправильным, нам надо каждый раз взвешивать по 2 раза до тех пор, пока второе, контрольное взвешивание однажды не разойдется с первым. Тогда нам надо будет произвести еще одно взвешивание, чтобы узнать истину. И далее, мы можем смело взвешивать по одному разу, т.к. лимит на неправильные показания закончился. В итоге, нам надо: 2*(k-1) взвешиваний - до ошибочного результата на k-ом шаге, +3 взвешивания на k-м шаге, +(10-k) взвешиваний после того как весы ошиблись, и мы провели три измерения. 2*(k-1)+3+(10-k)=k+11.
Если же ни на одном шаге взвешивание не разойдется с контрольным, то нам надо будет всего: 2*10 = 20 взвешиваний.

Уже выяснили что можно и за 14 уложиться.
Но можно и за 13. :read:

Расскажи, как точно уложиться за 13 измерений. Пожалуйста, поподробнее.

Очень интересное кино. Я задал задачку и меня просят дать ответ, когда не прошло и дня с первого поста. Есть же еще желающие.

ладно, подождем=)

ай!  моё решение про 14 оказалось неверным
илья простак, верит на слово :)

а, дошло...
и правда, совсем несложно

Илья, можно для прояснения условия задачи спросить, за сколько взвешиваний можно определить одну фальшивую монету из двух при твоем условии? это многое объяснит (для меня в частности) :tormoz:
варианты ответов:
1) за 1 взвешивание
2) за 2 взвешивания
3) за 3 взвешивания
4) за 4 взвешивания
5) невозможно определить
6) Смит, ты  :tormoz:
7) Ваш вариант

Так легко же.

на ответ 6) намекаете?  :muscles:

Нет, просто не хочу подсказывать.

так вот если ваш ответ 2), то мой ответ 13..
а вот если нет, то - нет. и тогда хотелось бы посмотреть, хотя бы, на 14, в Вашем исполнении, или  CD_Eater, например.. :bravo:

В моем исполнении?

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

Сначала интересно посмотреть на 13 взвешиваний, когда определяем 1 из двух. :)

ну, тогда чисто гипотетически...

1) 19683т>19683л=19683л
         /
2) 6561  >  6561л = 6561л
  19683л | 19683л
        /
3) 2187 >  2187=2187
    6561л |  6561л
  19683л | 19683л
        /
4) 6561  |  6561
  19683  | 19683 - меняем местами против 3). если все = то гуд. а если нет, то ..
а, вот, "то" зависит от ответа на мой вопрос в постах выше  :tianchik:

Решение есть - в троичной системе исчисления.
Могу дать не подробное решение для 13 монет:
Показать скрытый текст
Есть более подробный разбор этого решения.

Илья, спасибо за пояснение, обязательно завтра попробую осилить, вообще, троичная система счисления - это первое, что приходит в голову, когда пытаешься решить данную задачу,  однако она (троичная система) хороша в применении, если, к примеру, я задумал одну цифру из предложенного Вами числа, а Вы пытаетесь её угадать, с учетом того, что я могу отвечать только да и нет, и при этом могу один раз соврать.
но, согласитесь, это разные вещи в сравнении с взвешиванием..
зы: в любом случае - спасибо за представленное решение и пояснения :peace:

Если не осилите, то выложу и подробное. Вроде все кто хотел уже отметились.

не думаю, точнее просто вообще никто не представил своего решения или, хотя бы, видения ситуации..
я показал, примерно, как можно действовать, но нужно понимать, что 3) ответ на мой вопрос дает абсолютно иные решения, нежели ответ 2), и еще повторюсь, что есть разница между "вопрос-ответ" и "взвешивание": в первом случае можно представить число 59049 в троичной системе счисления и задавать вопросы по каждой цифре в числе, а во втором случае, понятно, все совсем по-другому :roll:

Илья, я пересмотрел свое решение, начало которого я дал, и у меня даже 13 не получается, только 14 в худшем варианте.. завтра подумаю еще, но пока что я ближе к 15 нежели к 13.. :roll:

какая коварная задачка
моё второе решение, когда я подумал, что 13 получить легко, оказалось неправильным

я думал, что после 10 взвешиваний (по правилу 10-мерного трёхслойного кубика рубика), дающих координату главного подозреваемого, достаточно проделать аналогичные 3 взвешивания для оставшихся 21 подозреваемых, т.к. 21 <= 27
но я не учёл, что ошибка может случиться как раз во время последних 3 взвешиваний

получается. что размещать эти 21 в кубе 3*3*3 надо хитро - главного подозреваемого в ячейку (0,0,0), а ячейки с двумя нулями в координатах заполнить монетами, которые гарантированно не фальшивые по результатам первых 10 взвешиваний.

я вчера предложил вариант решения, но небыло времени пояснить.
имеется ввиду, что если, к примеру, весы показывают 9683т>19683л=19683л при первом взвешивании, то, вполне возможно, что на самом деле правильно 1<2>3. и так в кажом взвешивании.
тогда при взвешиваниях 3^8, 3^5, 3^3, 3^1 мы делаем контрольные взвешивания (КВ) таким образом, что взвешиваем только "балласт".
при этом, если весы сохраняют свое положение, то все было правильно, и на КВ мы тратим 1 дополнительный ход. если во время КВ весы меняют положение, значит либо ошибка была допущена выше, либо это сейчас и есть ошибка, тогда для определения понадобится 3 взвешивания.
например:       
1) 19683a>19683b=19683c - весы показывают, на самом деле 19683a<19683b>19683c
         /
2) 6561a  >  6561a = 6561a - весы показывают, на самом деле  6561a  =  6561a = 6561a
  19683b > 19683c - мы добавили "балласт" из первого взвешивания, он то и дает знак >
       
3) 2187a >  2187a=2187a - пок. весы, на самом деле 2187a =  2187a=2187a
    6561a = 6561a
  19683b > 19683c
       
4) 6561a  =  6561a
  19683c  < 19683b - взвешиваем "балласт" без 2187 и меняем местами 19683c  < 19683b против 3). если весы равны, то взвешивание 3) было правильным и мы продолжаем взвешивания, но если весы меняют положение, то делаем (КВ) - 5)
5) повторяем взвешивание 4 (КВ) и если весы остались в положении как при 4) взвешивании, значит ошибка была в самом начале в 19683 и теперь мы знаем правильную 19683 из трех и следующие 9 ходов - это от 3^9 до 1.

а чтобы получить за 13 ходов - прийдется определить за 2 взвешивания на обычных (не Y образных) чашечных весах 1 фальшивую монету из 9, либо пересмотреть точки КВ  ???

Оцениваю число взвешиваний 3^К монет в К + [log₃K] + 1

buka, можете конкретно написать алгоритм для 59049 монет? ну или хотя бы просто скажите - сколько взвешиваний по-вашему понадобится для 59049 монет?

По приведенной Букой оценке видно, что он уложится  за 13 взвешиваний с хвостиком. :)

так хочется видеть..   :think:
зы: особенно - хвостик :laugh:

Более подробное решение:
Показать скрытый текст

Илья, я не понимаю, к сожалению, то, о чем там написано.  :tormoz: можно на пальцах для меня?  :-[
я могу помочь, написать, например:
₃10 = 59049
₃9 =   19683
₃8 =     6561
₃7 =     2187
₃6 =       729
₃5 =       243
₃4 =         81
₃3 =         27
₃2 =           9
₃1 =           3
₃0 =           1

Для начала надо занумировать монеты:
1 -0
2 -2
3-10
4-11
....
59049 - 10000000000
Разряд считается справа налево.

проще объяснить про кубик рубика

Это который 10-мерный трехслойный? :roll:

спасибо, это понятно  :peace:
а дальше (как взвешивать)? ???

Первое взвешивание, к=1.
На одну чашу весов кладем монеты у которых в первом разряде 0, на вторую у которых 1, а у которых в 1-ом разряде 2 лежат в стороне.

ну, начать надо с трёхмерного, а потом произнести волшебную фразу "пусть размерность куба равна N"  :)

ок. кстати, сколько каких? если знаете - напишите, плз, если нет - я посчитаю..

и вообще, задача какая-то не жизненная
её придумал крохобор
у него 50тыщ+ монет, а его беспокоит одна фальшивая :)

Смит, Вы удивитесь, но 19683 у которых 0, 19683 у которых 1 и 19683 у которых 2. :o
А Вы знаете кто ее придумал? :)

вообще, в троичной системе 0=0, 1=1, 2=2, а 3=10. впрочем, с распределением по первому разряду - согласен, 1:1:1 = 19683=19683=19683 :peace:
поехали дальше  :good:

не знаю

но почему бы не переформулировать её для 9 монет и 4 взвешиваний?  так будет интереснее

А я знаю. :)


Так бы было слишком просто. :)

Вы можете привести решение поставленной задачи с минимальным количеством взвешиваний? :-\

почему было бы просто?
разве есть более простое решение для 9 монет?

а ещё у крохобора, которого ты знаешь :) , афигенные весы - на них можно положить по 20 кг на чашу и уловить разницу в доли грамма.  современные широкораспространённые цифровые весы такого не умеют.


уже привёл, где-то там выше.  вместо нумерации монет числами из троичной системы я разложил монетки по одной в каждую ячейку кубика

прелестно, и каков результат? ???
зы: ну, или "хвостик"? :D

и, кстати, каков алгоритм? :help:

результат - 13
сначала заполняем монетами 10-мерный кубик, потом 3-мерный

в таком случае, у меня результат проще и короче: взвешиваем все монеты используя  синусоидальную трапецию (или призму) и - раз! определяем фальшивую (1 взвешивание) :peace:

зы: есть возражения? :D

конечно!

ps а это как ? :haha:

не, а тут я первый.. а это
- как? :o

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

интересно, ту акулу ты довёл до бешенства своими просьбами разъяснить очевидное?  :)

Смит, а сколько ячеек в кубике 3*3*3?

требует. если не можете представить алгоритм - честно признайтесь :tianchik:

Илья, в постановке вашей задачи не предусмотрено предоставление алгоритма. однако, полагаю, вполне уместно представить его - всего-то 13 строк, для понимания тех, кто  :tormoz:

зы: если не трудно, конечно ???

для всех: пока не будет конкретного алгоритма - ЗАДАЧА НЕ РЕШЕНА!

зы: закидоны, типа, "там всё понятно" - не принимаются, более того, рассматриваются, как НЕПОНИМАНИЕ и НЕЗНАНИЕ алгоритма решения.

зы: зы: ото таке... :peace:

Покажем алгоритм на 27 монетах
1-1
2-2
3-10
4-11
5-12
6-20
7-21
8-22
9-100
10-101
11-102
12-110
13-111
14-112
15-120
16-121
17-122
18-200
19-201
20-202
21-210
22-211
23-212
24-220
25-221
26-222
27-1000
Первое взвешивание:
1 4 7 10 13 16 19 22 25 --- 3 6 9 12 15 18 21 24 27
Если равновесие, то откладываем 1 3 и взвешиваем
2 5 8 -- 11 14 17, если равновесие, то откладываем 2 и 11
взвешиваем
20--23, если равновесие, то откладываем 20 и 23, главный кандидат 26.
Итого имеем: 26 главный кандидат и 1,3,2,11, 20, 23-потенциальные кандидаты, всего 7 монет
Взвешиваем  1 3 --2 11, если перевесила 1 3, то значит ошибка точно уже была и фальшивка в 1 3 или 26, определяем за 1 взвешивание стандартным способом
если же равновесие, то фальшивка в 26 20 23 и ошибки еще не было, взвешиваем 20 и 23, если равновесие, то фальшивка 26, если нет равновесия, то сравниваем 26 с той монетой, которая перевесила.

Илюха, объясни мне, зачем кодировать 27 монет? к чему, к примеру, 27=1010? ну ладно - такова метода. ок.

ок, начало понятно
а это не понятно: где в первом взвешивании 2 5 8 -- 11 14 17? или откуда ты взял эти цифры? почему именно их?
вообще, сколько взвешиваний получилось в твоем примере? я насчитал минимум 5. минимум. а если это не 27 монет, а - все 59049? извини, я не вижу 13  ???

Есть пару вопросов.
1. Что считать одиночной ошибкой взвешивания?
Если А1 > Б1, а весы при взвешивании А1,А2...Ак -- Б1,Б2...Бк показали "<" - это одиночная ошибка или двойная?
2. При равновесии процесс откладывания понятен. А вот что откладывать, если в первом взвешивании неравенство? Или я неправильно понял слово "окладываем"?
Второе взвешивание мы как производим: убираем по одной монете (1 и 3) и добавляем 6 новых (по 3 на каждую чашку, т.е. у нас по 11 монет на каждой чашке?).

Чтобы раскладывать по принципу разряда 0 - налево, 1-направо, 2- в стороне, я же уже писал об этом. Закодировал верно, распределил может не совсем, я не особо смотрел на это, но принцип такой, к-ое взвешивание смотрим к-тый разряд, то есть основных взвешиваний к=1,2,3 - что стандартно для 27 монет, остальные взвешиваня нужны, чтоб определить фальшивку. Я хотел показать общий принцип.
6 - три основных и три дополнительных
10 основных + три дополнительных

Бука, допустим у нас две монеты 1 и 2.
Первое взвешивание: 1--2, 1 перевесила
Второе взвешивание: 1--2, 2 перевесила
Третье взвешивание: 1--2, 1 перевесила, так вот 1- фальшивка, второе взешивание было ошибочным.
Если неравенство, то откладываем монету из кучки которая легче и из кучки, которая в стороне.

Илья, это твоя задача, вероятно я чего-то не понимаю, я склонен скорее соскочить с базара, чем в очередной раз писАть, что я не понимаю решения для 13 монет, и обострять ситуацию.
пойми правильно: то, что я показал в качестве своего варианта, могло быть иначе, например, вместо КВ на 4) взвешивании можно было сделать его на 3). тогда у меня получилось бы 12 взвешиваний на круг. но тогда был бы и справедлив вопрос: а если в начале все ок? а вот тогда 12 не получается у меня ???

Я не заметил обострения. :)
Для того мы и здесь, чтобы искать и давать ответы.
Ок, начнем с малого:
с решения в три монеты: одна фальшивка и одно ошибочное взвешивание на весах.. :)
Поехали, тут можно не кодировать:
1--2, равновесие, главый кандидат 3, 1 и 2 потенциальные претенденты,
1--2, равновесие, значит 3 - точна искомая фальшивка.
Если в первом взвешивании не было равновесия, тогда главный претендент та монета, которая перевесила, например 1, а 2 и 3 - потенциальные.
Взвешиваем 1 и 3, если равновесие, то взвешиваем опять 1 и 3, перевесила 1-ца - она фальшивка и второе взвешивание было ошибочным. Ели перевесила 3-ка, то взвешиваем 3 и 2, если перевесила 3-ка. то она и фальшивка, первое взвешивание было ошибочным. Вот так. С этим понятно?
Ай, вот здесь не точно, потому что весы по условию должны один раз ошибиться, поэтому они не могут в самом начале показать один и тот же результат, значит допустим второе взвешивание 1-- 2, 2 перевесила, сравниваем 2---3, если2 перевесила, то она и фальшивка, равновесие быть не может, значит первое взвешивание - была ошибка.

да. Илья, спасибо, здесь понятно. я так же рассуждал, и если идти снизу то получается, а если идти от 19683, то у меня - нет  ???
зы: отложим до завтра? :peace: :wall: :zzz:

Смит, вот здесь у меня не точно.
Потому что весы по условию должны один раз ошибиться, поэтому они не могут в самом начале показать один и тот же результат, значит допустим второе взвешивание 1-- 2, 2 перевесила, сравниваем 2---3, если2 перевесила, то она и фальшивка, равновесие быть не может, значит первое взвешивание - была ошибка.
Можно и так: третье взвешивание опять 1--2, если равновесие, то фальшивка 3, если опять перевесила 2, как во втором взвешивании, то фальшивка 2.

мне кажется, нам с вами даже ненужно объяснять расположение весов. понятно, что если после КВ весы не изменились, то взвешивание было верное. если изменились, то имела место ошибка и определить ее (при правильном подходе) - вопрос 3-х взвешиваний (а с учетом уже произведенного - 2) :peace:

Да, пожалуй. Поздно уже. :zzz:
Да и форум что-то тормозит. :wall:

Илья, здесь всё верно :good:

С самым трудным разобрались. :laugh:

с этим моментом давно разобрались, я писАл об этом же здесь http://nazva.net/forum/index.php/topic,3696.msg73365.html#msg73365 , ты просто это понимал, а сейчас мы просто устаканили свое понимание друг друга :beer:
а вот дальше как раз и начинается самое интересное :)

Илья, тут я совсем не понял: к примеру, если в первом взвешивании равенство было ложно, и, например, фальшивка - монета №13, то как ты ее определяешь исходя из предложенного тобою алгоритма?  ???

Тут у меня не совсем верно, как я уже и говорил выше. Глючный алгоритм или я пока не совсем догнал до ответа, который я сам дал.  :)Сейчас занет немного, попозже разберусь.

расскажи ему про 9 монет и 4 взвешивания
решение то же самое, только всё наглядно, меньше возни с нумерацией и нет 10-мерных кубов

если вам интересно обсуждение на принципах взаимоуважения и конструктивного диалога -  присоединйтесь.. :peace:

А задачка-то интересная вышла. У меня кстати есть еще бонусная задача на эту же тематику, про два ошибочных взвешивания, правда там монет поменьше. :)
Но не будем торопить события, сначала надо с данной разобраться. :read:

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

извини. я, вероятно, погорячился  >:(
зы: буду искренне рад, если вы приймете участие в обсуждении данной темы. искренне!  :peace:

кстати, я действительно не врубаюсь к чему тут вариант из 9 за 4? такое впечателение, что имело место обширное обсуждение данной задачи, которое я проспал... объясните, плз!? :roll:

Смит, я попытаюсь объяснить так, чтобы решение не вызывало бы недоумения и не выглядело бы как фокус-покус. Но надо набраться терпения и дочитать всё :)
1. Рассмотрим традиционный подход, т.е. без допущения возможной ошибки весов.
Такой подход базируется на дереве решений, причём решение на следующее взвешивание (измерение) принимается по результату предыдущего.
Напр. раскладываем на 3 кучки, 2 взвешиваем -> по рез-ту выбираем кучку, содержащую кандидата и проделываем с ней аналогичное.
Каждое взвешивание уменьшает число кандидатов в 3 раза. Здесь всё ясно.   
2. Данный подход ясен и прозрачен, но, увы, не подходит для нашего случая.
Почему?
Показать скрытый текст
Показать скрытый текст
Показать скрытый текст
Показать скрытый текст
Показать скрытый текст

Если всё, что описано в предыдущем моём постинге понятно, предлагаю более усложнённую задачу.
Допустим, наши весы могут ошибаться не чаще одного раза за К взвешиваний, а у нас число монет М > 3^К. Какова будет наша стратегия?

А где реакция, вопросы и пр.?

Вы точно человек ? :peace: :D

Все ясно. Формула последняя не совсем понятна, а так вроде все доступно.

Мне надо было выразить целую часть числа в сторону увеличения, т.е.
для 3.1 -> 4, для 12.9 = 13, но для 13 - тоже 13.
Если [Х] - целая часть числа, а {Х} - дробная часть, то
[Х+1] - [1-{Х}] - это то, что  нужно.

Это обозначается так:  ]X[

buka, спасибо за подробное и обстоятельное объяснение, к сожалению только сейчас выдалось свободное время, чтобы с ним ознакомиться.
если я правильно Вас понял, то для 27 монет раскладываем так, как показано ниже (кодировка - предложенная Ильей http://nazva.net/forum/index.php/topic,3696.msg73506.html#msg73506):

(1) 1   3    2  2) 2  11  20  3) 11  14  17
      4   6    5      5  14  23      10  13  16
      7   9    8      8  17  26      12  15  18
   10  12   11     1  10  19          2   5   8
   13  15   14     4  13  22          1   4   7
   16  18   17     7  16  25          3   6   9
   19  21   20     3  12  21      20  23  26
   22  24   23     6  15  24      19  22  25
   25  27   26     9  18  27      21  24  27
   -------------     ------------     --------------
   0 = 1  |  2     0 < 1  | 2        0 <  1 | 2

до этого момента всё понятно: 14 - Основной Кандидат (ОК), и если бы весы показывали точно, то это и была бы фальшивая монета;
а далее мне не совсем понятно :tormoz: следующее:
1)какие монеты являются Потенциальными Кандидатами (ПК) (для представленного выше случая 3^3)?
2)как определить за 3(2) взвешивания 1 из 6 ПК (для данного случая 3^3)?
3)как учитываются монеты 11 и 17, котрые для случая ошибки при взвешивании (3) также становятся ОК (или они входят в группу ПК?)?
4)как определить за 3(2) взвешивания 1 из 20 ПК (для случая 3^10)??
спасибо за внимание и терпение :)

зы: кстати, может быть кто-то еще понимает и захочет объяснить? буду признателен :peace:

В примере, на который Вы ссылаетесь допущена ошибка в кодировке
12-110 верно
13-121 нет, должно быть 111
14-122 нет, должно быть 112
и т.д. с этого момента.
Поэтому всё "поплыло" и на том примере я, вместо того, чтобы объяснить, могу Вас только запутать.
Поэтому я предлагаю следующее:
1. Пронумеруйте 27 монет, начиная с 0, а не 1. Это важно, иначе  придётся пересчитывать. Кроме того, в данном случае 27-я монета будет иметь номер 26, что соответствует 222 в троичной системе, а номер 27 уже будет 4-х разрядным - 1000.
2. Переведите эти номера в троичную систему. Каждый номер будет 3-х разрядным:
0: 000, 1:001, 2:002, 3: 010, ..., 9: 100, 10:101,..., 17:122, 18:200, 19:201,...,25:221, 26:222.
3.1 В первом взвешивании на левую чашку кладём 9 монет с 1-ей в старшем разряде, т.е. от 100 до 122 (с номера 9 по номер 17), на правую чашку - с 2-й в старшем разряде, т.е. с 200 по 222 (номера 18 - 26), монеты 0-8 (с 000 по 022) в стороне.
3.2 Во втором взвешиваии на левую чашку будем класть монеты с 1-ей во втором разряде: 010,011,012,110,111,112,210,211,222, т.е. 3,4,5,12,13,14,21,22,23;
на правую - 2-ой во втором разряде: 020,021,022,120,121,122,220,221,222, т.е: 6,7,8,15,16,17,24,25,26 и в стороне остальные: 000,001,002, 100,101,102, 200,201,202, т.е. 0,1,2,, 9,10,11, 18,19,20.
3.3. В третьем взвешивании: левая - 1-ца в младшем разряде, правая - 2-ка в младшем разряде и остальные - в стороне.
4. Запишем рез-ты взвешивания. Поясню, как их кодировать.
4.1 Мы ищем фальшивую, которая ТЯЖЕЛЕЕ, поэтому рез-ты мы будем записывать так:
1 - перевесила левая, 2 - перевесила правая, 0 - равновесие.
Если бы мы искали фальшивку которая ЛЕГЧЕ, мы бы кодировали так:
1 - левая легче, 2 - правая легче, 0 - равновесие.
Хочу подчеркнуть, что в принципе кодировка решающего значения не имеет, но выбрав другую кодировку, нам прошлось бы пересчитывать и мы бы запутались.
Поэтому для НАС кодировка ПОКА важна.
----------------------------------------------
Сообщите мне рез-ты взвешиваний и я Вам объясню, как мы выбираем монеты для дополнительных взвешиваний.

Да, ошибка. Спасибо, Бука.
Исправил.

Это просто описка имхо. 3-чная система вообще неприятна - нечeтное основание.

(1)
100  200    000    или  9     18      0
101  201    001          10     19      1
102  202    002          11     20      2
110  210    010          12     21      3
111  211    011          13     22      4
112  212    012          14     23      5
120  220    020          15     24      6
121  221    021          16     15      7
122  222    022          17     26      8

(2)
010   020  000  или      3    6    1
011   021  001              4    7    2
012   022  002              5    8    3
110   120  100            12  15    9
111   121  101            13  16  10
112   122  102            14  17  11
210   220  200            21  24  18
211   221  201            22  25  19
212   222  202            23  26  20

пока набирал - понял, что че-то теперь вы напутали с кодировкой или с переводом в 3-ю систему..

Не понял, в чём проблема?
Что Вас смущает?

(1)
100  200    000    или  9     18      0
101  201    001          10     19      1
102  202    002          11     20      2
110  210    010          12     21      3
111  211    011          13     22      4
112  212    012          14     23      5
120  220    020          15     24      6
121  221    021          16     25      7
122  222    022          17     26      8

(2)
010   020  000  или      3    6    0 - здесь так (жирный шрифт)
011   021  001              4    7    1
012   022  002              5    8    2
110   120  100            12  15    9
111   121  101            13  16  10
112   122  102            14  17  11
210   220  200            21  24  18
211   221  201            22  25  19
212   222  202            23  26  20

ок. что дальше?

А третье взвешивание?
И результаты взвешиваний.
То, что Вы выделили жирным меня абсолютно не смущает.
Поймите, Смит, мы должны как-то засинхронизоваться, чтобы я почувствовал, ЧТО Вас смущает. Не стесняйтесь не только указывать, что, но и говорить почему смущает.

ну просто у вас была описка. я исправил с 123 на 012. сейчас привожу третье взвешивание, а затем вы предложете кодировку весов во всех взвешиваниях.

Понял, спасибо. Здесь все мелочи важны. Сейчас исправлю.
А Вы пока скажите мне результат 3-х взвешиваний.

(1)
100  200    000    или  9     18      0
101  201    001          10     19      1
102  202    002          11     20      2
110  210    010          12     21      3
111  211    011          13     22      4
112  212    012          14     23      5
120  220    020          15     24      6
121  221    021          16     25      7
122  222    022          17     26      8

(2)
010   020  000  или      3    6    0 - здесь так (жирный шрифт)
011   021  001              4    7    1
012   022  002              5    8    2
110   120  100            12  15    9
111   121  101            13  16  10
112   122  102            14  17  11
210   220  200            21  24  18
211   221  201            22  25  19
212   222  202            23  26  20

(3)
001   002           000 - в сторне          1    2       0
011   012           010                           4    5       3
021   022           020                           7    8       6
101   102           100                          10  11      9
111   112           110                          13  14     12
121   122           120                          16  17     15
201   202           200                          19  20     18
211   212           210                          22  23     21
221   222           220                          25  26     24

Прекрасно. И какие результаты взвешиваний?

пусть рез-ты будут:
1) 0
2) 2
3) 2

я так понял, что ОК- 022? а ПК? вобщем, пока мои вопросы те же что и на прошлой странице, только применительно к данной кодировке.

То есть на 1-м взвешивании равенство, на 2-м и третьем перевесила правая чаша.
Итого мы имеем число 022 что даёт нам основного кандидата - 022 или номер 20.
Теперь выберем потенциальных кандидатов.
Для этого выпишем все трёхразрядные числа, отличающиеся от 022 ТОЛЬКО во одном разряде. Таковых будет 6:
122 и 222 отличаются в старшем разряде
012 и 002 отличаются во втором (среднем разряде)
020 и 021 отличаются в младшем разряде.
Можно убедиться, что остальные числа будут отличаться БОЛЬШЕ, чем в одном разряде.
А одиночная ошибка предполагает, что если она случилась, то лишь ОДИН раз.
-------------------------------
Итак у нас 7 монет: 022 (основной) и 6 потенциальных: 122,222,012,002,020,021.
Теперь эти номера уже не играют роли. При одиночной ошибке в дополнительных взвешиваниях мы будем придерживаться традиционной стратегии.
Поэтому забудем на время о СМЫСЛЕ номеров и будем их использовать только для идентификации.
1. Отложим нашего основного кандидата (022) и будем работать с 6-ю монетами - ПK.
2. 6 монет - это плохой случай и 2-мя взвешиваниями нам в худшем случае не обойтись.
Если положить по 3 монеты на каждую чашку, то в случае неравенства нам надо будет выбрать одну монету из 4-х (3 из плохой чашки + основной кандидат 022) и на это уйдёт 2 взвешивания.
3. Если положить по 2 монеты и 2 оставить в стороне, то в худшем случае тоже потребуется 3 взвешивания и я это сейчас покажу.
Положим 2 монеты на левую чашку, 2 - на правую и 2 оставим в стороне.
Какие номера на левую, какие - на правую и какие отложим - здесь не суть важно.
Допустим, 122 и 222 - на левую, а 020 и 021 - на правую (002 и 012 - в стороне).
Если неравенство - это хороший случай. У нас 2 "плохие" монеты + основной кандидат 022 и одним взвешиванием мы всё находим - ведь на этом последнем взвешивании ошибки уже быть не может: она УЖЕ произошла либо на предыдущем, либо в первом пакете взвешиваний (на одном из трёх первых взвешиваниях)
4. Если же у нас равенство, остаются 2 монеты, которые в стороне (002 и 012) и ещё наш кандидат.
Если на втором взвешивании (002 и 012) - равенство, - всё ОК, наш основной кандидат - и есть фальшивка и это окончательный рез-т.
Но если произошло неравенство, нам требуется ещё одно взвешивание и НИКУДА не деться.
Нам придётся взвесить нашего основного кандидата с этим "плохим" из предыдущего взвешивания.
Кому-то может показаться, что если вместо взвешивания 002 и 012 лучше взвесить нашего основного кандидата 022 с одним из этих товарищей, то это - шило на мыло.
В случае равенства нам потребуется всё равно ещё одно взвешивание:
нашего 022 с оставшимся вторым.
Итак, для 27 монет требуется 6 (ШЕСТЬ!) взвешиваний и НИКУДА от этого не деться, как в случае 3^10 монет, где нам удалось сэкономить на одном взвешивании.
Вопросы? Не стесняйтесь спрашивать.

почему 21 не является ОК?

точнее так: 022 = 8 (а не 20). а если вы имеете ввиду 022 и 020, тогда и 021

Во-первых, я опять ошибся - 022 это номер 8 а не номер 20.
Во-вторых - 21 это имеется ввиду 021 или 21₁₀ = 220₃ (т.е. 2*9 + 1*3 )?

бука с ошибкой понятно, вопрос о 21 (имелось ввиду 021) пока снял.

buka, почему? ведь если так, то вы предполагаете, что взвешивание, например 022 = 002 - могло быть фальшивкой?!

и последнее, что касается 3^10.
помнится, для этого случая вы назвали 1 ОК и 20 ПК (или 10 пар). я не предлагаю рисовать для всех 13 взвешиваний картинку, только, если можно, расписать последние 3 во второй сессии (после определения 1 основного и 20 потенциальных кандидатов)

Вот мы получили это равенство. Вы можете сказать - кто фальшивка?
Если мы ошиблись раньше - то фальшивка не наш ОК, а тот, кто остался.
Если мы ошиблись сейчас, то фальшивка - наш ОК...

да, во втором взвешивании первой сессии, монеты 002 и 012 были равны, и если ошибка там, то равенство ОК и и одной из них ничего не даст, прийдется взвешивать ОК с другим

Хорошо.
У нас есть ОК и 20 ПК.
Откладываем ОК в сторону.
--------------------------------------
1. Разбиваем ПК на 3 кучки - две по 8 и одну - 4. 1-е взв.: 8 - 8.
1.2 Если равенство: 2-взв: из 3-ей кучки - 2-2 (в стороне - пусто, если не считать ОК)
1.3 Если опять равенство - случай неинтересный. Фальшивка - наш ОК.
1.4 Если неравенство: у нас ещё одно взвешивание и мы ТВЁРДО знаем, что больше ошибок взвешивания не будет.
У нас 3 монеты - 2 из "плохой" кучки и наш ОК.
За одно взвешивание определяется фальшивая. И этот рез-т уже ОКОНЧАТЕЛЬНЫЙ.
В этом последнем взвешивании неважно какие 2 из 3-х мы будем взвешивать.
2. Если неравенство в 1 взвешивании (8-8): у нас "плохая" кучка из 8 ПК и наш ОК.
Итого - 9 монет, ошибок больше не будет -> достаточно ещё 2-х традиционных взвешиваний: разбиваем по 3, получаем "плохую" кучку из 3 и в последнем взвешивании определяем фальшивку окончательно.

buka, я, к сожаленю, вынужден откланяться на сегодня, завтра обязательно осмыслю всё еще раз, и обязательно отпишусь.
да, и спасибо вам огромное за обстоятельное разъяснние, сам бы я вероятно это все не осилил