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

[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

[amigofriend.livejournal.com]

Десять лет как жизни нет. Всё Колмогоровы, Линдерхольмы, Фихтенгольцы, всякие там Сканави.

[xxqs.livejournal.com]

и чем же f=2^x не проще?

[tandem-bike.livejournal.com]

однако шутник Карл!

[xxqs.livejournal.com]

вру, 2^(x-1)

[amigofriend.livejournal.com]

Вы прочитали название книги?

[xxqs.livejournal.com]

а, теперь да :)

[dimrub.livejournal.com]

Типичный overfit, кстати :).

[(Anonymous)]

На мой взглад, утверждение "Самые логичные кандидаты на f(x), благодаря своей простоте - несомненно, многочлены" весьма спорно.

[captain-tylor.livejournal.com]

Правильный ответ - 32
Если считать простейший ответ по количеству символов в формуле.

[avva.livejournal.com]

:)

[amigofriend.livejournal.com]

как у нас говорили - шалунишка.

[homotub.livejournal.com]

это прекрасно)))

more of the same

[kot-begemot.livejournal.com]

http://www.whydomath.org/Reading_Room_Material/ian_stewart/9505.html

[trurle.livejournal.com]

Удивительно с какой точностью полиномиальная аппроксимация воспроизводит экспоненту.

[grur.livejournal.com]

Чуть менее нетривиальная Хофштадтеровская последовательность: 0, 1, 2, ... ?

(правильный ответ: 720 факториал)

[gwadelup.livejournal.com]

Хех, примерно это же хотел написать. Бритва Оккама наше всё :)

[olkab.livejournal.com]

Ах как хорошо!

[avzel.livejournal.com]

Ну да. А разве бывают другие решения? :)

[kblcbka.livejournal.com]

:)))

[malyj-gorgan.livejournal.com]

Но все же, хоть и немножечко, да отстает, ибо рожденный ползать...

[cema.livejournal.com]

+1

[cema.livejournal.com]

Спорно, но логично!

[bugabuga.livejournal.com]

Напоминает систему предложения маршрута от Амтрака :)
Где при попытке съездить из Остина в Лос Анжелес предлагается не Остин-Сан Антонио-Лос Анжелес, а упорно рекоммендуется маршрут через штат Иллиноис или через Монтану :)

[kcmamu.livejournal.com]

В таких задачах более естественным представляется вычислять не отдельный элемент последовательности, а все подряд по очереди; при этом нам оказывается доступен набор ранее вычисленных предыдущих значений. В этом смысле вычислительная схема f(t)=2f(t-1) проще многочлена с кучей коэффициентов: для вычисления очередного значения нужно выполнить всего одно арифметическое действие.

[amigofriend.livejournal.com]

= 32

а толку...