Archives‎ > ‎

Задание 8 "N-мерный куб"

   Точка 2-мерного пространства (плоскости) имеет две декартовы
координаты x  и y. Ее  можно поэтому отождествить с парой чисел
(x,y). Точка  3-мерного  пространства  -- тройка чисел (x,y,z),
точка 4-мерного  --  четверка  чисел (x,y,z,t). Точка n-мерного
пространства -- это n-ка чисел (x_1,x_2,...,x_n).
   Точки (0,0), (1,0), (0,1) и (1,1) -- вершины квадрата, кото-
рый называется единичным квадратом на плоскости.

8.1. Выпишите в  столбик  а) вершины 3-мерного единичного куба,
б) вершины 4-мерного единичного куба. Расположите их в правиль-
ном порядке. Какое расположение Вы сочтете наиболее правильным?

Вершины n-мерного единичного куба - это n-ки (a_1,a_2,...,a_n),
где a_1, a_2, ..., a_n независимо друг от  друга принимают зна-
чения 0  или 1 (биты).  Количество вершин равно 2^n. Если смот-
реть на слово a_1a_2...a_n как на запись числа  в двоичной сис-
теме счисления, то получится, что вершины  n-мерного куба зану-
мерованы целыми числами от 0 до 2^n-1. В частности, в двумерном
случае:

                  ---------------------------
                  | вершина | слово | номер |
                  ---------------------------
                  |  (0,0)  |   00  |   0   |
                  |  (0,1)  |   01  |   1   |
                  |  (1,0)  |   10  |   2   |
                  |  (1,1)  |   11  |   3   |
                  ---------------------------

8.1 (продолжение). Заполните  такие  же таблицы для 3-мерного и
4-мерного единичных кубов.

   Ребра единичного квадрата описываются так:

              (0,x), (1,x) -- вертикальные ребра,
              (x,0), (x,1) -- горизонтальные ребра,

здесь x пробегает значения от 0 до 1.

   Если вместо 0 и 1 писать a (обозначает бит) и если не писать
скобки и разделяющую запятую, то получится, что ребра кодируют-
ся словами вида ax и xa. Этих слов 4, так  как  бит a принимает
одно из двух значений 0 или 1 (а буква x  однозначно трактуется
как обозначение протяженности).

   Ребра единичного 3-мерного куба описываются так:

(0,0,x), (0,1,x), (1,0,x), (1,1,x) - ребра, параллельные оси z;
(0,x,0), (0,x,1), (1,x,0), (1,x,1) - ребра, параллельные оси y;
(x,0,0), (x,0,1), (x,1,0), (x,1,1) - ребра, параллельные оси x.

здесь x в записи ребра пробегает значения от 0 до 1.

   Если вместо битов 0 или 1 писать a и если не писать скобки и
разделяющую запятую, то получится, что ребра кодируются словами
вида aax,  axa и xaa. Этих слов 12, так как биты a на каждом из
своих двух мест независимо принимают значения 0 или 1, что дает
4 слова для каждого из 3 видов. Буква x везде  однозначно трак-
туется как обозначение протяженности.

8.2. Опишите ребра 4-мерного куба и подсчитайте их количество.

   Грани  3-мерного  единичного  куба описываются словами  вида
axx, xax и xxa.  Вместо a можно поставить любой из битов  0 или
1, поэтому граней каждого вида 2, а всего граней 2*3=6. Буквы x
служат для обозначения протяженности в соответствующих  направ-
лениях. К примеру, слов вида axx имеется 2: 0xx и 1xx, они опи-
сывают грани, заполняемые точками (x_1,x_2,x_3):
слово 0xx --
       x_1=0, x_2 меняется от 0 до 1, x_3 тоже от 0 до 1;
слово 1xx --
       x_1=1, x_2 меняется от 0 до 1, x_3 тоже от 0 до 1.

Эти две грани имеют протяженность в направлениях x_2 и x_3.

   Вместо обозначений x_1, x_2  и  x_3 для координат в 3-мерном
пространстве можно было бы  использовать  обозначения x, y и z,
как мы это и делали раньше, но с x_1, x_2 и x_3 яснее происхож-
дение буквы x для обозначения протяженности.

   Посмотрим теперь на  4-мерный  куб. Вот пример его двумерной
грани:
              x=0, y=0, z от 0 до 1, t от 0 до 1.
То же самое в других обозначениях:
          x_1=0, x_2=0, x_3 от 0 до 1, x_4 от 0 до 1.
Эта грань относится к виду, описываемому словом aaxx.

   А вот пример 3-мерной грани:
          x от 0 до 1, y от 0 до 1, z от 0 до 1, t=1.
