?

Log in

No account? Create an account

На любые вопросы дает любые ответы - Общество дровосеков Бердичева по изучению Мишны

Nov. 14th, 2014

04:15 pm - На любые вопросы дает любые ответы

Previous Entry Share Next Entry

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

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

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

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

Comments:

[User Picture]
From:amigofriend
Date:November 15th, 2014 12:18 am (UTC)
(Link)
Квадрат?
(Reply) (Thread)
[User Picture]
From:spamsink
Date:November 15th, 2014 12:29 am (UTC)
(Link)
Ну так графики обычных функций тоже не бесконечные рисуют, а в ограниченном диапазоне что по х, что по у.
(Reply) (Parent) (Thread)
From:rezkiy
Date:November 15th, 2014 12:29 am (UTC)
(Link)
С указанной формулировкой, константа подойдет.
(Reply) (Thread)
[User Picture]
From:spamsink
Date:November 15th, 2014 12:33 am (UTC)
(Link)
Надо формально - будет формально: ∀a:∀b>a:∀y:∃x, a<x<b:f(x)=y
(Reply) (Parent) (Thread) (Expand)
[User Picture]
From:archaicos
Date:November 15th, 2014 12:33 am (UTC)
(Link)
Что значит все возможные? От минус бесконечности до плюс бесконечности?
(Reply) (Thread)
[User Picture]
From:spamsink
Date:November 15th, 2014 12:34 am (UTC)
(Link)
Да, ∀a:∀b>a:∀y:∃x, a<x<b:f(x)=y
(Reply) (Parent) (Thread)
[User Picture]
From:freeborn
Date:November 15th, 2014 01:17 am (UTC)
(Link)
тангенс ( мантисса * 2pi - pi)
(Reply) (Thread)
[User Picture]
From:freeborn
Date:November 15th, 2014 01:18 am (UTC)
(Link)
а, забыл мантиссу на 10 разделить
(Reply) (Parent) (Thread)
[User Picture]
From:yatur
Date:November 15th, 2014 03:15 am (UTC)
(Link)
Ну, скажем такая идея:

1. Представляем аргумент в виде десятичной дроби.
2. Если десятичная дробь получилась бесконечная, то f(x)=42.
3. Если десятичная дробь конечная (т.е. x = n*10k для некоего целого 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

Edited at 2014-11-15 03:17 am (UTC)
(Reply) (Thread)
[User Picture]
From:spamsink
Date:November 15th, 2014 03:17 am (UTC)
(Link)
Как доказать, что на любом интервале найдется любое значение?
(Reply) (Parent) (Thread) (Expand)
[User Picture]
From:kcmamu
Date:November 15th, 2014 03:22 am (UTC)
(Link)
Возьмем 5-ричную бесконечную запись дробной части аргумента и "исполним" ее как программу в таком языке:

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

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

Их выходом объявим число, бесконечная двоичная запись которого напечатается. Выходом некорректной программы объявим, скажем, ноль.
(Reply) (Thread)
[User Picture]
From:spamsink
Date:November 15th, 2014 03:27 am (UTC)
(Link)
Заскриню.
(Reply) (Parent) (Thread) (Expand)
[User Picture]
From:ygam
Date:November 15th, 2014 03:26 am (UTC)
(Link)
записать 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, вызванные началом числа, потом можно переписать.

Так как в любом интервале есть двоичные числа с общим началом и произвольным концом, эта функция действительно возвращает все возможные действительные числа.
(Reply) (Thread)
[User Picture]
From:spamsink
Date:November 15th, 2014 03:31 am (UTC)
(Link)
Способ годный, но бешеный. :) Заскриню.
(Reply) (Parent) (Thread)
[User Picture]
From:sab123
Date:November 15th, 2014 06:33 am (UTC)
(Link)
Скажем, берем X в десятичном представлении и делаем Y равным числу цифер в нем после десятичной точки, необходимых для точной записи числа (т.е. отбросив все нули на хвосте). А, и еще знак определять по четности/нечетности этого количества цифер.

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

Edited at 2014-11-15 06:38 am (UTC)
(Reply) (Thread)
[User Picture]
From:galkao
Date:November 15th, 2014 06:36 am (UTC)
(Link)
"Черный квадрат" никак не получится при такой постановке задачи. У функции ОДНОМУ значению аргумента соответствует ровно одно значение функции. Иначе это - не функция:-) То есть графиком функции всегда является линия (или ее кусочки). Но никогда не может быть нечто "объемное".
(Reply) (Thread)
[User Picture]
From:dluciv
Date:November 15th, 2014 06:59 am (UTC)
(Link)
Вы про другую функцию говорите. Требуется такая, которая принимает все значения на любом непустом интервале. Вы требование усилили, поэтому то, что под него подходит, перестало быть функцией.
(Reply) (Parent) (Thread) (Expand)
[User Picture]
From:dluciv
Date:November 15th, 2014 06:55 am (UTC)
(Link)
Предел функциональной последовательности. Не обязательно конечно, но так должно быть легче всего описать.

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

Либо адский хэш, как ниже в коментах было. Я не читал подробно, но расхожий способ — взять числа от 0 до 1, а потом из нечётных цифр составить аргументы, а из чётных соответствующие им значения. И для каждого из аргументов брать одно из значений по какому-нибудь выудуманному принципу, но чтобы размазывалось хорошо.
(Reply) (Thread)
[User Picture]
From:_guard_
Date:November 15th, 2014 06:58 am (UTC)
(Link)
+1 к пределу $n * sin(x / n)$
(Reply) (Parent) (Thread) (Expand)
[User Picture]
From:carla461
Date:November 15th, 2014 07:31 am (UTC)
(Link)
не конструктивный способ - взять любую биекцию между классами эквивалентности R/Q и R а потом расширить ее до функции R->R присвоив одинаковые значения на всех элемантах в каждом из классов
(Reply) (Thread)
[User Picture]
From:spamsink
Date:November 15th, 2014 07:36 am (UTC)
(Link)
Классы эквивалентности R/Q - это сильно неконструктивный способ. :) Но идея построения в чем-то схожая.
(Reply) (Parent) (Thread)
[User Picture]
From:mikev
Date:November 15th, 2014 08:59 am (UTC)
(Link)
Возьмем двоичную запись дробной части числа и разобьем ее на последовательные группы из 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)=предел ряда.
(Reply) (Thread)
[User Picture]
From:spamsink
Date:November 15th, 2014 09:12 am (UTC)
(Link)
Как это будет работать для произвольно малых интервалов?
(Reply) (Parent) (Thread) (Expand)
[User Picture]
From:freeborn
Date:November 15th, 2014 09:59 am (UTC)
(Link)
Все вещественные, или хватит и рациональных?
(Reply) (Thread)
[User Picture]
From:spamsink
Date:November 15th, 2014 03:29 pm (UTC)
(Link)
Все вещественные.
(Reply) (Parent) (Thread)