6 мар. 2012 г.

Теорема Пифагора

Добрый день.

В прошлой заметке (о расширениях теорий) были упомянуты «обобщения на пространства больших размерностей», что вызвало неожиданный интерес, приведший к занимательной переписке. Сейчас мне кажется, что один из моих ответов стоит опубликовать.

Это старинная задачка, позволяющая почувствовать, что в n-мерных пространствах (для n больших 3) не всё работает столь же привычно, как при переходах от прямых к плоскостям и от плоскостей к пространствам. Эти аналогии мы знаем давно, поэтому привыкли считать всё красивым и естественным (каковым оно и является), но нередко напрасно надеемся, что и при дальнейшем увеличении размерности интуиция нам поможет.

Ещё эта задачка бывает хороша на собеседованиях (естественно, многое зависит от специфики отбора), так как позволяет за короткое время услышать много разных идей... Но об этом позже. А сначала давайте вспомним теорему Пифагора. Она нам позволяет вычислить гипотенузу прямоугольного треугольника, зная его катеты, что можно использовать, например, для вычисления длины диагонали прямоугольника. А как теперь вычислить длину диагонали прямоугольного параллелепипеда (со сторонами a, b и c)? Правильно, сначала применить теорему пифагора для одной из граней — так мы найдём длину её диагонали d = sqrt(a^2 + b^2). А уже потом вычислить длину искомой большой диагонали sqrt(d^2 + c^2) = sqrt(sqrt(a^2 + b^2)^2 + c^2) = sqrt(a^2 + b^2 + c^2).

Сейчас мы не будем говорить о том, что таким элементарным путём мы пришли к определению евклидового расстояния, а лишь заметим неограниченность этого подхода. В n-мерном пространстве мы можем найти расстояние между двумя точками, n-1 раз воспользовавшись теоремой Пифагора. Естественно, обычно так никто не делает , потому что глупо считать квадратный корень, а потом сразу же возводить результат в квадрат. Но важно понимать, откуда возникла странная формула расстояния между точками d(A, B) = sqrt((A1-B1)^2 + (A2-B2)^2 + ... + (An-Bn)^2). Сейчас, скорее всего, мы это неплохо понимаем.

Теперь переходим к задаче, а заодно пользуемся возможностью поучаствовать в создании этой заметки (подробности будут в квадратных скобках ниже). Начать этот разговор проще всего с двумерного пространства. Представьте себе квадрат со стороной 2. Его можно разбить на четыре квадрата 1x1, в каждый из которых легко вписать окружность диаметра 1. Давайте найдём величину D2 (диаметр окружности, вписанной между этими четырьмя окружностями).

Если в большом квадрате, разделенном на маленькие, провести диагональ, то увидим, что искомый диаметр D2 состоит из двух равных половинок. Каждая половинка — это расстояние от угла маленького квадрата до окружности, которая в этот квадрат вписана. И такая же половинка находится с другой стороны окружности в этом же квадрате. Получается, что искомый диаметр равен диагонали маленького квадрата минус диаметр окружности. Т.е. D2 = sqrt(2) - 1. [Спасибо KYegres за это объяснение (в комментариях есть ещё несколько решений этой задачи)]

Отлично, так мы нашли D2. Теперь давайте рассмотрим трёхмерный случай. Представьте себе куб со стороной 2. Его можно разбить на восемь кубов 1x1x1, в каждый из которых легко вписать сферу диаметра 1. Давайте найдём величину D3 (диаметр сферы, вписанной между этими восемью сферами).

Расстояние между центрами сфер, лежащих на большой диагонали куба, равно sqrt(3), а радиус каждой из этих сфер равен 1/2. Получается, между центрами этих сфер есть только они сами и вписанная сфера => D3 = sqrt(3)-1/2-1/2 = sqrt(3)-1. [спасибо анонимному комментатору за это решение]

Прекрасно, теперь мы нашли D3. А теперь давайте зададимся вопросом: к какой величине будет стремиться значение Dn при росте n? Или по-русски: к чему приближается диаметр сферы, вписанной между единичных сфер, прижатых к углам n-мерного куба со стороной 2?

Что такое сфера в n-мерном пространстве? Это множество n-мерных точек, удалённых от центра сферы на одинаковое расстояние. Так как расстояние мы считать умеем, то и с множеством таких точек работать можем. С n-мерными кубами ещё проще, так как там даже корни с квадратами считать не надо, а всё прямо задаётся неравенствами.

Давайте попробуем найти D9 и D16 (диаметры вписанной окружности для случаев девятимерного и шестнадцатимерного пространств). Достаточно посмотреть на одну из главных диагоналей n-мерного куба. Ее длина 2*sqrt(n), центр искомой сферы лежит прямо посередине неё, центры двух вписанных в куб сфер лежат на ней, точки касания искомой сферы и сфер, вписанных в куб лежат тоже на ней (строго не готов доказать, но визуально достаточно очевидно и из всяческой симметрии вроде бы должно получиться). Теперь смотрим на половинку этой диагонали. Расстояние от ее конца, являющегося углом куба, до центра вписанной в куб сферы — sqrt(n)/2 (ровно четверть всей диагонали), радиус вписанной в куб сферы 1/2, в итоге радиус искомой сферы (sqrt(n)-1)/2, а диаметр — sqrt(n)-1 [Спасибо Eyeless за это описание].