То же самое в других обозначениях:
      x_1 от 0 до 1, x_2 от 0 до 1, x_3 от 0 до 1, x_4=1.
Эта грань относится к виду, описываемому словом xxxa.

8.3. Сколько двумерных граней у 4-мерного куба?

8.4. Сколько трехмерных граней у 4-мерного куба?

   Подсчитаем количество k-мерных граней n-мерного куба.  Видов
граней столько,  сколько анаграмм слова, в  котором k букв  x и
остальные n-k букв a.  Это  число мы раньше обозначали C(k,n-k)
или < n/k >. Это число сочетаний из n по  k  или так называемый
биномиальный коэффициент из n по k. Далее, в записи конкретного
вида грани  n-k букв a,  поэтому граней этого вида 2^{m-k} (так
как каждая буква  a принимает независимо одно из двух значений,
0 или 1). Поэтому k-мерных граней n-мерного куба имеется

                                         n!
        B(n,k) = < n/k > * 2^{n-k} = --------- * 2^{n-k}
                                     k! (n-k)!

   К примеру, при подсчете количества двумерных граней 3-мерно-
го куба у нас n=3, k=2 и ответ такой: 3*2=6, при подсчете коли-
чества ребер 3-мерного куба n=3, k=1 и ответ 3*4=12.

   Число
              E_n = Summa_{k=0..n-1} (-1)^k B(n,k)

называется эйлеровой характеристикой n-мерного куба.

8.5. Покажите, что E_n = 1-(-1)^n, то есть E_n = 0 при четном n
и E_n = 2 при нечетном n.

8.6.  Сколько  4-звенных  путей,  идущих по ребрам  из  вершины
(0,0,0,0) в вершину (1,1,1,1) 4-мерного куба?

8.7. Обобщите задачу 8.6 на n-мерный куб.

8.8. Укахите, как  можно,  выйдя из вершины (0,0,0,0) 4-мерного
куба, пройти по всем его ребрам, причем по  каждому только один
раз, и вернуться в вершину, из которой вышли.

   Единичный n-мерный куб задается неравенствами

               0 <= x_1 <= 1, ..., 0 <= x_n <= 1,

а единичный n-мерный симплекс -- неравенствами

          x_1 >= 0,  ..., x_n >= 0, x_1+...+x_n <= 1.

8.9. Какие  результаты, полученные для 3-мерного, 4-мерного или
для  n-мерного  куба, Вы можете перенести на случай  3-мерного,
4-мерного или n-мерного симплекса?

   n-мерный куб с центром в начале координат задается  неравен-
ствами
                  |x_1| <= 1, ..., |x_n| <= 1.

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

   Рассмотрим n-мерный многогранник, задающийся неравенствами

                  |x_1| + ... + |x_n| <= 1.

8.10. Исследуйте  этот многогранник. Как описываются его верши-
ны, ребра и k-мерные грани? Какова его эйлерова характеристика?

   При n=3 этот многогранник называется октаэдром. Задающее его
неравенство можно в этом случае переписать так:

                     |x| + |y| + |z| <= 1.

Стандартный 3-мерный симплекс - это тетраэдр, треугольная пира-
мида, он задается так:

            x >= 0, y >= 0, z >= 0,  x + y + z <= 1

Эйлерова характеристика 3-мерного многогранника равна

                             В - Р + Г,

где В - число вершин, Р - число ребер и Г - число граней.

8.11. Проверьте, что эйлеровы характеристики тетраэдра, октаэд-
ра и куба совпадают.

                           О задачах

   Как обычно, задачи для младших (7-9 класс) рассеяны по всему
тексту. Нужно находить то, что по плечу, и решать.
   В ВЗМШ -- Заочной математической школе при МГУ -- было зада-
ние "Метод  координат  в пространстве", которое школьники очень
любили,  там  были задачи про 4-мерный куб, вызывавшие  большой
интерес. Это задание было по книжке
И.М.Гельфанд, Е.Г.Глаголева, А.А.Кириллов.  Метод координат. --
М.: Наука, разные издания, от 1-го в 1964 г. до 5-го в 1974.
   В  главе  2 этой книжки очень подробно разбирается  4-мерный
куб.
   Интересные рассказы  про  многомерный мир содержатся в книге
Эбботт Э.Э. Флатландия. Бюргер Д. Сферландия. -- М.: Мир, 1976.
Ее первая часть -- перевод вышедшей в 1884 году книги
                     Abbott E.A., Flatland.
Английский текст с  рисунками автора можно взять здесь (и учить
по нему английский):
          http://www.geom.umn.edu/~banchoff/Flatland/
Поиграть с 4-мерным кубом можно  на страничке
          http://www1.tip.nl/%7Et515027/hypercube.html
Там же можно найти много ссылок.
Comments