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

[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

[(Anonymous)]

n!!! * sgn(n)? Какое-то непростое решение. В исходном посте была идея, что многочлен - самая простая функция, хотя известно, что интерполяционный многочлен Лагранжа аппроксимирует тем хуже, чем больше точек выборки взять.

[grur.livejournal.com]

Есть куда более красивая функция.

[(Anonymous)]

Рекуррентное соотношение f_n = (f_{n-1} + 1)!!!
Не знаю, насколько оно красивое. Но если не оно, то сдаюсь.

[avva.livejournal.com]

Не, это на самом деле f(n) = n{!}^n, т.е. n, после которого написано n факториальных знаков. Я неправильно помнил. Я бы не сказал, что это куда более красиво, но забавно, да.