Подставим 9 и 16 в найденную формулу:
- D9 = sqrt(9) - 1 = 3 - 1 = 2,
- D16 = sqrt(16) - 1 = 4 - 1 = 3.
Получается, что диаметр сферы, зажатой между сфер, вписанных в углы куба, совпадает со стороной этого куба (или даже выходит за его пределы). «Немного» странно, верно?

Как же так? Да, выглядит странно. А теперь надо понять, кто нас обманул: Пифагор, интуиция или ещё кто-то? :) Приглашаю в комментарии обсудить детали этого безобразия.

[Благодарю Arthur Baraov за очень подробные рассуждения по поводу этой задачи]

Хорошего вечера!

69 комментариев:

  1. Анонимный06.03.2012, 17:29

    С первым все понятно. В силу симметрии:
    (D2)/2 = (1/2)*sqrt(2) - 1/2
    D2 = sqrt(2) - 1

    А вот с кубом странно сформулировано... Возможно имелись ввиду сферы и кубы, а не квадраты и окружности?

    ОтветитьУдалить
    Ответы
    1. Уважаемый аноним, спасибо, что поправили опечатку.
      Я пока не могу вставить Ваш способ вычисления D2, так как он слишком краток (т.е. его будет трудно понять тем, кто не решил задачу самостоятельно).

      Удалить
    2. Анонимный06.03.2012, 17:53

      Можете и не размещать. Хотя вроде бы очевидно и красиво:
      (D3)/2 = (1/2)*sqrt(3) - 1/2
      D3 = sqrt(3) - 1

      Удалить
    3. Уважаемый аноним, в Ваших словах слышна обида :(
      Вы можете чуть подробнее написать, почему это равенство очевидно?

      Удалить
    4. Анонимный06.03.2012, 18:19

      Извините:( Я не специально. Никаких обид! Честно!
      А вот понятно объяснить... сложно...

      Все разбиения в текущей задаче симметричны относительно геометрических центров квадрата и куба. Соответственно, там и должен располагаться центр окружности/сферы.
      Что бы не путаться возьмем квадрат:
      Если соединить центр квадрата с центром окружности, то мы получим отрезок длинной в сумму радиусов этой окружности и искомой.
      Дальше простая геометрия...

      Проблема в том, что у для 4-х мерного пространства эти рассуждения не обязаны быть применимы(

      Удалить
    5. Спасибо! Я думаю, многим Ваше объяснение будет понятнее, чем представленные ниже. Но ради краткости в текст заметки я включил другое.

      Удалить
  2. Анонимный06.03.2012, 17:46

    Расстояние между центрами окружностей, лежащих на диагонали квадрата, равно sqrt(2), а радиус каждой из этой окружностей равен 1/2. Получается, между центрами этих окружностей есть только они сами и вписанная окружность => D2 = sqrt(2)-1/2-1/2 = sqrt(2)-1.

    ОтветитьУдалить
    Ответы
    1. Уважаемый аноним, благодарю за краткое пояснение!

      Удалить
    2. Анонимный07.03.2012, 10:46

      Расстояние между центрами сфер, лежащих на большой диагонали куба, равно sqrt(3), а радиус каждой из этих сфер равен 1/2. Получается, между центрами этих сфер есть только они сами и вписанная сфера => D3 = sqrt(3)-1/2-1/2 = sqrt(3)-1.

      Удалить
    3. Уважаемый аноним, благодарю за настойчивость. Ваше объяснение включено в текст заметки.

      Удалить
  3. Мда, действительно, пока не могу понять как же так получается с D9 и D16? Похоже, метод индукции применил некорректно.
    Додумываю.
    Спасибо за подобную пищу для размышлений.

    ОтветитьУдалить
  4. При n=2. Если в большом квадрате, разделенном на маленькие, провести диагональ, то увидим, что искомый диаметр состоит из двух равных половинок. Каждая половинка - это расстояние от угла маленького квадрата до окружности, которая в этот квадрат вписана. И такая же половинка находится с другой стороны окружности в этом же квадрате. Получается, что искомый диаметр равен диагонали маленького квадрата минус диаметр окружности. Т.е. D2 = sqrt(2) - 1

    ОтветитьУдалить
    Ответы
    1. Спасибо, Ваше объяснение включено в текст заметки.

      Удалить
  5. Я могу определить n-мерную сферу, как геометрическое множество точек сумма квадратов расстояний от который до центра сферы равна квадрату радиуса.

    Я могу определить n-мерный куб, несколькими способами (но пока еще не знаю как правильно).

    А вот как определить, что эта сфера вписана в этот конкретный куб?

    ОтветитьУдалить
    Ответы
    1. Анонимный06.03.2012, 19:45

      n-мерный куб с центром в точке 0 и стороной 2 задаётся как множество всех таких точек (x1, x2, ... xn), для которых верны все следующие неравенства:
      -1 <= x1 <= 1,
      -1 <= x2 <= 1,
      ...
      -1 <= xn <= 1.

      А сфера полностью лежит в кубе, если все её точки удовлетворяют этой системе неравенств.

      Удалить
    2. Ну да, как-то так и задаётся куб, включая внутренность. Борис, а какие ещё естественные способы задать куб Вы видите?

      Удалить
    3. Один тот, что указал Анонимный пользователь.
      Второй векторный: Задать систему координат {x_i} из n-единичных и взаимноперпендикулярных векторов. Тогда куб - это множество точек заданных векторами вида sum(a_i*x_i) для всех возможных a_i в промежутке от -1 до 1.

      Фактически - это тоже самое.

      Но вопрос был в другом. Я, видимо, плохо сформулировал.
      Как быть с точками касания. Мы ведь считаем ищем радиус сферы, которая касается всех сфер, вписанных в n-мерные кубики. Именно вписаных, т.е. имеющих несколько точек касания....

      Я попытался пойти от классического определения с равенством производных до (n-1) порядка, но к ответу пока еще не пришел.

      Удалить
    4. Это не полное доказательство, но попытаюсь набрать...

      Разместим начало координат в центре симметрии куба. Из соображений симметри, мы можем утверждать, что эта точка будет центром искомой сферы. И ее будет описывать уравнение: sum((x_i)^2) = R^2.

      Раз эта сфера касается сферы sum((x_i - 1/2)^2) = 1/4.

      Пусть точка касания имеет координаты {m_i} в этой точке достигается равенство первых производных от этих двух функций. Т.е.
      Перепишем функции в виде:
      (x_0)^2 = R^2 - sum((x_i)^2, i!=0) {ну и вторую аналогично}.
      Отсюда следует, что
      - sum(2*m_i, i!=0)/(2*m_0) = - sum(2*(m_i - 1/2), i!=0)/(m_i - 1/2)
      Отсюда, m_0 = sum(m_i, i!=0)/(n - 1)

      Из полученного равенства и соображений симметрии следует, что
      m_0 = m_1 = m_2 = ... = m_n

      Что, вроде бы, логично.

      Теперь вспоминаем, что в точке касания одновременно выполняются оба равенства:
      sum((m_i)^2) = R^2 и sum((m_i - 1/2)^2) = 1/4

      Отсюда, учитывая, что 1/2>m_i>0 и m_0 = m_1 = m_2 = ... = m_n, получаем:
      m_0 = R/sqrt(n) = 1/2 - 1/[2*sqrt(n)]

      Отсюда, 2*R/sqrt(n) = 1 - 1/sqrt(n)
      D = 2*R = sqrt(n) - 1 --> +oo

      При этом, m_0 = 1/2 - 1/[2*sqrt(n)] --> 1/2

      Удалить
    5. Борис, я ещё несколько раз перечитал Ваше комментарий, но так и не понял его. Вы теперь разобрались (с учётом остальных комментариев)? Если нет, то, пожалуйста, напишите подробнее.

      Удалить
  6. По-моему, достаточно посмотреть на одну из главных диагоналей n-мерного куба. Ее длина 2sqrt(n), центр искомой сферы лежит прямо посередине нее, центры двух вписанных в куб сфер лежат на ней, точки касания искомой сферы и сфер, вписанных в куб лежат тоже на ней (строго не готов доказать, но визуально достаточно очевидно и из всяческой симметрии вроде бы должно получиться).
    Теперь смотрим на половинку этой диагонали. Расстояние от ее конца, являющегося углом куба до центра вписанной в куб сферы - sqrt(n)/2 (ровно четверть всей диагонали), радиус вписанной в куб сферы 1/2, в итоге радиус искомой сферы (sqrt(n)-1)/2, а диаметр - sqrt(n)-1.
    Сомнения тут примерно того же рода, из-за которых кажется странным, что у десятимерного яблока почти вся масса сосредоточена в кожуре.

    ОтветитьУдалить
  7. Анонимный06.03.2012, 20:18

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

    Мне попадалась задача на том же принципе и тоже с контринтуитивным ответом: «существует ли такое N, что шар размером с Землю целиком помещается в N-мерный куб с ребром 1 см?»

    (Что-то OpenID глючит. janatem.livejournal.com)

    ОтветитьУдалить
    Ответы
    1. Не очень понятно, каким размером может быть сравним с Землей n-мерный шар.

      Удалить
    2. Анонимный06.03.2012, 21:26

      Целиком помещается. Также же как (плоский) лист бумаги помещается в (трехмерном) ящике.

      Удалить
    3. Про шар размером с Землю: не совсем понятно, что именно имеется в виду.

      Шар, объем которого превышает объем земного шара можно разместить внутри n-мерного куба (в смысле, что существует такое n). Но диаметр такого шара не будет превышать длину ребра куба, т.е. 1 см.

      Удалить
    4. Анонимный06.03.2012, 21:37

      Имеется в виду трехмерный шар размером с Землю, помещенный в N-мерный куб.

      Удалить
    5. Анонимный06.03.2012, 21:46

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

      Удалить
    6. janatem, это отличный и очень ясный пример!

      Удалить
    7. Анонимный07.03.2012, 13:42

      По-моему пример не очень удачный, так как в нем предлагается в ТРЕХмерный куб поместить ДВУХмерный круг. В исходной же задаче требуется в N-мерный куб поместить N-мерную же сферу а не (N-1)-мерную. Непонятно как можно в N-мерный куб поместить N-мерную же сферу размерами больше куба? Хотя теоретически может и возможен вариант что в N-мерном пространстве гиперсфера будет выступать за размеры гиперкуба, но оставаться при этом вписанной в единичные гиперсферки.

      Удалить
    8. Этот пример плохой ещё и потому, что лист бумаги можно свернутьв трубочку. В отличие от Н-мерного шара в Н-мерном пространстве. ;)

      Удалить
  8. Наверно, для многомерного случая удобнее воспользоваться координатными методами.
    Зафиксируем понятия:

    1. n-гиперсфера, вписанная в n-гиперкуб -- это n-гиперсфера, центр которой равноудален от всех 2^n (n-1)-гиперплоскостей, в которых лежат "гиперграни" n-гиперкуба.
    В определении использовано понятие:

    2. Расстояние точки до n-гиперплоскости -- это длина перпендикуляра, опущенного из данной точки на эту n-гиперплоскость.
    В нашем случае перпендикуляры к "гиперграням" будут параллельны осям координат, и найти их длину будет просто.

    Ну, и ключевое понятие задачи: "сфера, вписанная между сфер". Ясно, что речь не идет о "сфере максимального диаметра, находящейся внутри данного тела", поскольку "вписываем" в несвязное множество, и по смыслу "вписанная" сфера находится снаружи от заданных сфер. Положим, что речь идет о сфере, внешне касающейся всех данных сфер.
    3. Сферы внешне касаются -- это такие сферы, у которых есть только одна общая точка, эта точка лежит на одной прямой с центрами этих двух сфер и между ними.
    Определение, конечно, избыточно, но загромождать решение доказательством нужных свойств (как и термином "n-гиперсфера") не хочется. Желающие могут доказать их исходя из единственности точки касания в качестве упражнения :).

    Дальнейшее -- дело техники.

    ОтветитьУдалить
  9. Дальнейшее -- дело техники.
    Зададим Систему координат: пусть одно точка гиперкуба имеет координаты (0, 0, ... 0), а диаметрально противоположенная - (2, 2, ... 2). Все ребра, очевидно, будут параллельны осям координат.
    Симметрия задачи подсказывает, что центр последней "вписанной" сферы находится в точке (1, 1, ... 1). Действительно, при проекции на любую плоскость, образованную любой парой координатных осей, искомый цент должен проецироваться в центр окружности из двумерного варианта задачи, то есть в (1, 1). Откуда следует, что все координаты этой точки равны 1.
    В силу той же симметрии нам достаточно рассмотреть отношение центральной сферы только с одной "угловой". Для простоты выберем сферу, вписанную в "гиперкубик" A(0, 0, ... 0) - B(1, 1, ... 1). Его гиперграни либо лежат на координатных гиперплоскостях, либо параллельны им и смещены на 1 вдоль перпендикулярной себе оси. То есть расстояние до ни от любой точки либо равно модулю определенной её координате t, либо равно abs(1-t). Легко убедится, что точка C(1/2, 1/2, ... 1/2) находится на равном расстоянии от всех гиперграней, поскольку все расстояния расстояния равня 1/2.
    То есть сфера с центром в точке C(1/2, 1/2, ... 1/2) и радиусом 1/2 будет вписана в данный "гиперкубик".
    Осталось рассмотреть отрезок CB, соединяющий центры двух сфер, и найти на нем точку касания M. По определению сферы, точка касания, как и любая точка сферы, находится на расстоянии радиуса от центра сферы. То есть расстояние C(1/2, 1/2, ... 1/2) - M равно 1/2. Ну а расстояние C(1/2, 1/2, ... 1/2) - B(1, 1, ... 1) легко вычислить: CB = sqrt( (1-1/2)^2 * n ) = sqrt(n)/2. Стало быть, расстояние M - B(1, 1, ... 1) равно:
    MB = CB - CM = sqrt(n)/2 - 1/2 = ( sqrt(n) - 1 )/2
    MB - это радиус искомой сферы, а диаметр d = 2*MB. То есть:

    d = sqrt(n) - 1


    Здесь не рассматривался вопрос существования такой "вписанной" сферы, но из решения можно получить алгоритм её построения, так что можно считать её существующей.

    При больших n расчетный диаметр превосходит дли ну ребра большого гиперкуба, например d(16) = 3. Это означает, что, вопреки нашей интуиции, построенная "вписанная" сфера выходит за границы большого гиперкуба. Но не выходит за границы описанной около гиперкуба сферы, сдесь наша интуиция работает.

    Лично я для тренировки интуиции для многомерных случаев представляю себе различные варианты визуализации многомерных объектов -- не тени, а динамические сечения и неортогональные проекции на трехмерное пространство. Внешне это чем-то похоже на деформации, иллюстрирующие сохранения топологических свойств. При этом форма и размер элементов чертежа могут существенно меняться, при сохранении их взаимодействия. В данном случае можно вариант проекции, когда образ центральной сферы вылезает за все грани образа куба, но не за углы (образы угловых сфер не пускают).

    ОтветитьУдалить
  10. Интересно, а мой первый комментарий (с началом решения) удален или сам как-то пропал?

    ОтветитьУдалить
    Ответы
    1. Vladimir, фильтры гугла углядели в том Вашем сообщении признаки спама (увы, иногда бывают ложные срабатывания), поэтому скрыли его (на всякий случай). Как только я его прочитал, так сразу разблокировал, поэтому сейчас все Ваши сообщения видны.

      Удалить
  11. d = sqrt(n) - 1

    А в том что в какой-то момент она станет больше стороны гиперкуба ничего парадоксального нету. Это уже обьяснил Vladimir.

    Чтобы лучше представить себе что он имеет в виду, можно попробовать уменьшать радиусы вписаных двумерных окружностей. Уже при размере 0,1 (точное значение не привожу), окружность выходит за пределы квадрата, но всё ещё выполняет условие касания ко вписаным окружностям.

    Приблизительно то же происходит с увеличением количества измерений:
    расстояние между центрами вписаных гипер-сфер будет увеличиваться (D = sqrt(n)).

    ОтветитьУдалить
  12. Вот они, масштабы многомерной трагедии
    http://www.wolframalpha.com/ подставьте сюда это - plot sqrt(x)-1, x=2 to 64

    ОтветитьУдалить
  13. Никакого недоразумения на самом деле нет. Просто с ростом размерности единичного куба его диагональ неограниченно возрастает. Вследствие этого описанная конструкция из шаров становится все более разреженной. Хоть шары продолжают касаться друг друга, "карманы" в углах кубов становятся настолько большими, что могут вместить шар, диаметр которого будет больше ребра куба. Разумеется, такой шар не поместится в куб, и его сегменты будут выступать наружу посередине каждой грани куба. Но никакого парадокса я в этом не вижу.

    ОтветитьУдалить
    Ответы
    1. Дмитрий К.08.03.2012, 13:25

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

      Удалить
  14. Вопрос: к какой величине будет стремиться значение Dn при росте n? Или по-русски: к чему приближается диаметр сферы, вписанной между единичных сфер, прижатых к углам n-мерного куба со стороной 2?

    Ответ: думаю, что значение Dn при росте n будет стремиться к 2.

    Кто нас обманул: Пифагор, интуиция или ещё кто-то?

    Ответ: ещё кто-то. Полагаю нетрудно догадаться как зовут этого "ещё кто-то" :)

    ОтветитьУдалить
    Ответы
    1. Спасибо за подробный текст ниже!
      Всех иногда подводит интуиция, но не все готовы обнаружить и признать свои ошибки.

      Удалить
  15. Поздравляю всех читательниц с женским праздником 8 Марта.

    ОтветитьУдалить
  16. Вот смежная задача, которая возможно заинтересует кого-то из читателей. Найти максимальный диаметр окружности, которую можно целиком разместить внутри куба со стороной 2. Или ее обобщение: Найти максимальный диаметр n-1-мерной сферы, которую можно целиком разместить внутри n-мерного куба со стороной 2.

    Для обобщенной задачи попробуйте хотя бы ответить на вопрос: стремится ли к бесконечности диаметр упомянутой n-1-мерной сферы при неограниченном росте n? А n-2-мерной сферы? А n-3-мерной сферы? ... А 2-мерной сферы (т.е. окружности)?

    Для 1-мерной сферы (т.е. совокупности двух точек) ответ очевиден: искомый "диаметр" равен "большой диагонали" n-мерного куба, т.е. Dmax = 2√n

    ОтветитьУдалить
    Ответы
    1. Да, эти задачки стоит порешать всем.
      Кстати, выше одну из них уже предлагали обдумать, чтобы лучше понять, что происходит в общем случае.

      Удалить
    2. Никто не клюнул на смежную задачу. Давайте все-таки попробуем решить ее общими усилиями. Для простейшего случая n=3 у меня получается, что максимальный радиус R окружности, которую можно спрятать в трехмерном кубе со стороной 2 равен √(3/2).

      Вот мои расчеты. Пока кто-то не убедит меня в обратном, полагаю, что искомая окружность лежит в плоскости, перпендикулярной одной из главных диагоналей куба (например, [-1,-1,-1] [1,1,1]), а ее центр совпадает с центром куба. Подобная окружность описывается следующей системой уравнений:

      X + Y + Z = 0
      X^2 + Y^2 + Z^2 = R^2

      Исключив Z, получаем:

      X^2 + Y^2 + XY = R^2/2

      Введем новые переменные r и φ:

      X(φ) = r(φ)cos(φ)

      Y(φ) = r(φ)sin(φ)

      [1 + sin(φ)cos(φ)][r(φ)]^2 = R^2/2

      Отсюда имеем:

      X(φ) = Rcos(φ)/√[2(1 + sin(φ)cos(φ))]

      Максимальное значение X(θ) = 1 достигается при значении φ = θ, удовлетворяющем условию достижения экстремума:

      dX(φ)/dφ = 0, что равносильно условию cos(θ) + 2sin(θ) = 0, т.е. sin(θ) = -1/√5, cos(θ) = 2/√5.

      Следовательно, r(θ) = 1/cos(θ) = √5/2. Подставив полученные выражения sin(θ) = -1/√5, cos(θ) = 2/√5 и r(θ) = √5/2 в уравнение [1 + sin(θ)cos(θ)][r(θ)]^2 = R^2/2, получаем окончательно R = √(3/2).

      Удалить
    3. Задача, конечно, полезная. Всем стоит порешать и эту, и остальные разновидности. Но мне кажется, что особой активности по этим формулировкам пока не видно, так как ничего парадоксального пока не обещано (и я не знаю, чего же внезапного там можно найти).
      Нужна мотивация чуть больше, чем "вам будет полезно". Поэтому я стараюсь давать задачки с мотивацией "вам будет удивительно".

      Удалить
    4. Для случая n=4 расчеты показывают, что самый большой 3-мерный шар внутри 4-мерного куба со стороной 2 имеет радиус R=√(4/3). Для случая n=3 мы получили выше R=√(3/2). По аналогии, для произвольного n мы вероятно получим R=√[n/(n-1)], т.е. при росте n, R стремится к 1 сверху, что хорошо согласуется с интуицией.

      Да, похоже, что это упражнение не обещает эффектного парадокса.

      Удалить
    5. Правдоподобные рассуждения, изложением которых я не буду утомлять читателей, приводят к гипотезе:

      Максимальный радиус m-мерной сферы, которую можно целиком упаковать внутри n-мерного куба со стороной 2, где n≥m≥1, равен R=√(n/m).

      Я не смог пока найти компактного и красивого доказательства этой гипотезы, но попробую продемонстрировать, что она верна для n=4 и m=2, т.е. самая большая окружность внутри 4-мерного куба со стороной 2 имеет радиус R=√2.

      Искомая окружность естественно лежит в некой плоскости, а плоскость в 4-мерном пространстве есть пересечение двух "непараллельных" 3-мерных пространств. Поскольку мы ищем окружность максимального радиуса, должно быть ясно, что эти 3-мерные пространства должны быть "диагонального" типа, следовательно искомая окружность описывается так:

      ±X ± Y ± Z ± U = 0
      ±X ± Y ± Z ± U = 0
      X^2 + Y^2 + Z^2 + U^2 = R^2,

      где знаки "-" и "+" в первых двух уравнениях, описывающих 3-мерные "диагональные" пространства, следует выбирать таким образом, чтобы эти два уравнения не вырождались друг в друга. На первый взгляд кажется, что нам придется перебрать огромное количество комбинаций из двух 3-мерных "диагональных" пространств. На самом же деле имеются всего лишь две отличающиеся по существу комбинации:

      X + Y + Z + U = 0
      X + Y + Z - U = 0
      X^2 + Y^2 + Z^2 + U^2 = R^2,

      или

      X + Y + Z + U = 0
      X - Y + Z - U = 0
      X^2 + Y^2 + Z^2 + U^2 = R^2.

      Первая система уравнений равносильна следующей:

      U = 0
      X + Y + Z = 0
      X^2 + Y^2 + Z^2 = R^2,

      т.е. первая комбинация фактически свелась к задаче, которую мы уже решили выше: R=√(3/2).

      Вторая комбинация даст нам окружность большего радиуса. Действительно, систему уравнений во втором случае можно легко преобразовать к виду:

      Z = -Х
      U = -Y
      X^2 + Y^2 = R^2/2

      Отсюда уже легко видеть, что радиус окружности внутри 4-мерного куба со стороной 2 имеет максимальное значение R=√2.

      Удалить
  17. Завидую тем, кто способен себе представить 10-мерный куб!

    user_ami

    ОтветитьУдалить
    Ответы
    1. 10-мерный ещё легко, так как у нас на руках как раз 10 пальцев :)

      А если серьёзно, то можно особенно ничего не представлять, а честно смотреть на алгебраические выражения:
      - описание сферы уже дано в заметке,
      - а куб описан выше в комментариях. Стоит понять, что больше ничего и не требуется.

      Удалить
    2. Посмотрела. И что?

      В общем случае радиус сферы, вписанной в единичный кубик, равен 1/2. Длина диагонали кубика корень(эн). Радиус внутренней сферы равен половине диагонали минус радиус угловой сферы, то есть корень(эн)/2-1/2, а диаметр, соответственно, вдвое больше, то есть корень(эн)-1. Следовательно при неограниченном росте эн искомый диаметр тоже будет возрастать неограничено, а в случае 16-мерного куба он равен 3. (Хотя правдоподобность этого ответа проверить нельзя так же, как и любого другого)

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

      А вот называть центральную сферу "вписанной в сферы, вписанные в куб" неверно. Она вписана не "в них", а между ними снаружи и вполне может быть больше. Например, в случае эн=2 при диаметрах угловых кругов 1-1/корень(2) диаметр центрального круга будет равен стороне квадрата, а при меньших -- её превысит.

      Удалить
    3. З.Ы. Извините, в последнем абзаце число 1-1/корень(2), конечно, не верно, не то число написала. На самом деле меня получилось, что центральная окружность коснётся квадрата при радиусе угловой (корень(2)-1)/(корень(2))+1=3-2*(корень(2)), а диаметре, соответственно, 6-4(корень(2))

      Удалить
    4. > А вот называть центральную сферу "вписанной в сферы, вписанные в куб" неверно
      Да, Вы правы, это было несколько запутывающее определение. Лучше говорить "сфера, зажатая между единичных сфер, прижатых к углам куба со стороной 2".

      Вы здорово разобрались в этой задаче!

      Удалить
    5. И, тем не менее, по лично моя интуиция отказывается что-либо говорить о 16-мерном кубе вообще (и даже о четырёхмерном), а при шутке автора по поводу 10 пальцев представила моему внутреннему взору весьма обидную фигуру из трёх. Никаих же нарушений логики я не заметила.

      В двумерном случае угловые окружности образуют вокруг центральной замкнутую фигуру, но уже в трёхмерном случае это не так. Если спроецировать трёхмерный куб с угловыми шарами на одну из его граней то посередине останется не закрытая шарами дырочка, в которую можно вписать окружность диаметром кор(2)-1. (Замечу в скобочках, что эта проекция совпадает с чертежом двумерного случая) На самом деле, конечно, самое узкое место лежит не на грани, а в параллельной плоскости на расстоянии 1/2, но вывода насчёт диаметра вписанной окружности это не меняет. Если рассматривать трёхмерный куб с шарами и аналогично считать его гранью-проекцией четырёхмерного, то там посередине дырочка, в которую можно вписать трёхмерный шар диаметром уже побольше -- кор(3)-1. Про четырёхмерный куб сказать ничего не могу, но если аналогично считать каждый куб с шарами проекцией следующего, получается, что против каждой (Н-1)мерной грани Н-мерного куба есть (Н-1)-мерная дырка, в которую можно вписать (Н-1)мерную сферу диаметром кор(Н-1)-1. Теперь попробуем посчитать диаметр (Н-1)мерного сечения Н-мерной центральной сферы на расстоянии 1/2 от её центра. Если рассуждать по аналогии с двух- и трёх-мернными случаями, то радиус -- это второй катет треугольника с гипотенузой, равной радиусу центральной Н-мерной сферы, и вторым катетом 1/2. Чтобы получить сразу диаметр, возьмём сразу вдвое больше и получим (корН-1)^2-1^2=Д^2 или Н-2корН=Д^2. Упростить это выражение у меня не получилось, но если возвести в квадрат рассчитанный диаметр (Н-1) мерной сферы, вписуемой в дырку корень(Н-1)-1, получится Н-2кор(Н-1), что больше левой части Н-2корН. Значит, Д ещё меньше, и размер дырки достаточен.

      Два эн граней -- два эн дыр,
      В каждой грани -- целый мир:
      Эн на единицу меньше,
      На два штуки меньше дыр... (стихи мои)

      Очень надеюсь, что это не больший бред, чем несомый Вами самим.

      А вот насчёт задачи про три шкатулки интуиция мне сообщила нечто такое, из чего следовал вывод, что в лучшем случае менять шкатулку -- 50 на 50, а в худшем -- заведомо не следует.

      Удалить
    6. user_ami, приношу извинения, если шутка о десяти пальцах на двух руках Вас задела.

      > Никаких же нарушений логики я не заметила.
      В чём именно?

      Спасибо за стихи!

      > Очень надеюсь, что это не больший бред, чем несомый Вами самим.
      Я иногда ошибаюсь, конечно. Если не трудно, указывайте, пожалуйста, на такие места. Это даст мне возможность легко исправиться (если я осознаю ошибку, естественно). В любом случае, только через такой диалог можно прийти к истине.

      Удалить
    7. Не задела (если в смысле "обидела"), но Вы как-то неправильно меня поняли. Лучше уж извинитесь за это. :)

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

      Про шкателки я не отписалась потому, что тема старая, и я не была уверена, стоит ли отвечать теперь.

      Удалить
    8. Да, неправильно понять - это запросто. Если можете, поясните свою позицию. Я внимательно читаю все комментарии, но не всегда могу понять, что же хотел сказать человек, когда написал этот конкретный текст. Делаю это непреднамеренно, но всё равно приношу извинения.

      В теме про шкатулки можете смело писать. Я читаю все комментарии, да и во многих заметках есть активные читатели, которые отвечают (так как подписались на уведомление о новых комментариях).

      Удалить
    9. Анонимный16.03.2012, 07:00

      Поддерживаю user_ami

      Понятие "что нам подсказывает интуиция" применимо только к тем объектам, явлениям, с которыми мы имеем дело в повседневном бытовом плане или к тем, на которые можно естественным образом экстраполировать наш повседневный бытовой опыт.

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

      Злой анонимный Х.

      Вопрос по существу. Что в теории вероятности то не устраивает?

      Удалить
    10. > Понятие "что нам подсказывает интуиция" применимо только к тем объектам, явлениям, с которыми мы имеем дело в повседневном бытовом плане
      К сожалению, этот тезис не мешает многим людям иметь ощущение по поводу того, как должно быть что-то, с чем они почти не сталкивались. Многие имеют убеждение, основанное на непонятно чём. И мы здесь, в частности, разбираемся с подобными заблуждениями.

      > Вопрос по существу. Что в теории вероятности то не устраивает?
      В теории вероятностей всё устраивает. Она красива и надёжна.

      Удалить
    11. Анонимный16.03.2012, 12:06

      Илья, вообщето я изначально подумал, что это именно Вы стараетесь людей столкнуть с пути истинного в сторону заблуждений (Чего тогда стОит фраза "А теперь надо понять, кто нас обманул"?), заставляете формировать у себя в голове суждение, "основанное на непонятно чём". А теперь выясняется, что они (те самые многие люди) зря так делали (слушали Ваши науськивания и заблуждались).
      Это такой тонкий педагогический приём?

      Хорошо, -стей, непринципиально, но на мой вкус так правильнее. Почему тогда теория эволюции, закон гравитации, уравнение движения а не эволюций, гравитаций и движений?

      Всёже, тогда зачем её расширять?

      Злой анонимный Х.

      Удалить
    12. > А теперь выясняется
      Нет, не выясняется. Больше похоже, что при переводе мысли из моей головы в текст, а потом из этого текста в Вашу голову, произошли заметные деформации исходного смысла. И если Вам удобно считать, что тут кого-то науськивают, то давайте договоримся, что исключительно Вас.

      > зачем её расширять?
      Чтобы решать задачи, которые ранее решить было невозможно.

      Удалить
  18. Анонимный10.03.2012, 06:41

    Вы извините, отвечу не читая комментарием.

    В n-мерном случае имеем формулу:
    d(A, B) := ((A1-B1)^n + ... + (An-Bn)^n)^(1/n)
    верно?

    ОтветитьУдалить
    Ответы
    1. Анонимный10.03.2012, 06:52

      Откуда взялись квадратные корни в n-мерных случаях?

      Удалить
    2. Ещё имеет смысл эту формулу для n=3 :)

      Удалить
    3. d(A, B) := ((A1-B1)^n + ... + (An-Bn)^n)^(1/n)так не правильно!(проверь хотя бы для n = 3)
      d(A, B)^2 = ((A1-B1)^2 + ... + (An-Bn)^2) вот так верно!

      Удалить
  19. Анонимный10.03.2012, 20:20

    Никто не купился :'-(

    ОтветитьУдалить
  20. После ознакомления с комментариями вынужден признать, что интуиция подвела меня. Аккуратная алгебра показывает, что диаметр n-мерной сферы, о которой идет речь в задаче, действительно равен √n-1, т.е. эта сфера вылезает за пределы n-мерного куба со стороной 2 при n > 9.

    Весомое и наиболее четкое возражение интуиции против такого довольно неожиданного результата дано в комметарии Дмитрия К : Сложно представить, как эта сфера расположена по отношению к точкам касания угловых сфер между собой. Эти-то точки находятся внутри куба. И все точки касания центральной сферы тоже внутри куба. Поэтому с трудом представляется выход за грани куба с одновременным сохранением сферической формы.

    Попробую привести несколько аргументов которые возможно помогут интуиции как-то смириться с результатом математического анализа. Интуиции легче всего увидеть свойства симметрии, если начало координат n-мерного пространства совместить с центром исходного n-мерного куба:

    -1 <= Х1 <= 1,
    -1 <= Х2 <= 1,
    ...
    -1 <= Хn <= 1.

    Для начала отметим следующие, помогающие интуиции, очевидные факты:

    1. Минимальное расстояние, которое необходимо пройти от цетра куба до ее поверхности, равно 1 независимо от размерности n . Это достигается движением вдоль любой из координатных линий.

    2. Максимальное расстояние, которое необходимо пройти от цетра куба до ее поверхности, равно расстоянию от начала координат до любой угловой точки куба, а поскольку любая угловая точка имеет набор координат типа ±1, ±1, ..., ±1(где каждая координата берется со знаком + или -), то это максимальное расстояние равно √n .

    3. После разбиения исходного куба имеем 2^n единичных кубов. Центр каждого единичного куба имеет набор координат вида ±1/2, ±1/2, ..., ±1/2.

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

    Продолжение следует ...

    ОтветитьУдалить
  21. Вторая часть.

    Теперь давайте рассмотрим множество точек касания угловых сфер между собой. Как совершенно правильно отметил Дмитрий, все эти точки попарных касаний находятся внутри куба. Но лежит ли хотя бы одна из этих точек на координатной линии (если одна из них лежит на координатной линии, то все они ввиду симметрии должны лежат на координатных линиях)? Это очень важный вопрос, потому что если окажется, что точки касания угловых сфер лежат на координатных линиях, тогда совершенно невозможно, чтобы ядерная сфера выходила за пределы исходного куба.

    Как легко убедиться, при n=2 все 4 точки касания угловых окружностей действительно лежат на координатных линиях. Но при n=2 ядерная окружность и не выходит за пределы квадрата.

    Однако оказывается, что при n>2 точки касания угловых сфер никогда не лежат на координатных линиях, что делает возможным выход ядерной сферы за пределы исходного куба. Действительно, давайте уточним координаты этих самых точек касания угловых сфер. Две угловые сферы А и В являются смежными и соприкасаются если все координаты центров этих сфер совпадают за исключением одной единственной, скажем, k-той координаты: А1=В1=±1/2, А2=В2=±1/2, ...., Аk=1/2, Вk=-1/2, ..., Аn=Вn=±1/2. Следовательно, набор координат точки С касания сфер А и В выглядит так С1=±1/2, С2=±1/2, ...., Сk=0, ..., Сn=±1/2. А это и означает, что при n>2 точки касания угловых сфер никогда не лежат на координатных линиях (точка лежит на координатной линии лишь тогда, когда все координаты этой точки равны нулю за возможным исключением одной координаты).

    Теперь когда мы знаем как выглядит набор координат произвольной точки касания двух смежных угловых сфер, легко видеть, что все эти точки лежат на сфере с центром в начале координат и диаметром Dск=√(n-1).

    Диаметр же ядерной сферы легко вычисляется если, пользуясь очевидной симметрией задачи, заметить, что ядерная сфера просто зажата между двумя угловыми сферами на противоположных концах любой большой диагонали исходного куба, скажем между угловыми сферами со следующими наборами координат (1/2, 1/2, ... , 1/2) и (-1/2, -1/2, ... , -1/2):

    Dяс=√n-1.

    Сравнивая полученные выражения для диаметров двух центральных сфер Dск=√(n-1) и Dяс=√n-1, легко видеть, что ядерная сфера находится внутри сферы, на которой лежат все точки касания угловых сфер. И обе эти сферы вылезают за пределы исходного n-мерного куба со стороной 2 при n > 9.

    ОтветитьУдалить

Понравилась заметка? Подпишитесь на RSS-feed или email-рассылку.

Хотите поделиться ссылкой с другими? Добавьте в закладки:



Есть вопросы или предложения? Пишите письма на адрес mytribune АТ yandex.ru.

С уважением,
      Илья Весенний