59049 монет

[buka]

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

[buka]

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

Если мы вынуждены допускать что весы могут один раз ошибиться, мы вынуждены принимать решение по результату нескольких независимых измерений, а не одного, - чтобы мы могли судить по кандидату ТОЛЬКО по результату такого ПАКЕТА взвешиваний, будучи уверенным что сама последовательность взвешиваний в таком пакете НЕ ЗАВИСИТ от результатов самих одиночных взвешиваний. Именно такой подход даёт НЕЗАВИСИМОСТЬ одного взвешивания от другого. Иначе ошибка весов при предыдущем взвешивание ломала бы все рез-ты последующих.
Если с этим моментом понятно, пойдём дальше.

Показать скрытый текст

3. Вернёмся опять к "безошибочным" весам и обратим внимание на следующий момент.
Когда мы разделили монеты на 3 кучки и по результату одного взвешивания получили кучку в которой должна быть фальшивая монета, чтобы проделать с этой кучкой то же самое, то есть разделить эту кучку на 3 части и положить 2 из них на весы, НИЧТО нам не мешает дополнить две эти кучки любым (но равным, естественно) кол-вом монет из отвергнутых в предыдущем взвешивании куч - это не повлияет на результат!!!
Это - основной момент подхода. На этом базируется вся идея.
Если мы, например, ЗАРАНЕЕ разделим все монеты на 3 кучи и напишем на каждой монете первой кучи "Левая", второй - "Правая", а 3-й - "Резерв", затем разделим каждую кучку на 3 и допишем на каждой монете под первым словом "Левая", "Правая" или "Резерв"  и так далее, то каждая монета в конце концов приобретёт К слов, в которых будут чередоваться эти слова. 
Что это нам даёт?

Показать скрытый текст

4. Первым взвешиванием мы взвешиваем, как и планировали, кучи, в которых самые верхние слова - "Левая" и "Правая" - левые на левую чашку, правые - на правую.
Теперь, допустим, перевесила бы правая чашка. Что бы мы сделали при традиционном подходе? разделили бы её на 3 части и продолжили. Правильно?
Но ничто нам не мешает дополнить наши маленькие кучки ещё двумя кучками из отвергнутых куч? Ничего, верно?
А если бы было бы равновесие при первом взвешивании?
Мы бы выбрали 3-ю кучку, разделили бы её на 3 части и дополнили бы маленькими кучками из отвергнутых куч.
И чем бы отличались бы выбранные монеты в случае перевеса правой чашки от случая равновесия? Да ничем.
В обоих случаях было бы:
1-е взвешивание: на левой чашке - куча монет с верхним словом "Левая", на правой - "Правая".
2-е взвешивание: на левой часке - куча монет со словом "Левая" вторым сверху, а на правой - со словом "Правая" вторым сверху. При этом 1/3 монет в левой чашке будет иметь первым словом "Правая", 1/3 - "Левая" и 1/3 - "Резерв".
То же будет и на правой чашке.
5. Другими словами, мы можем разделить монеты ЗАРАНЕЕ и тупо взвешивать НЕЗАВИСИМО от результатов предыдущих взвешиваний.
И при этом мы получим АБСОЛЮТНО тот же результат, который бы получили на "безошибочных" весах, действуя традиционным (по дереву) способом.
6. Таким образом я продемонстрировал подход ЭКВИВАЛЕНТНЫЙ традиционному подходу, дающий СТОЛЬКО же взвешиваний, НО обеспечивающий НЕЗАВИСИМОСТЬ ввешиваний.
Очевидно, что вместо "Левая"/"Правая"/"Резерв" можно писать 0/1/2 и не сверху вниз, а слева направо, что и предлагал Илья.
7. Если мы результаты взвешиваний тоже будем записывать как 0/1/2, то получим К-разрядное слово полностью идентифицирующее фальшивую монету - это слово будет ПОЛНОСТЬЮ СОВПАДАТЬ с номером одной и ТОЛЬКО одной монеты.
8. Что бы мы делали с этим рез-том, если бы не надо было допускать одиночной ошибки весов? Да ничего. Это было бы нашим решением.
А что мы будем делать сейчас?

Показать скрытый текст

9. Да всё - просто. Что значит возможность одиночной ошибки?
Это значит, что полученный К-разрядный результат взвешивания может отличаться от истинного ТОЛЬКО ОДНИМ разрядом.
Что это значит?
Допустим мы получили результат 102 при развешивании наших 3^3 = 27 монет.
Каждый разряд (но только ОДИН!!!) может врать. Это нам даст монету с номером 102 (основной кандидат) и ещё 2*3 монет с номерами: 101, 100, 112, 122, 002, 202.
Вместе с нашей монетой - всего 7. (Для 3^10 монет было бы 2*10 + 1 монета).
10. С этими монетами мы проделываем следующее - выбираем 1 из 6 для 27 монет или 1 из 20 для 3^10 монет. Основных кандидатов мы не взвешиваем!!!
11. Полученного при дополнительных взвешиваниях кандидата взвешиваем с основным и выбираем "достойного"   
Итого: для 3^10 монет имеем: 10 + 3 + 1 = 14.     
12. А теперь я покажу трюк, когда одно взвешивание можно сэкономить.

