Еще однв прикольная задачка заданная на интервью

Arto · Post by **Arto** » 07 Dec 2001 22:26

Есть квадрат 1*1.Проводим диагональ/гипотенузу.
как известно она по известной теореме [img:6475f3f458]images/smiles/icon_wink.gif[/img:6475f3f458] =SQRT(2)
Обозначим треугольник ABC (Т.е AC=SQRT(2))
теперь попробуем от A до С дойти не по гипотенузе a а двигаясь в горизонтальнои и вертикальном направлении (см рисунок)
_
_| |
_| |
_| |
_| |
_|_________|
какой би длини не били горизонтальние и вертикальние отрезки сумарная длина от пунтка А до B получается 2.....
вопрос Как доказать что при уменьшении длини отрезков до 0 малого длина будет SQRT(2)??

Arto · Post by **Arto** » 07 Dec 2001 22:32

[b:22d434b673]какой би длини не били горизонтальние и вертикальние отрезки сумарная длина от пунтка А до B получается 2.....[/b:22d434b673]
Sorry, До пункта С а не B
и рисунок не получился [img:22d434b673]images/smiles/icon_sad.gif[/img:22d434b673] ((
Идея рисунка двигаться шаг в горизонтальном направлиении шаг в вертикальном- в постом слечае 1/2 в горизонтальном 1/2 в вертикальном и снова 1/2 в горизонтальном 1/2
потом уменьшать шаги до 0 малого

Kisena · Post by **Kisena** » 07 Dec 2001 22:51

<blockquote>quote:<hr>
Как доказать что при уменьшении длини отрезков до 0 малого длина будет SQRT(2)??
<hr></blockquote>
Насколько мы поняли, пример, собственно, призван продемонстрировать, что этого не происходит. Поверните гипотенузу горизонтально. Тогда Ваши лесенки будут графиками определенных функций. На пространстве этих функций определен функционал - "длина графика".

Если у Вас уже отвалилась башка [img:4ec0a5dcaa]images/smiles/icon_smile.gif[/img:4ec0a5dcaa] , то ничем помочь не можем - для остальных именно сейчас только начинаются тонкости. [img:4ec0a5dcaa]images/smiles/icon_smile.gif[/img:4ec0a5dcaa] "Парадокс" в том, что на первый взгляд кажется, что лесенки "приближаются" к гиптенузе, а у "близких" функций должна быть "близкая" длина графика. Что такое "близкие" длины более-менее понятно - два числа близки, если расстояние между ними (модуль разности) маленькое. А вот что такое "близкие" функции? Берем две функции - как мерять расстояние между ними? Существует куча способов, и важно, что они неэквивалентные. В одном смысле функции могут быть близки, а в другом далеки. В одном смысле они могут сходиться, а в другом расходиться. Далее, понятие непрерывности, если Вы внимательно посмотрите на определение, зависит от того, как Вы меряете расстояние. Т.е. один и тот же функционал может быть непрерывным в одном смысле, и не быть таким в другом смысле.

Функционал "длина графика" не непрерывен, если растояние между функциями мерять "очевидным способом", т.е. смотреть на максимум разницы. Отсюда и возможность таких эффектов. Если же, например, смотреть не только на максимум расстояния между функциями, но и на максимум расстояния между производными, то "длина графика" становится непрерывным функционалом, НО приведенная последовательность лесенок уже не "приближается" к гипотенузе *в этом другом смысле*, так что противоречия опять нет.

В общем, Колмогоров, Фомин... ну и дальше более продвинутые книжки. [img:4ec0a5dcaa]images/smiles/icon_smile.gif[/img:4ec0a5dcaa]

[ 07-12-2001: Message edited by: Kisena ]

[ 07-12-2001: Message edited by: Kisena ]

Joker · Post by **Joker** » 07 Dec 2001 23:03

А что, красиво [img:fa6647a9d7]images/smiles/icon_smile.gif[/img:fa6647a9d7]
Предельный переход по длине здесь не работает - иначе говоря, уменьшая длину шагов, вы не получите длину результирующего пути равной длине диагонали, - первая всегда будет равна 2. Вот если вы посчитаете площадь под этим ступенчатым путем, тут другое дело, - эта площадь будет стремиться к 1/2 и в пределе в нее перейдет (т.к. lim (1/n^2 + 2/n^2 + ... + n/n^2) = 1/2. Получится не что иное, как верхняя интегральная сумма Дарбу, которую все учили в детском саду [img:fa6647a9d7]images/smiles/icon_smile.gif[/img:fa6647a9d7] . Там площадь и здесь площадь, мера одинаковая. А с длиной это не получится, ибо [b:fa6647a9d7]меры[/b:fa6647a9d7] получающихся объектов разные.
На самом деле это весьма сложно понять. Приведу классический пример.
Представьте равносторонний треугольник. Теперь на каждой стороне треугольника "выбросим" центральную треть, заменив ее двумя сторонами построенного на этой трети (в "выпуклую" сторону) меньшего треугольника. Получится звезда Давида. Теперь проделаем то же самое с ее сторонами, и т.д. Нетрудно сообразить, что на каждом шаге длина каждой стороны увеличивается в 4/3 раза, и в итоге периметр получающегося объекта стремится к бесконечности. Однако же площадь того же объекта конечна, хотя бы потому, что он весь находится внутри окружности, описывающей исходный треугольник. Получается, что объект конечной площади имеет, однако, бесконечный периметр.
Секрет, как и в Вашей задаче, в том, что линия, получающаяся в итоге, это уже не линия, но еще и не площадь. "Размерность" получающегося объекта есть 4/3, что больше 1, но меньше 2. "Длину" такого объекта (собственно, это и не длина уже) логично выражать не в метрах, а в метрах в степени 4/3, как бы парадоксально это ни звучало.
Ключевые слова для тех, кто заинтересовался, — "множество Мандельброта".

Kisena · Post by **Kisena** » 07 Dec 2001 23:13

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

Правда, нас все еще гложут сомнения. Что же все-таки требовалось "[i:9f0ba161b3]доказать[/i:9f0ba161b3]"? И где такие работы, где на интервью спрашивают такие задачи?

Joker · Post by **Joker** » 07 Dec 2001 23:29

<blockquote>quote:<hr>Originally posted by Kisena:
[i:9af791620d]Ага, фракталы - это тоже вещь. Правда, тут мы почти ни в зуб ногой, так что функциональный анализ нам ближе и понятнее.[/i:9af791620d]<hr></blockquote>И еще какая вещь! [img:9af791620d]images/smiles/icon_smile.gif[/img:9af791620d]
Но на самом деле, эту задачку можно решить с помощью практически любого раздела математики [img:9af791620d]images/smiles/icon_smile.gif[/img:9af791620d] Вот вам решение на языке матанализа, если кто боится функционального анализа или теории фракталов [img:9af791620d]images/smiles/icon_smile.gif[/img:9af791620d]
Длина графика любой функции есть криволинейный интеграл по мере вдоль этой функции. Так вот, начальная и конечная точка обоих интегралов одинакова, но вот мера интегрирования разная. Поскольку у "зубчатого" графика, как нетрудно понять хотя бы из моей аналогии с фракталом, мера в SQRT(2) раз больше, то и итоговая длина, естественно, получается в SQRT(2) раз больше. То есть, не SQRT(2), а 2.
L1 = 2 = Int(dl1) = Int(SQRT(2)dl2) = SQRT(2) Int(dl2) = SQRT(2) L2.
(здесь L1 - длина ступенчатой линии, L2 - длина диагонали).

Kisena · Post by **Kisena** » 07 Dec 2001 23:42

<blockquote>quote:<hr>Originally posted by Joker:

Длина графика любой функции есть криволинейный интеграл по мере вдоль этой функции. Так вот, начальная и конечная точка обоих интегралов одинакова, но вот мера интегрирования разная. Поскольку у "зубчатого" графика, как нетрудно понять хотя бы из моей аналогии с фракталом, мера в SQRT(2) раз больше, то и итоговая длина, естественно, получается в SQRT(2) раз больше. То есть, не SQRT(2), а 2.
L1 = 2 = Int(dl1) = Int(SQRT(2)dl2) = SQRT(2) Int(dl2) = SQRT(2) L2.
(здесь L1 - длина ступенчатой линии, L2 - длина диагонали).<hr></blockquote>

Как говорят у нас на Каролинщине: "I hate to be an asshole but..."

Последовательность такая:

Мера -> интеграл. Не наоборот. Как объяснение "на пальцах" Ваше последнее решение вполне годится. Но если Вы все напишете аккуратно, то все сведется либо к описанному нами решению, либо мы не знаем, что Вы имеете в виду. Смысл слов "мера графика" нам представляется расплывчатым.

Joker · Post by **Joker** » 07 Dec 2001 23:51

<blockquote>quote:<hr>Originally posted by Kisena:
[i:9251a59180]Мера -> интеграл. Не наоборот. Как объяснение "на пальцах" Ваше последнее решение вполне годится. Но если Вы все напишете аккуратно, то все сведется либо к описанному нами решению, либо мы не знаем, что Вы имеете в виду.[/i:9251a59180]<hr></blockquote>Вот именно это я и имею в виду. Решение "на пальцах", для тех, кто боится функанализа. Ежу понятно, что все решения по своей сути одинаковы и сводятся к одному и тому же [img:9251a59180]images/smiles/icon_smile.gif[/img:9251a59180] даже на Каролинщине [img:9251a59180]images/smiles/icon_smile.gif[/img:9251a59180]

Arto · Post by **Arto** » 08 Dec 2001 00:57

[b:d4c62af574]Правда, нас все еще гложут сомнения. Что же все-таки требовалось "доказать"? И где такие работы, где на интервью спрашивают такие задачи? [/b:d4c62af574]
Требовальсь даказать что нет парадокса....при уменьшении длини отрезка работает теорема Пифагора...т.е =SQRT(2)
Задачу предложил выпускник Принстона (увидев что у меня тоже физико-математическое образование)...хотя сказал что ответа не знает просто ему типа заинтересовало ето когда от ходил по городу (хотел по гипотенузе и получалось так что обходил дома etc. вот и возникла задача)
Не знаю из чистого любопытства задал или притворился типа невзначай типа ни в чем не бывало и в общем-то ради прикола или еще чего...

Вообщем мне очень понравились решения Джокера!
Но вот еще одно решение.
[b:d4c62af574]Предельный переход по длине здесь не работает - иначе говоря, уменьшая длину шагов, вы не получите длину результирующего пути равной длине диагонали, - первая всегда будет равна 2[/b:d4c62af574]
Только вот Я решил именно этим способом [img:d4c62af574]images/smiles/icon_wink.gif[/img:d4c62af574]
Я взял и в лоб по честному расписал формулы.
решение:
Берем для маленького квадрата S=SQRT(deltaX^2+deltaX^2)
для всей прямой длина AC= SUM (lim S ) where deltax->0
AC=SQRT(2)*lim(SUM(deltaX)) where deltaX->0
lim(Sum) равно 1 т.к длина равна 1
AC=SQRT(2) В предельном переходе.

Joker · Post by **Joker** » 08 Dec 2001 01:28

[img:68373a5edc]images/smiles/icon_smile.gif[/img:68373a5edc] Вы доказали, что если идти пома-а-аленьким кусочкам гипотенузы, то в конце концов пройдешь по всей гипотенузе [img:68373a5edc]images/smiles/icon_smile.gif[/img:68373a5edc] Это действительно так, только при чем тут Ваш же вопрос о "ступенчатом" пути?

Первая формула в Вашем решении должна выглядеть так:
S=deltaX+deltaX (путь по "ступенькам")
Тогда (цитирую) для всей прямой длина AC= lim (SUM S) where deltaX->0
AC=2*lim(SUM(deltaX)) where deltaX->0
lim(Sum) равно 1 т.к длина равна 1
AC=2 В предельном переходе.

[img:68373a5edc]images/smiles/icon_wink.gif[/img:68373a5edc]

[ 07-12-2001: Message edited by: Joker ]

Arto · Post by **Arto** » 08 Dec 2001 03:10

<blockquote>quote:<hr>Originally posted by Joker:
 [img:7118e7db6b]images/smiles/icon_smile.gif[/img:7118e7db6b] Вы доказали, что если идти пома-а-аленьким кусочкам гипотенузы, то в конце концов пройдешь по всей гипотенузе [img:7118e7db6b]images/smiles/icon_smile.gif[/img:7118e7db6b] Это действительно так, только при чем тут Ваш же вопрос о "ступенчатом" пути?

Первая формула в Вашем решении должна выглядеть так:
S=deltaX+deltaX (путь по "ступенькам")
Тогда (цитирую) для всей прямой длина AC= lim (SUM S) where deltaX->0
AC=2*lim(SUM(deltaX)) where deltaX->0
lim(Sum) равно 1 т.к длина равна 1
AC=2 В предельном переходе.

[img:7118e7db6b]images/smiles/icon_wink.gif[/img:7118e7db6b]

[ 07-12-2001: Message edited by: Joker ]<hr></blockquote>

[img:7118e7db6b]images/smiles/icon_eek.gif[/img:7118e7db6b] [img:7118e7db6b]images/smiles/icon_biggrin.gif[/img:7118e7db6b]
Т.е АС=2, а не SQRT(2)??
тогда полагаясь на Ваше цитирование либо теорема пифагора не верна либо в моем решении есть неправильные рассуждения??
(не будете ли вы так добры указать ошибки в решении)?
Или может я неправильно формулирую задачу?
Задача не о ступенчатой фуикции а о том как показать математически что никакого кажущегося парадокса нету между тем что идешь по гипотенузе или по ступенчатым функциям когда шаг стреминся к 0. Естественно логически и по здравома смыслу видно что ктогда шаг->0 Ступенчатая функция превращается в прямую...но с другой стороны врожде когда чуть отлияается от 0 длина "кривой=ступенчатой функции" = 2..так надо показать что в пределе все становится на свои места....

Joker · Post by **Joker** » 08 Dec 2001 03:32

Сорри [img:f98c0239d5]images/smiles/icon_smile.gif[/img:f98c0239d5]
У меня ощущение, что Вы не поняли ничего из написанного мной и Kisena. Sorry. Попробуйте прочитать еще раз.
Путь по ступенчатой линии всегда равен 2, независимо от "длины" ступенек. Путь по гипотенузе всегда равен SQRT(2). Никакого парадокса тут нет. "Предельный переход" для ступенчатого пути НЕ превращает его в путь по гипотенузе (как, может быть, кажется), а превращает в путь по некоторой линии, которая, строго говоря, и линией-то не является, а является объектом более высокой размерности. Мера вдоль этой "линии" больше, чем мера вдоль гипотенузы, в SQRT(2) раз, поэтому и длина соответствующего пути тоже в SQRT(2) раз больше.

Kisena · Post by **Kisena** » 08 Dec 2001 03:55

Если это выпускник математической специальности Принстона, то Принстон должен провалиться со стыда. Нет, задача не тривиальная для неспециалиста, но *для математика* это основы.

-ЭР- · Post by **-ЭР-** » 08 Dec 2001 04:56

Так, фантазия на тему. Пусть ступенька складывается из вертикального a и горизонтального b. Тогда длина пути по ступеньке всегда будет SUM(a(i) + b(i)) { i = 0 : N }. Длина по гепотенузе будет SUM(SQRT(a(i)^2 + b(i)^2)). Если a(i) = b(i) = a, то длина по гепотенузе = N*a*1.41, длина по ступеньке N*a*2. Ни при каких угодно малых a и каких угодно больших N эти длины не будут равны.

Так вот, собственно фантазия: пусть ступенька видоизменяется с уменьшением a и b. Например, пусть косинус угла между a и b меняется как (a + b - 1) { a < 1/2, b < 1/2). Вот тогда все, вроде, получается гладко и по-мему наглядно. А может и нет. Не знаю [img:6afc997171]images/smiles/icon_smile.gif[/img:6afc997171]

DV · Post by DV » 08 Dec 2001 05:02

<blockquote>quote:<hr>Originally posted by Joker:
...Представьте равносторонний треугольник. Теперь на каждой стороне треугольника "выбросим" центральную треть, заменив ее двумя сторонами построенного на этой трети (в "выпуклую" сторону) меньшего треугольника. Получится звезда Давида. Теперь проделаем то же самое с ее сторонами, и т.д. ..."Размерность" получающегося объекта есть 4/3, что больше 1, но меньше 2. ...<hr></blockquote>

The fractal dimension of this object is ln(4)/ln(3) = 1.26.

DV · Post by DV » 08 Dec 2001 05:08

<blockquote>quote:<hr>Originally posted by Joker:
Сорри [img:0d7b0b390c]images/smiles/icon_smile.gif[/img:0d7b0b390c]
У меня ощущение, что Вы не поняли ничего из написанного мной и Kisena. Sorry. Попробуйте прочитать еще раз.
Путь по ступенчатой линии всегда равен 2, независимо от "длины" ступенек. Путь по гипотенузе всегда равен SQRT(2). Никакого парадокса тут нет. "Предельный переход" для ступенчатого пути НЕ превращает его в путь по гипотенузе (как, может быть, кажется), а превращает в путь по некоторой линии, которая, строго говоря, и линией-то не является, а является объектом более высокой размерности.. Мера вдоль этой "линии" больше, чем мера вдоль гипотенузы, в SQRT(2) раз, поэтому и длина соответствующего пути тоже в SQRT(2) раз больше<hr></blockquote>

I disagree. If I am not mistaken, the fractal dimension of this object is 1. A straight line also has a fractal dimension of 1.

Kisena · Post by **Kisena** » 08 Dec 2001 05:11

<blockquote>quote:<hr>Originally posted by -ЭР-:
Так, фантазия на тему. Пусть ступенька складывается из вертикального a и горизонтального b. Тогда длина пути по ступеньке всегда будет SUM(a(i) + b(i)) { i = 0 : N }. Длина по гепотенузе будет SUM(SQRT(a(i)^2 + b(i)^2)). Если a(i) = b(i) = a, то длина по гепотенузе = N*a*1.41, длина по ступеньке N*a*2. Ни при каких угодно малых a и каких угодно больших N эти длины не будут равны.

Так вот, собственно фантазия: пусть ступенька видоизменяется с уменьшением a и b. Например, пусть косинус угла между a и b меняется как (a + b - 1) { a < 1/2, b < 1/2). Вот тогда все, вроде, получается гладко и по-мему наглядно. А может и нет. Не знаю [img:dff44d369d]images/smiles/icon_smile.gif[/img:dff44d369d] <hr></blockquote>

Подойдет любая последовательность такая, что сами функции стремятся к нулю [b:dff44d369d]и[/b:dff44d369d] их производные стремятся к нулю.

DV · Post by DV » 08 Dec 2001 05:27

The fractal dimension is the Hausdorff Besicovich dimension, if anybody wonders what I meant by it.

Kisena · Post by **Kisena** » 08 Dec 2001 06:16

Что касается нас, то как уже было сказано, мы с фракталами не знакомы, хотя про их существование слышали. Но исключительно на уровне "бывают дробные размерности".

Что же до основ функционального анализа, то в своих знаниях [i:38af0dcdfa]его основ[/i:38af0dcdfa] мы более-менее уверены. Хотя от ошибок, конечно, как и все не застрахованы.

Dmitry67 · Post by **Dmitry67** » 08 Dec 2001 06:23

Множество Мандельброта, eh ?
А вот вам еще интересное множество
Придумал сам, потом правда узнал что не первый...

Рассмотрим множество вещественных числел, определяемых строками ASCII

Например,
1
3.67899
(34*566)/45
LIM(n->INF,(1+1/n)^n)
Min root of (X^45+3*X^44+66.77*X^23+45=0)

итд
Договоримся что если строка корректно определяет единственное вещественное число, То все OK, как бы сложно это не вычислялось

Множество строк счетно
Множество вещественных числен нет
Вычтем из множества вещественных чисел множество чисел, определенных строками

Получилось очень интересное множество
Оно бесконечно и даже несчетно.
Но НИ ОДНОГО ПРИМЕРА числа из этого множества привести нельзя
Потому что любой пример определяется строками
и по опредедлению не содержится в этом множестве

DV · Post by DV » 08 Dec 2001 06:38

<blockquote>quote:<hr>Originally posted by Kisena:
Что касается нас, то как уже было сказано, мы с фракталами не знакомы, хотя про их существование слышали. Но исключительно на уровне "бывают дробные размерности".

Что же до основ функционального анализа, то в своих знаниях [i:6c78798056]его основ[/i:6c78798056] мы более-менее уверены. Хотя от ошибок, конечно, как и все не застрахованы.<hr></blockquote>

Да я согласен и с Вашим ответом, и с ответом Jokerа. Вот только с размерностями он в спешке напутал. Как для знежинки, так и для лесенки.

Olegus · Post by **Olegus** » 08 Dec 2001 06:40

<blockquote>quote:<hr>Originally posted by Dmitry67:
А вот вам еще интересное множество
<hr></blockquote>

Интересно. Проэкция мира вещественных чисел на мир целых.Как бы убрали одно измерение. А-ля Мебиус.

Kisena · Post by **Kisena** » 08 Dec 2001 06:54

Хмммм... Не очевидно, что пример полностью корректен.

Допустим, что такое множество, действительно, корректно определено. Оно несчетно, т.е. существует биекция на него из отрезка [0,1]. Назовем ее "функция Кисены": k(x), x из [0,1].

Что Вы думаете про число, задаваемое строкой, "k(0)"?

Joker · Post by **Joker** » 08 Dec 2001 07:06

<blockquote>quote:<hr>Originally posted by DV:
[i:c5d6dd6a49]Да я согласен и с Вашим ответом, и с ответом Jokerа. Вот только с размерностями он в спешке напутал. Как для знежинки, так и для лесенки.[/i:c5d6dd6a49]<hr></blockquote>Совершенно верно, я в спешке забыл про логарифмы [img:c5d6dd6a49]images/smiles/icon_smile.gif[/img:c5d6dd6a49] размерность все-таки не вычисляется как коэффициент приращения длины в каждой итерации, хотя на нем и базируется [img:c5d6dd6a49]images/smiles/icon_smile.gif[/img:c5d6dd6a49]
Спасибо за поправку!

Joker · Post by **Joker** » 08 Dec 2001 07:16

<blockquote>quote:<hr>Originally posted by Dmitry67:
[i:f0b5e00922]А вот вам еще интересное множество
Придумал сам, потом правда узнал что не первый...
Рассмотрим множество вещественных числел, определяемых строками ASCII
Договоримся что если строка корректно определяет единственное вещественное число, То все OK, как бы сложно это не вычислялось
Множество строк счетно
Множество вещественных числен нет
Вычтем из множества вещественных чисел множество чисел, определенных строками
Получилось очень интересное множество
Оно бесконечно и даже несчетно.
Но НИ ОДНОГО ПРИМЕРА числа из этого множества привести нельзя
Потому что любой пример определяется строками
и по опредедлению не содержится в этом множестве[/i:f0b5e00922]<hr></blockquote>А зачем так сложно?
Давайте возьмем множество вещественных чисел (несчетное) и вычтем множество рациональных чисел (счетное, насколько я помню, но пусть меня опять поправят, если что не так [img:f0b5e00922]images/smiles/icon_smile.gif[/img:f0b5e00922] ) Получится множество иррациональных чисел, несчетное и удовлетворяющее всем пожеланиям Дмитрия №67 - в рамках стандартных знаков арифметических действий и скобок ни одно из них выразить нельзя. Ну и что?