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

[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]

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

[cema.livejournal.com]

+1

[xxqs.livejournal.com]

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

[xxqs.livejournal.com]

вру, 2^(x-1)

[tandem-bike.livejournal.com]

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

[amigofriend.livejournal.com]

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

[dimrub.livejournal.com]

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

[avva.livejournal.com]

:)

[(Anonymous)]

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

[cema.livejournal.com]

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

[captain-tylor.livejournal.com]

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

[oblomov-jerusal.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]

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

[kblcbka.livejournal.com]

:)))

[grur.livejournal.com]

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

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

[(Anonymous)]

Лол что? А функция какая?

[olkab.livejournal.com]

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

[avzel.livejournal.com]

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

[ilya-dogolazky.livejournal.com]

Вообще-то да. Тут этот многочлен вылезает как рояль из кустов. Пропедевтически правильнее было бы решение с разностями.

[bugabuga.livejournal.com]

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

[kcmamu.livejournal.com]

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

[vaniusha.livejournal.com]

+1. Задача сформулирована некорректоно. "ПРодолжить последовательность" <> "отыскать функцию от аргумента, гдле аргументом служит порядковый номер значения функции в приведенной последовательности".
Простейший ответ на вопрос "продолжить последовательрность" - это 32. который получается умножением предыдущего члена последовательности на 2.
поскольку это работает для всех приведенных членов последовательности то это и является именно ПРОСТЕЙШИМ решением. притом - корректным :)

[vdinets.livejournal.com]

очаровательно :-)

[kirenenko.livejournal.com]

Думал, что будет про это

Place n points along a unit circle, in such a way that when you draw all lines connecting every pair of points, no more than two lines pass through any interior point. How many regions does this divide the unit disk into?
(гуглится)

А тут какие-то многочлены 4й степени, которых не бывает в природе...

[spamsink.livejournal.com]

Вариантов масса: https://oeis.org/search?q=1,2,4,8,16,31

[amok-life.livejournal.com]

Это что-то феерично прекрасное...

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

[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 то же самое.

[diana-shipilova.livejournal.com]

У Гарднера в «Математических досугах» было похоже: он показывал, что ряд 0, 1, 2, 3... можно продолжить числом 5 (по формуле n + 1/24*n(n − 1)(n − 2)(n − 3)).

[http://users.livejournal.com/_winnie/]

Решение у Аввы забавно тем, что выбирается некий разумный вариант бритвы Оккама, который приводит к неочевидному результату.

0,1,2,3 приближается многочленом (n-1) который проще чем n + 1/24*n(n − 1)(n − 2)(n − 3) по всем разумным метрикам.

[aleiner.livejournal.com]

good

21 или 10^21

[muchkap.livejournal.com]

Если записать по-английски и посчитать буквы, получится ряд Фибоначчи плюс два. Значит следом идет число, записываемое 10 буквами: twenty-one. Если без дефисов и пробелов – sextillion.

[iq-21.livejournal.com]

Обжигался на подобных вопросах во время IQ-теста.
По-видимому создатели теста в упор не замечали самых элементарных функций.

[(Anonymous)]

Если интересны математические шутки, то Математическая смесь Литтлвуда гораздо интереснее,

дежавю формат

http://www.krelib.com/nauchnopopuljarnaja_literatura/2512

[http://users.livejournal.com/_winnie/]

Авва, а можете посмотреть этот современный вариант бритвы Оккама? http://users.livejournal.com/_foreseer/54671.html?style=mine

[http://users.livejournal.com/_winnie/]

Эпикур: нельзя исключать любую гипотезу, объясняющую явление (включая рака за горой?)
Байес: Да, все но некоторые надо рассматривать с меньшими весами. (как выбрать веса, что бы не зависеть от единиц измерения?)
Оккам: Лучше выбрать самую простую (что значит простую?)
Колмогоров: Простую - значит для которой нужна самая маленькая машина Тьюринга.
Соломонов: Вероятность гипотезы в байесовской методике пропорцинальна 2^^{-сложность гипотезы}

[crazyhome.livejournal.com]

Ну, я так и подумал ;)