задачка с решением (математическое)
Dec. 22nd, 2011 12:35 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
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) = x4/24 - x3/4 + 23x2/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.
Решение у нее немного нетривиальное, хотя в принципе ничего сложного нет. Я его дам под катом.
Понятно, что напрашивается предположение, что это значения какой-то не очень сложной функции, и если мы поймем, какой, то легко будет продолжить последовательность. Если мы обозначим эту функцию f, то можно предположить, что нам дали значения f(1), f(2), f(3), f(4), f(5), и если мы по ним сможем понять, что такое f(x), то следующее число будет просто f(6).
Самые логичные кандидаты на f(x), благодаря своей простоте - несомненно, многочлены. Поскольку у нас есть пять значений, можно надеяться, что есть единственный многочлен степени 4, который отвечает нашим условиям. И действительно, с помощью простых методов линейной алгебры (опускаю эту часть), легко видеть, что это многочлен
f(x) = x4/24 - x3/4 + 23x2/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.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
Re: явный вид полиномов
Date: 2011-12-26 12:25 am (UTC)обобщение
Date: 2011-12-26 02:35 am (UTC)Кстати, я своим студентам это дело в тот же день и рассказал -- обсуждались рекуррентные последовательности, и я как бы "к слову" вставил это дело.
Интересно, что происходит в аналогичном примере со степенями тройки. Легко проверить, что после
1, 3, 9, 27, 81
идёт число 211, то есть 35-25. Здесь формула для интерполяционного многочлена так же точно получается из биномиального выражения, но уже не степени x+1, а степени x+2.