Для разминки вот вам задачка для школьников 😉

Существует ли конечное множество функций R–>R, композициями которых можно получить любой многочлен с целыми коэффициентами?

GD Star Rating
loading...
Конечное множество функций, 10.0 out of 10 based on 1 rating

57 Responses to Конечное множество функций

  1. Lanigram:

    С вероятностью 50% ответ — ДА.

  2. RaBig:

    Напомни, что такое композиция.

  3. rSuper:

    F(*) = *+1
    F(*) = 0
    F(*) = *–1

  4. rSuper:

    F(*) o G(*) = F(G(*))

  5. Hsv:

    Сложение и умножение, не пойдёт?

  6. Hsv:

    Ой блин, R–>R.

  7. rSuper:

    Почему нет? Что это R –> R значит по–твоему?

  8. Hsv:

    сложение и умножение это RxR–>R.

  9. Htyl:

    Можно ли задавать многочлен не композицией, а с использованием обычных арифметических действий, т.е. F(*)+G(*), с F и G произвольными из заданного множества? Или есть только F(G(*))?

  10. Htyl:

    В обещм, кажется, что этим можно, но доказать не могу :
    F(0)=1
    F1(*)=*+1
    F2(*)=–*
    F3(*)=*(*+1)

    Константные y=C делаются комбинациями F1 и F2, но это при условии, что можно многочлен задавать сложением функций: F1(*)+F2(*). Без этого даже константные задать не получится.
    Первая степень: F1(*)+F1(*)+…
    Повышение степени с порождением всех более низких получается применением F3. При этом коэффициент высшей степени будет 1, так что дальнейшими сочетаниями можно добиться любой комбинации более низких степеней.

    Вот как–то так. Если я правильно понимаю, задача найти минимальный набор функций не ставилась :

  11. Hsv:

    многочлен f(*)=0,5.

  12. AlMath:

    f1(*) = **2
    f2(*) = */ф, где ф — иррациональное и больше 1
    f3(*) = sin(*)
    f4(*) = cos(*)
    композиции понятно будут бесконечными.

    Если не ошибся, то вроде все.

  13. EvBig:

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

    А для этих функций неясно даже, почему бесконечная существует хоть в каком–то смысле (для произвольной композиции, их вообще–то континуум) 😉

  14. EvBig:

    Нет, только F(G(*)).

  15. EvBig:

    Целочисленные нужно.

  16. EvBig:

    Для сложения и композиции это действительно решение, но вообще–то в задаче можно пользоваться одной лишь композицией.

    И даже в этом случае ответ положителен. 😉

  17. NiDad:

    ребята, он над нами издевается. это какая–то адская алгебраическая фигня.
    подозреваю, что такое множество существует и называется базисом Грёбнера.
    EvBig, не томи, расскажи доходчиво что да как.

  18. EvBig:

    Это задачка то ли для 9–го, то ли для 10–го класса (не помню уже), какие базисы Грёбнера? :)))
    Подумайте ещё.
    Если не, вечером расскажу.

  19. Htyl:

    попытка №2 :
    F0(*)=1
    F1(*)=2*
    F2(*)=2^*
    F3(*)=***
    F4(*)=log2(*)

    «Руль где–то рядом» :

  20. Tavav:

    зная систему преподавания в школе, думаю надо посмотреть что проходили в это время по алгебре. Очевидно, задача крутиться вокруг какой–нибудь функции с особенными свойствами.

  21. Htyl:

    кстати, а производные уже были? Может их тоже…того 😉

  22. EvBig:

    Ну и как с помощью этого получить произвольный целочисленный многочлен c_0 + c_1 * + … + c_n *^n? 🙂

  23. EvBig:

    На олимпиадах задачи обычно крутятся вокруг наличия мозга у школьника* 🙂

    *Естественно, тут достаточно школьных знаний. Но тупо с помощью «тех функций, что проходили», думаю, ничего не получится.

  24. Tavav:

    так это олимпиадная? тогда действительно надо мозги. Справедливости ради надо сказать что олимпиадные задачи для школ так же как Сканави для ВТУЗов не всякий может решить.

  25. EvBig:

    Ну, задачи, для решения которых не нужно мозгов — это как–то грустно совсем. 🙂

  26. Tavav:

    вот я и грущу… сижу функции перебираю и понимаю что есть люди которые смотрят на задачу и видят ответ. Я вообще не математик, я инженер.

  27. rSuper:

    Ладно, как тогда сделать F(*) = C** с помощью композиции?

  28. Htyl:

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

  29. rSuper:

    Не работает с разными n по идее. Т.е. для каждой n мы должны создать отдельную функцию.

    Было бы клёвски сделать что–то типа F(*) = * + *, тогда F(F(*)) = 4 * *. но это не то — эдак мы любой n никак не получим всё равно

  30. Htyl:

    *двочиного представления числа
    Даже встречал когда–то задачу по возведению в степень одними умножениями за малое число шагов…но здесь немного другой случай, хоть и похоже. Пока сам не нашел решения, но есть ощущение, что это так :

  31. EvBig:

    Ну, если я напишу, как, будет сразу понятно, как решить всю задачу в целом. 😉

    В общем, если никто не осилит, часов в 9 вечера (по ДС) напишу своё решение.

  32. EvBig:

    Подсказка.
    На самом деле, целочисленные многочлены тут ни при чём.
    Для любого счётного семейства функций R–>R (то есть семейства, которое можно перенумеровать натуральными числами) существует конечное число функций, композициями которых можно получить любую функцию из семейства.

  33. rSuper:

    Вас ещё никто не спрашивает, господин ведущий!

  34. AlBig:

    сообразил после подсказки:
    возьмем биективную ф–ю R–>(1,0), f(*) = ( 1/pi * arctg(*) ) + 0.5
    возьмем биективную ф–ю (0,1) –> (1,2); g(*) = *+1

    пронумеруем все многочлены с целыми коэфф. (их счетное число) : p0, p1, …

    возьмем третью ф–ю (0, +inf) –> R, такую, что при * лежащем в (n,n+1) h(*) = (pn * f^(–1) * g^(–1) * g^(–1) * … * g^(–1))(*), (где g^(–1) — ф–я, обратная к g) взята n раз.( * — композиция ф–й )

    Тогда для любого pi искомой композицией трех ф–й (f,g,h) будет h * g * g * … * g * f, где g взята i раз.

    вроде все ок?

  35. EvBig:

    Ага, я так же решал. 🙂

    Если совсем гнусно придираться, нужно h ещё в натуральных и отрицательных точках доопределить как угодно, но это уже фигня.

  36. AlBig:

    еще раз убедился в справедливости слов своего научника: более общая задача часто решается проще чем частная 🙂

  37. AmCrazy:

    для любого pi )

  38. rSuper:

    Факинщит!

    где блог для дебилов?

  39. RaBig:

    фигню ты сморозил, друг. Видеть решение помогает только бэкграунд. Вдохновение свыше тоже не мешает, но на пустом месте такого не бывает. Так что завязывай с самоуничижением.

  40. Noan:

    В композиции каждая из функций может встречаться сколько угодно раз?

  41. EvBig:

    Да, главное, чтобы композиция была конечной.

  42. NiDad:

    так, я не доезжаю. это всё надо обдумать.

  43. Noan:

    Блин, всю голову уже сломал (:
    Только один вопрос: эта задача на данный момент решена?

  44. EvBig:

    Да, выше в комментах есть верное решение.

  45. Noan:

    я уж было поверил, но нет 🙂
    Дело в том, что тангенс многочлена в общем случае — функция непериодическая. Вы же при построении функции h(*) предлагаете брать куски тангенсов, однако после взятия арктангенса получится не первоначальная функция, а какое–то говно 🙂
    То есть для получения нужной нам функции нужно брать весь тангенс многочлена, а не его кусок.
    Контр пример в Вашему решению *2.
    А идея была просто отличная! Буду дальше думать…

  46. EvBig:

    Нет, вы просто не поняли решения.
    Суть решения в том, что R можно взаимно однозначно отобразить в (0,1). Арктангенсом или чем–нибудь другим — не суть, таких отображений континуум. Пусть это функция f.
    Если P — функция, вы же не будете спорить, что P(f^{–1}(f(*)) = P(*)?
    Теперь можно счётное количество R «упаковать» в R_+, отобразив i–е множество взаимно однозначно в (i,i+1). И на (i,i+1) положить h такой, чтобы P_i(f^{–1}((f(*) + i)–i)) = P_i(*), где P_i(*) — i–я функция.
    Тогда, чтобы получить P_j(*), нужно * «свернуть» в интервал (0,1), дойти до интервала (j,j+1) с помощью функции * |–> *+1 и применить h.

    Периодичность чего–либо здесь вообще не требуется.

  47. EvBig:

    Чтобы стало яснее, покажу, как получить *^2 😉

    Пусть *^2 идёт первым в списке наших функций, поэтому сдвигов применять не нужно.

    Тогда g(*) = 1/\pi (arctg(*) + \pi/2)
    h(*) = (tg((\pi *) — \pi/2))^2 на (0,1), а на остальных (n,n+1) нас не волнует 😉

    Тогда, очевидно, h(g(*)) = *^2.

  48. Noan:

    да, спасибо, понял 🙂 Отличная идея, я правда сначала не до конца ее понял.
    Красиво 🙂 ++
    P.S. и да, надо бы Виталика попросить, чтобы прикрутил хоть какой–нибудь простенький редактор формул, а то ж читать порой невозможно 😉

  49. VeMatematik:

    эээ
    ну например

    F0(*) = 1
    F1(*) = *
    F2(*) = *+1

  50. EvBig:

    Из этого композициями получаются только положительные натуральные константы и линейные многочлены (тоже не все).

  51. VeMatematik:

    F1(F2(*)) проверь

  52. AmCrazy:

    F1(F2(*)) = F2(*) = *+1

  53. VeMatematik:

    мдэ, и правда нестыковочка…

  54. Tavav:

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

Добавить комментарий