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

Возможно и была. Но вот я сколько не просмотрела,  развернутого ответа нигде не нашла, сама решала, получилось 99 монет, а по ответу гораздо больше . Если можно дать не просто ответ, а развернутое решение. Просто интересно.

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

Найдите максимальное N при котором можно найти фальшивую не более, чем за 7 взвешиваний на этих весах.

:crazy: :roll: :-[
Очень оригинальная трактовка вопроса  :wall:
Очевидно 7 и есть максимальное число если в фильтрах - "не более чем за 7
Да и имхо в таких задачач искать МАКСИМАЛЬНОЕ ЧИСЛО - чушь - однозначно - бесконечность, сиди и взвешивай 1-1, 2-2 ну и т.д.
"

У меня тоже пока 99 получается.
иду от обратного: в конце должно быть 3 монеты.

379

решение:
Показать скрытый текст

я же просила решение, а не мнение, чушь это или не чушь, если не понимаете, зачем захламлять тему?

в ответе написано 527, а вот решения там нет, как они пришли к этому числу.

Фиг его знает.
я до 219 досчитал:)
1 взвешивание: 33 и 33. 153 остается. Если в одной из кучек по 33 есть фальшивая- находим еще за 6 взвешиваний. Если 33 = 33, берем из оставшейся кучи 153  по 27(нужно, чтоб в случае равенства весов, осталось еще 1 взвешивание неравных весов). Взвешиваем. Показывают неравенство. Находим фальшивую. Нет. Берем из большей оставшейся кучи по 21 монет (за 5 взвешиваний, включая 2 возможности взвесить неравный вес).
и так далее...

RD
Уже прогресс. Попробую посчитать с конца. :-\ с 527 , только вот как  это число разбить. :roll:

Прочтите ещё раз решение iPhonograph и вникните в него.
Даю подсказки.
Если нам можно К раз взвешивать, но только 1 раз из этих К допускается неравенство, то мы можем выделит лёгкую из 2К+1 монет: каждый раз взвешивается пара, неравенство даёт ответ, равенство -> берём следующую пару и т.д.
Если все 2К взвешиваний дали равенство, то последняя (2К+1)-я монета фальшивая.
Теперь рассмотрим в-т когда дважды допускается неравенство и можно К раз взвешивать.
1-е взвешивание:
2К-1 монета на одной чашке и столько же на другой.
В случае неравенства - у нас ещё есть К-1 взвешивание для 2К-1 монеты.
В случае равенства - 2-е взвешивание - по 2К-3 монеты на каждой чашке и т.д.
То есть всего можно взвесить: 2К-1 + 2K-3 + 2K-5... и т.д. - сумму найти просто.
По аналогичному принципу определяется общее кол-во монет, когда допустимы 3 взвешивания с неравенством и т.д.
iPhonograph привёл рекурсивное решение общего вида (или рекуррентное, уж и не помню как верно).

buka
а васне смущает вот это условие?

К сожалению то, что написал iPhonograph, для меня китайская грамота. Пусть он хоть тысячу раз прав. Ваши примеры мне более понятны.
Но решение iPhonograph у меня что- то не получается:)
Решаю так:
Пусть сразу после 2- х взвешиваний неравных весов осталось X монет. То есть, после 2- го взвешивания Х монет. Тогда на втором взвешивании можно было бы взвесить X и X монет. X осталось бы в запасе. Тогда после первого взвешивания можно было бы взвесить 3X и 3X.
X = 2*(K - 2) + 1 - где K - кол- во взвешиваний.
То есть, кол- во монет при 7 попытках для взвешивания было бы: 6*(2*(K - 2) + 1) = 66
Если бы весы показали равенство при взвешивании 33 и 33, взяли бы 6 * (2(K-3)+1) = 54
на последних двух попытках для взвешивания можно оставить 9 монет для первого взвешивания (3+3+3), и (1+1+1), для последнего взвешивания оставим 3 монеты.
Итого считаю и получаю: 231

В запасе осталось бы не X, а больше.

В какой момент больше?
В запасе при втором взвешивании я имел в виду.
То есть : X = 2*(K-2)+1
на 2- м взвешивании можно было взвесить X и X, На первом - 3X и 3X.

Почему из утверждения
ты делаешь вывод, что
?

На втором взвешивании ты взвешиваешь X и X, но в запасе у тебя остаётся не X, а какое-то Y большее X. Так что на первом взвешивании ты моешь взвесить 2X+Y и 2X+Y

Так: я на первом взвешивании взвешиваю 33 и 33 монеты (3X и 3X). В случае их неравенства
проверяю кучку 3X с фальш. монетой взвешиванием X и X.

Тоесть получается так. Ты взвешиваешь 33 и 33 и не взвешиваешь ещё 33?

У меня монет всего( 33 + 33, 27 +27, 21 + 21, 15 +15, 27, 9, 3)
я проверяю 33 и 33.
в случае 1 - го неравенства 11 и 11 и заодно 11, которые отложил.

А почему ты откладываешь столь же, сколько и взвешиваешь? Ведь если у тебя взвешенные кучки будут равными по весу, то ты возмешь всё теже 11, но на один неравный ход у тебя будут больше.

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

Нет, не смущает.
Итак, в общем случае: нам надо найти максимальное N монет, среди которых одна фальшивая, причём весы ломаются после Х взвешиваний где неравенство и за не более чем К взвешиваний.
То есть, нам надо найти N как функцию Х и К (у Вас - Х=3,K=7)
Если Х = 1, то N(X,K) = N(1,K) = 2K+1. С этим, думаю, ясно.
Если Х = 2, то N(X,K) = N(2,K) = 2*(N(1,K-1)+N(1,K-2)+...+N(1,2)+3¹
Если Х = 3, то N(X,K) = N(3,K) = 2*(N(2,K-1)+N(2,K-2)+...+N(2,3))+3²
Рекурсивно:
N(X,K) = 2*(N(X-1,K-1)+N(X-1,K-2)+...+N(X-1,X))+3^X-1

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

Ну дак кто межает взвешивать всё теже 11, а откладывать (не взвешивать) больше