59049 монет

[buka]

Понял, спасибо. Здесь все мелочи важны. Сейчас исправлю.
А Вы пока скажите мне результат 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

(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

[buka]

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

[Smith]

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

[Smith]

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

[buka]

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

То есть на 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 монет, где нам удалось сэкономить на одном взвешивании.
Вопросы? Не стесняйтесь спрашивать.

[Smith]

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

То есть на 1-м взвешивании равенство, на 2-м и третьем перевесила правая чаша.
Итого мы имеем число 022 что даёт нам основного кандидата - 022 или номер 20.

Вопросы? Не стесняйтесь спрашивать.

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

[Smith]

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

То есть на 1-м взвешивании равенство, на 2-м и третьем перевесила правая чаша.
Итого мы имеем число 022 что даёт нам основного кандидата - 022 или номер 20.
ить на одном взвешивании.
Вопросы? Не стесняйтесь спрашивать.

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

[buka]

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

То есть на 1-м взвешивании равенство, на 2-м и третьем перевесила правая чаша.
Итого мы имеем число 022 что даёт нам основного кандидата - 022 или номер 20.

Вопросы? Не стесняйтесь спрашивать.

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

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

[Smith]

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

[Smith]

Кому-то может показаться, что если вместо взвешивания 002 и 012 лучше взвесить нашего основного кандидата 022 с одним из этих товарищей, то это - шило на мыло.
В случае равенства нам потребуется всё равно ещё одно взвешивание:
нашего 022 с оставшимся вторым.

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

[Smith]

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

[buka]

Кому-то может показаться, что если вместо взвешивания 002 и 012 лучше взвесить нашего основного кандидата 022 с одним из этих товарищей, то это - шило на мыло.
В случае равенства нам потребуется всё равно ещё одно взвешивание:
нашего 022 с оставшимся вторым.

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

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

[Smith]

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

[buka]

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

Хорошо.
У нас есть ОК и 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 и в последнем взвешивании определяем фальшивку окончательно.