На любые вопросы дает любые ответы

[spamsink]

Задачка для занимательных математиков и любознательных программистов:

Не глядя в интернет, придумайте вещественную функцию от вещественного аргумента, которая на любом интервале ненулевой длины принимает все возможные значения, т.е. ∀a:∀b>a:∀y:∃x,a<x<b:f(x)=y

(Теперь мы знаем, что такое "Черный квадрат" — график этой функции.)

Оригинальный ответ: Конвеева трискайдекафункция

Comments

[amigofriend.livejournal.com]

Квадрат?

[spamsink]

Ну так графики обычных функций тоже не бесконечные рисуют, а в ограниченном диапазоне что по х, что по у.

[rezkiy.livejournal.com]

С указанной формулировкой, константа подойдет.

[spamsink]

Надо формально - будет формально: ∀a:∀b>a:∀y:∃x, a<x<b:f(x)=y

[archaicos.livejournal.com]

Что значит все возможные? От минус бесконечности до плюс бесконечности?

[spamsink]

Да, ∀a:∀b>a:∀y:∃x, a<x<b:f(x)=y

[freeborn.livejournal.com]

тангенс ( мантисса * 2pi - pi)

[freeborn.livejournal.com]

а, забыл мантиссу на 10 разделить

[spamsink]

Возьмем диапазон от 10¹⁰⁰ до 10¹⁰⁰+10^-100.

[yatur.livejournal.com]

Ну, скажем такая идея:

1. Представляем аргумент в виде десятичной дроби.
2. Если десятичная дробь получилась бесконечная, то f(x)=42.
3. Если десятичная дробь конечная (т.е. x = n*10^k для некоего целого n и целого k), записываем ее задом наперед, приписывая в качестве целой части ноль. Получится число из интервала (0,1). Скажем, из 123.4567 получится 0.7654321.
4. Прогоняем получившееся число через функцию типа tan(x*pi/2), которая превращает (0,1) в (-inf,+inf).
5. Особый случай: f(0) = 0.

Пример:

f(0) = 0.
f(1) = tan(0.1*pi/2) = 0.15838444032453629383888309269437
f(1.00099) = tan(0.990001*pi/2) = 63.663108520903310110316979529304
f(1.000999999) = tan(0.9999990001*pi/2) = 636683.44071112896191064686511318
f(pi) = 42

[spamsink]

Как доказать, что на любом интервале найдется любое значение?

[ilya-dogolazky.livejournal.com]

выкинув на шаге 2 все числа с бесконечной десятичной записью, вы останетесь только с рациональным (да и то не со всеми), рациональных не хватит для заполнения несчётных интервалов

[kcmamu.livejournal.com]

Возьмем 5-ричную бесконечную запись дробной части аргумента и "исполним" ее как программу в таком языке:

0 -- print("0")
1 -- print("1")
2 -- print("-")
3 -- print(".")
4 -- стереть всё ранее напечатанное

Корректными программами объявим {[0-4]*4}?2?[01]*3[01]{∞}

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

[spamsink]

Заскриню.

[ygam.livejournal.com]

записать x в виде двоичной строки s, отбросив десятичную точку

разбить s на куски согласно универсальному коду; после каждых двух кусков оставить 1 бит; декодировать куски согласно коду: (i0,j0,b0),(i1,j1,b1),{i2,j2,b2),(i3,j2,b3)..., где i_n и j_n - положительные целые числа, а b_n - либо 1, либо 0.

Создать бесконечную двоичную последовательность t, сначала состоящую из нулей, но потом установить бит t[i1]=b1; t[i2]=b2; t[i3]=b3... Если процесс не сойдется на одной t, то пусть функция возвращает 0; если сойдется, то пусть под t мы дальше понимаем предел этого процесса.

Если последовательность j1, j2, j3... не начинает равняться 1 с какого-то j_n, то пусть функция возвращает 0; если начинает, то пусть N - наименьшее n, после которого все j_n равняются 1. Мы ставим в t десятичную точку после floor(N/2) цифр, преобразуем двоичную строку с точкой в число, ставим знак минуса если N нечетное, и возвращаем его.

Итак, чтобы получить (-1)**(N%2) * a1a2a3a4...aN/2.aN/2+1aN/2+2... нам нужно двоичное число ...C(1)C(2)a1C(2)C(2)a2C(3)C(2)a3C(4)C(2)a4...C(N)C(2)aNC(N+1)C(1)aN+1C(N+2)C(1)aN+2... где C(x) - кодирование универсальным кодом. Заметьте, что у двоичного числа может быть абсолютно любое начало (пропустив число бит, которое требует универсальный код), так как все изменения в t, вызванные началом числа, потом можно переписать.

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

[spamsink]

Способ годный, но бешеный. :) Заскриню.

[sab123.livejournal.com]

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

Впрочем, это дает только целые числа в Y.

[galkao.livejournal.com]

"Черный квадрат" никак не получится при такой постановке задачи. У функции ОДНОМУ значению аргумента соответствует ровно одно значение функции. Иначе это - не функция:-) То есть графиком функции всегда является линия (или ее кусочки). Но никогда не может быть нечто "объемное".

[dluciv.livejournal.com]

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

[spamsink]

Эта функция разрывна в каждой точке, какие уж тут линии. А раз она принимает значения от плюс до минус бесконечности в вертикальной полосе любой ширины, то ее можно изобразить, полностью заштриховав плоскость вертикально. :)

[dluciv.livejournal.com]

Предел функциональной последовательности. Не обязательно конечно, но так должно быть легче всего описать.

Что-нибудь типа правильно отмасштабированного синуса, у которого частота стремится к бесконечности, должно подойти. Красиво писать формулу на планшете тяжело, поэтому не стану.

Либо адский хэш, как ниже в коментах было. Я не читал подробно, но расхожий способ — взять числа от 0 до 1, а потом из нечётных цифр составить аргументы, а из чётных соответствующие им значения. И для каждого из аргументов брать одно из значений по какому-нибудь выудуманному принципу, но чтобы размазывалось хорошо.

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

+1 к пределу $n * sin(x / n)$

[carla461.livejournal.com]

не конструктивный способ - взять любую биекцию между классами эквивалентности R/Q и R а потом расширить ее до функции R->R присвоив одинаковые значения на всех элемантах в каждом из классов

[spamsink]

Классы эквивалентности R/Q - это сильно неконструктивный способ. :) Но идея построения в чем-то схожая.

[mikev.livejournal.com]

Возьмем двоичную запись дробной части числа и разобьем ее на последовательные группы из 1,1,2,2,4,4,8,8... знаков.
Первой группе сопоставим множитель (+1/2), второй - (-1/2), третьей - (+1/4), четвертой - (-1/4) и т.д. Затем сложим единички из каждой группы с соответствующими множителями. Например, для числа 110,100101100010110010111100... разбивка будет 1 0 01 01 1000 1011 0010111100..., а сумма:
1/2 - 0/2 + (0+1)/4 - (0+1)/4 + (1+0+0+0)/8 - (1+0+1+1)/8 + (0+0+1+0+1+1+1+1+0+0)/16 - ...
Если для числа x такой ряд расходится, зададим f(x)=0, а если нет f(x)=предел ряда.

[spamsink]

Как это будет работать для произвольно малых интервалов?

[codedot.livejournal.com]

Неплохо было бы еще затребовать от функции всюду определенность и вычислимость.

[freeborn.livejournal.com]

Все вещественные, или хватит и рациональных?

[spamsink]

Все вещественные.