Список голосов Thank You

[buka]

Хорошо, я попробую зайти с другого боку.
1. Среди скольких шаров (максимум) Х можно определить фальшивый, отличающийся от настоящего по весу, но неизвестно, в какую сторону, если у нас есть дополнительно один заведомо настоящий шар за К=1  взвешиваний (т.е. за одно взвешивание)?
Ответ: среди 2-х: кладём один из них на одну чашу, на другую - заведомо настоящий. Если весы в равновесии, то фальшивый - оставшийся. Если весы не в равновесии, то фальшивый - тот, что мы положили на весы.
Итак: К=1, Х=2 Запишем это так: Х(1) = 2.
2. Тот же вопрос, если К=2.
Рассуждаем следующим образом: какое-то кол-во шаров мы должны в первом взвешивании оставить в покое (не взвешивать), а остальные - сравнить взвешиванием.
Сколько можно оставить в покое максимум? Очевидно, не более 2, поскольку если среди сравниваемых фальшивого не будет, то нам останется одно взвешивание, а за одно взвешивание мы мошем определить фальшивый шар из двух (см. п.1)
Итак, П = Х(1) = 2.
А сколько шаров (В) можно сравнить взвешиванием?
Если фальшивый шар - среди В (т.е. весы - не в равновесии), то после первого взвешивания, мы знаем, что наш шар - либо среди тех, которые перевесили (Т) и тогда он - тяжелее, либо среди тех, которых перевесили (Л) и тогда он легче.
И вот на то, чтобы определить фальшивый среди В = Т+Л у нас осталось одно взвешивание (ведь одно уже "ушло") на то, чтобы определить - которые Т и которые Л.
А среди скольких шаров можно определить 1 фальшивый за одно взвешивание, если известно что наш шар - либо среди тех, которые перевесили (Т) и тогда он - тяжелее, либо среди тех, которых перевесили (Л) и тогда он легче?
Мы выяснили - что среди 3¹ шаров. Т.е. В = 3¹
Итак, если К=2, то Х = В+П = 3+2 = 5 (2 - если весы в равновесии, т.е. шар - среди П и 3 - если наоборот).
Запишем это: Х(2) = 5.
3. Аналогично можно убедиться, что Х(3) = 14 (Вы, Тиана, сами это расписали, помните?)
Как мы получили 14?
14 = 9 + 5 : 5 шаров в случае если шар среди тех, что мы оставляем в покое на 1-м взвешивании и 9 = 3².
Т.е. Х(3) = 3² + Х(2) = 3^3-1 + Х(3-1).
Т.е. при К=3: Х(К) = 3^К-1 + Х(К-1). (если К=3, то К-1=2)
И так далее.
Общая формула:
Х(К) = 3^К-1 + Х(К-1).
Но эта формула ещё не говорит нам - а какой вид у этой зависимости. Она рекурсивная и её надо раскрыть.
Не стесняйтесь, Тиана, спрашивайте, что Вам не понятно. Я постараюсь объяснить.