Задание 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
Там же можно найти много ссылок.
(С) С.И.Соболев, 2000-2002