Блин, снова монетки

[Lepra]

Я-то думала, что на этом эпопея точно завершилась. Ан нет, выяснилось, что 12 монеток - это не максимальное количество. Решила найти формулу, по которой буду всегда знать максимальное колличество монеток, из которых можно найти фальшивку, при любом количестве взвешиваний. Получилось, поэтому могу формулировать теперь какие угодно задачи на эту тему. Например за семь взвешиваний можно однозначно определить фальшивку знаете из какого числа монеток? Ни за что не поверите, из 977 монеток )))

Решение привожу в комментариях.

Comments

[Lepra]

Задача: Найти формулу, описывающую максимальное число монеток, среди которых можно по весу однозначно определить фальшивую за n взвешиваний на двучашечных весах, при условии, что неизвестно, в какую сторону фальшивая по весу отличается от настоящих



Решение:

Все очень просто, идем по порядку - решаем сначала задачку в ноль взвешиваний, потом в одно, и усложняем себе жизнь потихонечку. Но перед этим определимся, что вариант задачи будет обозначаться цифрой и буквой. Цифра означает, сколько взвешиваний разрешено, буквы дают дополнительную информацию:



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

б) определение фальшивки при наличии эталонной монетки (э)

в) определение фальшивки когда известно, в чем их подозревать (знак подозрительности - л или т)



о взвешиваний - одна монетка, она и есть фальшивая



1а = одна монетка, она и есть фальшивая

1б = две монетки, одну из них сравниваем с эталонной

1в = три монетки, сравниваем те, которые имеют один знак подозрительности (л с л или т с т)



2а - тут за первый ход мы разделяем монетки на те, что лежат отдельно, и те, что будут нами взвешены. сколько максимум мы можем отложить вне весов? ответ - 1б, ибо останется один ход, а эталонные монетки у нас уже будут в распоряжении. Сколько должно лежать на весах? после первого взвешивания у нас уже определится знак всех монет на весах, поэтому как бы действует пункт 1в, но так как нечетное число класть нельзя, то тоже только две. Итак 2а = четыре монетки

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

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

3а - ход, опять же, состоит из двух вариантов - равновесие на весах, и мы переходим к отложенной кучке, и отклонение. При равновесии спускаемся к варианту 2б - ибо эталонными располагаем, но знаков подозрительности не имеем. ну а на весах у нас должно быть число, равное 2в. Итак вместе мы получаем 3а = 13 монеток.

3б - куда бы нам использовать эталонную монетку? В кучку на равновесие не положишь - там итак есть эталонная - пятая, больше не пригодится. А с весами? А вот там запроста. Ведь у нас была проблема с нечетностью на весах - на втором ходу мы могли бы отложить три монеты, и по три монеты на весы, то есть девять, но девять монет мы изначально не завесим, а вот десять это пожалуйста. В таком случае у нас будет четыре монетки одного знака, пять монеток другого, из этих пяти мы три отправляем в отложенную кучку и приходим к варианту 1в, а остальные распределяем по чашам как уже проходили. Итак 3б = 14

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

4а - по аналогии с 2а и 3а - есть сумма 3б и 3в, то есть 4а = 38 монеток.

4б - по аналогии с 2б и 3б - есть 4а, в которой на единицу увеличено число в кучке после первого хода - не 8, а девять. Соответственно 4б = 39 монеток.

4в слагается из трех 3в (ибо там опять число монеток четное и выкидывать ничего не надо, вообще же далее число монеток всегда будет четное, ибо четное число, увеличенное в три раза, всегда будет четным) 4в = 72



Итак можно увидеть формулу -

nа = (n-1)б + (n-1)в

nб = nа + 1

nв = 3(n-1)в, при n-1 > 1, nв = 3(n-1)в - 1 = 8, при n-1 = 1, nв = 3, при n = 1



попробуем раглядеть прогрессию:

3а = 2в + 2б = 8 + 5

4а = 2в*3 + 3а+1 = 8*3 + 8 + 5 + 1

5а = 8*3*3 + 8*3 + 8 + 5 + 1 + 1

6а = 8(3^(6-3) + 3^(6-4) + 3^(6-5) + 1) + 5 + (6-3)

nа = 8 (Сигма(i=[0; n-3]) 3^i) + n + 2 = 8(3^(n-2)-1)/(3-1) + n + 2 = 4*3^(n-2) + n - 2





Ответ: за n взвешиваний фальшивку можно выявить из максимум 4*3^(n-2) + n - 2 монеток при n >= 2.

[x_petrs_o]

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

Да уж.... Лепра... ну ты даешь... у меня даже слов нет...

[Merfanef]

Senior



У меня слова есть, но они нецензурные.

[Cara]

Молодец Lepra !!! Так держать! Не дай себе засохнуть!

[Lepra]

Petrs Senior Merfanef Cara



я сама офигела. Катаюсь на катке, и тут меня как обухом ударило...



честное слово, не хотела, я не на зло )))

[Acsinia]

Lepra кажется у меня закипел моск