Показать скрытый текст

13. Дело в том, что 2-й пакет взвешиваний (дополнительный) несколько отличается от первого. По идее, он не должен давать неравенств, если 1-й пакет был без ошибки. Поэтому, если на каком-то этапе оказалось неравенство, то:
а) либо ошибка в 1-м пакете,
б) либо ошибка в ДАННОМ конкретном взвешивании.
В любом случае после 1-го неравенства мы можем утверждать, что ПОСЛЕ ЭТОГО МОМЕНТА ошибок взвешивания быть НЕ МОЖЕТ, ошибка УЖЕ произошла.
А это значит, что после этого момента мы можем "работать" традиционно.
Поэтому мы УЖЕ можем добавить к "плохой" кучке нашего основного кандидата и продолжить работать с такой обновлённой кучкой, ЗНАЯ, что результат будет ОКОНЧАТЕЛЬНЫЙ.
Поэтому мы заинтересованы зафиксировать неравенство (если оно случится) тогда,  когда на "плохой" чашке - НЕ степень 3-ки.
В этом случае мы можем добавить нашего основного кандидата к монетам в "плохой" чашке, он нам не увеличит общее число взвешиваний (степень 3-ки не была перейдена)
Для этого мы заинтересованы зафиксировать неравенство КАК МОЖНО РАНЬШЕ - больше свободы манёвра.
14. Поэтому в 1-м из дополнительных взвешиваний мы берём 8 и 8, а оставляем 4.
Если произошло неравенство, то мы продолжаем работу с 9 монетами, добавив к "плохим" нашего основного кандидата из первого пакета.
При этом результат дальнейших взвешиваний - ОКОНЧАТЕЛЬНЫЙ:
- если ошибка в первом пакете, то добавленный основной кандидат не изменит рез-та
- если ошибка в этом нашем взвешивании, то больше ошибок не произойдёт и мы опять получим нашего основного кандидата, т.е. С ЭТОГО МОМЕНТА результат дополнительного пакета будет окончательным и нам НЕ НАДО будет сравнивать одного кандидата с другим.
15. В случае равенства при 1-м доп. взвешивании мы делим оставшиеся  4 монеты ПОПОЛАМ - 2 и 2 и делаем 2-е взвешивание.
При равенстве во 2-м взвешивании - всё, мы закончили, основной кандидат 1-го пакета и есть фальшивая монета.
В случае нерав-ва - добавляем к плохой куче нашего кандидата и определяем одного из 3-х последним взвешиванием.
Итого: для 3^10 монет требуется 10 + 3 = 13 взвешиваний.
16. Но при другом кол-ве монет это не всегда возможно.
Например при 3^4 монетах после 1-го пакета из 4-взвешиваний мы имеем 1-го основного кандидата и 2*4 = 8 потенциальных. 8 монет мы можем поделить лишь как 3-3-2 и в случае неравенства не сможем добавить основного кандидата без увеличения кол-ва взвешиваний. Поэтому нам потребуется: 4 + 2 + 1.
Поэтому общая формула для М монет: число взвешиваний Х для М монет:
Х = ([log₃M]+([1- {log₃}] + [log₃(2log₃M)+1] +[1-{log₃(2log₃M)}

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

[Redirect]

Вы точно человек ?

[Илья]

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

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

[buka]

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

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

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

[iPhonograph]

Мне надо было выразить целую часть числа в сторону увеличения

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

[Smith]

buka, спасибо за подробное и обстоятельное объяснение, к сожалению только сейчас выдалось свободное время, чтобы с ним ознакомиться.
если я правильно Вас понял, то для 27 монет раскладываем так, как показано ниже (кодировка - предложенная Ильей http://nazva.net/forum/in...96.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 - Основной Кандидат (ОК), и если бы весы показывали точно, то это и была бы фальшивая монета;
а далее мне не совсем понятно следующее:
1)какие монеты являются Потенциальными Кандидатами (ПК) (для представленного выше случая 3^3)?
2)как определить за 3(2) взвешивания 1 из 6 ПК (для данного случая 3^3)?
3)как учитываются монеты 11 и 17, котрые для случая ошибки при взвешивании (3) также становятся ОК (или они входят в группу ПК?)?
4)как определить за 3(2) взвешивания 1 из 20 ПК (для случая 3^10)??
спасибо за внимание и терпение

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

[buka]

В примере, на который Вы ссылаетесь допущена ошибка в кодировке
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 - равновесие.
Хочу подчеркнуть, что в принципе кодировка решающего значения не имеет, но выбрав другую кодировку, нам прошлось бы пересчитывать и мы бы запутались.
Поэтому для НАС кодировка ПОКА важна.
----------------------------------------------
Сообщите мне рез-ты взвешиваний и я Вам объясню, как мы выбираем монеты для дополнительных взвешиваний.

[Илья]

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

[buka]

Да, ошибка. Спасибо, Бука.

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

[Smith]

(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-ю систему..

[buka]

(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-ю систему..

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

[Smith]

(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

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

[buka]

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

[Smith]

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

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