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

[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