12 шариков (самая лучшая задачка)

[buka]

Итак, из какого максимального кол-ва Х шаров можно за К взвешиваний определить один фальшивый?
Другими словами, нам следует найти зависимость Х(К).
1. Мы выделяем из Х шаров П, оставляем их в покое, а оставшиеся В сравниваем на весах (деля на 2 равные части если В чётно или на В/2 и В/2 -1 и добавляем один заведомо настоящий, если В - нечётно.
2.1 Если весы показали равенство, то фальшивый шар - среди П. Следовательно, П не должно быть больше некоторого кол-ва шаров, среди которых надо определить 1 фальшивый за К-1 взвешивание (ведь одно взвешивание мы уже произвели).
Следовательно, П <= Х(К-1). Саму формулу (зависимость) мы ещё не знаем, но в общем виде она такая, что если подставить туда К, мы получим Х1 = Х(К), а если подставить К-1 получим П=Х(К-1).
2.2 Если весы показали неравенство, то фальшивый шар - либо среди Т шаров и он тяжелее (Т - на той чаше, что перевесила), либо среди Л шаров и он - легче.
3. Но мы уже выяснили зависимость от K в этом случае и она равна 3^К, т.е. за К взвешиваний мы можем в этом случае выделить один фальшивый шар среди 3^К шаров, если известно, что он либо среди Т и более тяжёлый, либо среди Л и более лёгкий.
Но ведь на это у нас уже ушло одно взвешивание, т.е. осталось К-1 взвешивание и мы можем определить один фальшивый шар из 3^К-1 шаров.
Отсюда: В = 3^К-1 и Х(К) = В + П = 3^К-1 + X(K-1)

[Тиана]

buka, вам большое спасибо за объяснения  я как бы понимаю о чем вы говорите, но вот мат.запись ..... не совсем 

если подставить туда К, мы получим Х1 = Х(К), а если подставить К-1 получим П=Х(К-1).

это как получили? объясните плиз, если есть еще желание 

[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).
Но эта формула ещё не говорит нам - а какой вид у этой зависимости. Она рекурсивная и её надо раскрыть.
Не стесняйтесь, Тиана, спрашивайте, что Вам не понятно. Я постараюсь объяснить.

[Тиана]

buka, теперь почти все понятно, спасибо 
но .... я думала, что на общей формуле все закончится, а тут похоже только все начинается 

[buka]

Да нет, мы почти у финиша. Раскрыть эту рекурсию очень просто.
Показать скрытый текст

Х(К) = 3^К-1 + Х(К-1).
Х(К-1) = 3^К-2 + Х(К-2).
...
Х(2) = 3¹ + Х(1)
Х(1) = 3⁰ + Х(0)
Х(0) - это среди скольких шаров можно определить 1 фальшивый вообще не взвешивая.
Очевидно, что Х(0) = 1, т.е. вообще не взвешивая можно определить один фальшивый шар среди одного
Таким образом, мы получили сумму степенного ряда + 1. Это легко вычислить:
X(K)  = 3^К-1 + 3^К-2 + 3^К-3 +...+ 3¹ + 3⁰ + 1 = (3^К+1)/2
Итак: X(K) = (3^К+1)/2

[Тиана]

класс 
это уже финиш? 

[семеныч]

класс 
это уже финиш? 

продолжайте


нам нравится

[buka]

класс 
это уже финиш? 

Для этой задачи - да
Но за это время я решил и другую задачу - для случая, когда надо определить и фальшивый шар и в какую сторону он отличается

[Илья]

Но за это время я решил и другую задачу - для случая, когда надо определить и фальшивый шар и в какую сторону он отличается

Тиана - это намек.
Новое домашнее задание.

[Smith]

Илюха, я в 10-м классе решил задачу - как можно за 3 взвешивания определить фальшивую монету из 10-ти, причем в отличие от моих товарищей, решавших в последствии ее в институте уже, мое решение предусматривало безусловно однозначное определение фальшивой монеты в плане легче/тяжелее..
так что я вполне "прохавал тему" от buka

[Тиана]

Для этой задачи - да
Но за это время я решил и другую задачу - для случая, когда надо определить и фальшивый шар и в какую сторону он отличается

делов-то  еще одно взвешивание (К+1) и все  Показать скрытый текст

это я шалю чуть 

[Smith]

Для этой задачи - да
Но за это время я решил и другую задачу - для случая, когда надо определить и фальшивый шар и в какую сторону он отличается

делов-то  еще одно взвешивание (К+1) и все  Показать скрытый текст

это я шалю чуть 

ой не бегай, кандидат! (с) ММЖ

[buka]

Вас может удивить, но решение также простое:
если у нас есть дополнительный заведомо настоящий шар, то в этом случае:
Х(К) = (3^К - 1)/2, если нет, то Х(К) = (3^К - 1)/2 - 1.

[Тиана]

buka, если я правильно поняла, то  при помощи
Х(К) = (3^К - 1)/2 - 1
можно рассчитать количество шаров, когда у нас нету заведомо настоящего шара и точно сказать тяжелый он или легкий, так?
если да, то при 3 взвешиваниях максимум будет 12 шаров, а ведь есть способ и для 13
или же я опять чего-то недопонимаю 

[buka]

buka, если я правильно поняла, то  при помощи
Х(К) = (3^К - 1)/2 - 1
можно рассчитать количество шаров, когда у нас нету заведомо настоящего шара и точно сказать тяжелый он или легкий, так?
если да, то при 3 взвешиваниях максимум будет 12 шаров, а ведь есть способ и для 13
или же я опять чего-то недопонимаю 

Для 13 - нет возможности - и определить фальшивый и узнать лёгче он или тяжелее во ВСЕХ случаях...
Есть ситуация, когда какой шар - фальшивый определить можно, но при этом не узнать - легче он или тяжелее...
Только 12 ...