задачка с решением (математическое)

[avva]

Задачка такая: продолжить последовательность чисел 1,2,4,8,16...

Решение у нее немного нетривиальное, хотя в принципе ничего сложного нет. Я его дам под катом.


Понятно, что напрашивается предположение, что это значения какой-то не очень сложной функции, и если мы поймем, какой, то легко будет продолжить последовательность. Если мы обозначим эту функцию f, то можно предположить, что нам дали значения f(1), f(2), f(3), f(4), f(5), и если мы по ним сможем понять, что такое f(x), то следующее число будет просто f(6).

Самые логичные кандидаты на f(x), благодаря своей простоте - несомненно, многочлены. Поскольку у нас есть пять значений, можно надеяться, что есть единственный многочлен степени 4, который отвечает нашим условиям. И действительно, с помощью простых методов линейной алгебры (опускаю эту часть), легко видеть, что это многочлен

f(x) = x⁴/24 - x³/4 + 23x²/24 - 3x/4 + 1

Легко проверить, что его значения для x=1,2,3,4,5 как раз равны 1,2,4,8,16. А если подставить x=6, получим f(x)=31. Очевидно, это и есть правильный ответ.


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

источник: Carl E. Linderholm, Mathematics Made Difficult.

Comments

явный вид полиномов

[falcao.livejournal.com]

Интересно, что это верно для любого количества членов.

Если начать с последовательности 1, 2, то "очевидно", что далее идёт 3, что соответствует линейной функции. Далее, если даны члены 1, 2, 4, то из их разностей формируется последовательность 1, 2, и потому следующая разность должна быть равна 3, то есть продолжение имеет вид 1, 2, 4, 7. Это соответствует квадратичной функции. Далее по тому же принципу после 1, 2, 4, 8 с разностями 1, 2, 4 должно идти 7, то есть следующий член равен 15, и так для любой степени.

Можно при этом "сходу" выписать сам полином f(x) степени n, значения которого в точках 0, 1, 2, ..., n равны степеням двойки. Это будет сумма вида C_x^0+C_x^1+C_x^2+...+C_x^n, где C_x^k равно x(x-1)(x-2)...(x-(k-1))/k!

Здесь ясно как то, почему сначала будут идти 2^0, 2^1, ... вплоть до 2^n, так и то, почему далее пропадает единичка (не хватает числа сочетаний из n+1 по n+1). Интерполяционный многочлен из условия задачи, соответственно, будет равен f(x-1).

Re: явный вид полиномов

[avzel.livejournal.com]

Я не заметил этого Вашего замечания, и запостил у себя http://avzel.blogspot.com/2011/12/polynomial-interpolation-for-powers-of.html то же самое.

обобщение

[falcao.livejournal.com]

Это соображение очень естественное -- совершенно не удивительно, что оно могло прийти в голову многим людям.

Кстати, я своим студентам это дело в тот же день и рассказал -- обсуждались рекуррентные последовательности, и я как бы "к слову" вставил это дело.

Интересно, что происходит в аналогичном примере со степенями тройки. Легко проверить, что после

1, 3, 9, 27, 81

идёт число 211, то есть 3⁵-2⁵. Здесь формула для интерполяционного многочлена так же точно получается из биномиального выражения, но уже не степени x+1, а степени x+2.