Сборник материалов выездных школ команды Москвы на Всероссийскую математическую олимпиаду

• Название: Сборник материалов выездных школ команды Москвы на Всероссийскую математическую олимпиаду
• Дата: 19.09.2022
• Размер: 3.42 Mb.
• Имя файла: matprob.pdf
• Тип: Сборник; #684321
• страница: 19 из 31

б) Сколько существует различных функций, имеющих не более двух существенных переменных?
в) Придумайте функцию трех переменных, существенно зависящую от каждой переменной.
г)* Тоже, что в б, но для трех переменных. Назовем функцию f линейной, если при некоторых ε ∈ и подмножестве для любого (x
1
, . . . , x n
) ∈ выполнено (те. если ее полином Жегалкина не содержит мономов степени больше Точнее, в приведенном определении f — не функция алгебры логики, а отображение f : Z
n
2
→ Z
2
. Функция алгебры логики называется линейной, если некоторое (или, эквивалентно, любое) представляющее ее отображение f : Z
n
2
→ линейно. Далее такие тонкости будем опускать (ноне советуем вам опускать их в своих олимпиадных или научных работах!).
а) Если все функции набора линейные, то через них нельзя выразить ни одну нелинейную функцию.
б) Через функции задачи а) можно выразить все линейные функции.
в) Не существует одной линейной функции, через которую можно выразить все линейные функции. Назовем функцию f монотонной, если для любых двух наборов, . . . , x n
) > (y
1
, . . . , y n
) выполняется f (x
1
, . . . , x n
) > f (y
1
, . . . , y n
). При этом (x
1
, . . . , x n
) > (y
1
, . . . , y n
), если это выполнено покомпонентно, то есть x
1
>
y
1
, x
2
>
y
2
, . . . , x n
>
y а, б) Решите аналоги задача, б) для монотонных функций (7 в)
вместо 7 а)).
в) Не существует трех монотонных функций, через которые можно выразить все монотонные функции. Функция f называется сохраняющей 0, если f(0, 0, . . . , 0) = 0.
а)–в) Решите аналоги задач 10 а)–в) для функций, сохраняющих 0
(7 г) вместо 7 а. Аналогично определим функции, сохраняющие 1.
а)–в) Решите аналоги задач 10 а)–в) для функций, сохраняющих 0
(7 д) вместо 7 а

Гл. 11. Многомерный куб. Назовем функцию f самодвойственной, если f(¯¯
x
1
, ¯¯¯
x
2
, . . . , ¯¯¯
x n
) =
= f (x
1
, x
2
, . . . , x а, б) Решите аналоги задача, б) для функций, сохраняющих 0
(7 е) вместо 7 а)).
в) Существует одна самодвойственная функция, через которую можно выразить все самодвойственные функции. а) Пусть f — несамодвойственная функция. Докажите, что через f и x можно выразить константы 0 и б) Пусть f — немонотонная функция. Докажите, что через f икон- станты 0, 1 можно выразить функцию в) Пусть f — нелинейная функция. Докажите, что через f , x, 1 и можно выразить &.
г)
Критерий полноты — теорема Поста. Через функции данного множества функций можно выразить любую функцию тогда и только тогда, когда в этом множестве найдутся функции (необязательно различные) каждого из пяти предполных классов.
Предполным классом (= множеством) называется каждое из пяти перечисленных выше множеств функций (линейные, монотонные, сохраняющие, сохраняющие 0 и самодвойственные).
16. а) В каждом из пяти предполных классов есть функции, не принадлежащие к другим классам, те. для любых двух различных пред- полных классов A и B есть такая функция f , что f ∈ A и f 6∈ б) Множество функций называется полным, если через функции этого множества можно выразить любую функцию. Докажите, что при добавлении к каждому из пяти предполных классов любой новой функции получается полное множество. Придумайте бесконечное число различных классов функций,
замкнутых относительно суперпозиции
2)
Зачетные задачи 2 а, баб ваг а)–е); 10 а, баба, баб ага, б).
Указания
7. Ответ нет (во всех пунктах).
Указание:
б), г, е) f (x) = 1 выразить нельзя;
б), де выразить нельзя;
в) f (x) = x выразить нельзя.
2)
На занятии была показана решетка Поста, состоящая из всех классов функций,
замкнутых относительно суперпозиции

Геометрия N -мерного куба
285
Рассмотрите выражение указанной выше функции через данные.
Все переменные в нем можно считать совпадающими. Ответа б) 12; в) Геометрия мерного куба (Ю. М. Бурман
Хорошо известно, что точке плоскости можно сопоставить пару чисел ее декартовых координат (для этого нужно предварительно выбрать систему координат, те. начало координат и оси. Тем самым плоскость можно понимать просто как множество всевозможных пар (x
1
, действительных чисел. Аналогично трехмерное пространство можно считать просто множеством всевозможных троек (x
1
, x
2
, x
3
). Накладывая на числа различные ограничения, мы получим описание разнообразных подмножеств плоскости и пространства (плоских фигур и трехмерных тел).
Контрольный вопрос
Даны три набора условий на числа x
1
, x
2
, а) x
1
= x
2
= б) x
1
+ 2x
2
+ 3x
3
= 0, 3x
1
+ 2x
2
+ x
1
= в) x
2 1
+ x
2 3
− 2x
3

= Какие из них задают прямую в трехмерном пространстве?
Когда измерений больше, чем три, координатный подход становится ведущим удобно определить, скажем, четырехмерное пространство как множество всевозможных наборов (x
1
, x
2
, x
3
, x
4
) из четырех действительных чисел.
Отрезком мы назовем множество [−1, 1] = {x: |x| 6 1} чисел,
по модулю не превосходящих 1. Квадратом — множество [−1, 1]
2
=
= {(x
1
, x
2
) : |x
1
|, |x
2
| 6 1} пар чисел, каждое из которых не превосходит по модулю 1. Кубом — множество, 1]
3
= {(x
1
, x
2
, x
3
) : |x
1
|, |x
2
|, |x
3
| 6 троек таких чисел, четырехмерным кубом — четверок, и т. д. См. риса) Расставьте на рисунке координаты вершин.

б) Сколько вершину мерного куба?
в) Какие вершины мерного куба соединены между собой ребром,
а какие нет

Гл. 11. Многомерный куб

Рис. 1. Кубы размерностей 1, 2, 3, 4 2. а) Сколько ребер у мерного куба?
б) Двумерных граней?

в) мерных граней, где k — произвольное число от 0 дог) Всего граней, всевозможных размерностей?
Точка на прямой задается условием (уравнением) вида x = p. Прямая на плоскости задается уравнением вида a
1
x
1
+ a
2
x
2
= p, где и неравны нулю одновременно. Плоскость в пространстве задается уравнением вида a
1
x
1
+ a
2
x
2
+ a
3
x
3
= p, где среди чисел a
1
, a
2
, есть хотя бы одно ненулевое. Аналогичное уравнение от 4 переменных задает трехмерное подпространство в четырехмерном пространстве, и т. д.;
в общем случаев мерном пространстве) такой объект называется гиперплоскостью. Нас будут интересовать гиперплоскости, заданные уравнениями x
1
+ x
2
= 0, x
1
+ x
2
+ x
3
= 0, и т. д.
Ортантом называется часть плоскости (в этом случае еще говорят квадрант, трехмерного пространства (октант, четырехмерного пространства, и т. д, в котором все координаты имеют фиксированные знаки. Например, на прямой имеется два ортанта — лучи луч {x | x < 0}, на плоскости — 4 квадранта, и т. д всего в мерном пространстве, очевидно, 2
n ортантов.
Контрольный вопрос
Сколько ортантов пересекаются с гиперплоскостью, заданной уравнением а) Все;
б) все, кроме двух;
в) ровно половина.
Пересечение прямой x
1
+ x
2
= 0 и квадрата — отрезок, соединяющий две вершины (диагональ. Пересечение плоскости x
1
+ x
2
+ x
3
= 0 и куба многоугольник. Какой именно Нарисуйте этот многоугольники перечислите координаты его вершин

Геометрия N -мерного куба
287
Следует ожидать, что пересечение четырехмерного куба [−1, и трехмерной гиперплоскости x
1
+ x
2
+ x
3
+ x
4
= 0 — трехмерный многогранник обозначим его Q
3 4. а) Перечислите все вершины многогранника б) Перечислите все ребра. Какие вершины соединены ребром, а какие нет Нарисуйте каркас многогранника Q
3
, состоящий из вершин и ребер.
в) Перечислите все грани многогранника Q
3
. Сколько вершин в каждой грани и какие именно вершины принадлежат одной грани Нарисуйте многогранник Флагом в многограннике называется набор из вершины v («гв´оздик»),
ребра e (древко) и грани f (полотнище) таких, что v — один из концов e, а e — одна из сторон f . Многогранник Q называется правильным, если для любых двух его флагов (v
1
, e
1
, f
1
) и (v
2
, e
2
, f
2
) существует движение пространства, переводящее Q в себя и при этом переводящее v
1 7→ v
2
, e
1 7→ e
2
, f
1 7→ f
2 5. Докажите, что для любых двух вершин v
1
, многогранника существует движение четырехмерного пространства, переводящее в себя ива) Пусть e
1
, e
2
— два ребра многогранника Q
3
, имеющие общую вершину v = (1, 1, −1, −1). Докажите, что существует движение четырехмерного пространства, переводящее в себя, вершину v в себя,
а ребро в б) Пусть f
1
, f
2
— две грани многогранника Q
3
, имеющие общее ребро e = {(−t, 1, t, −1) | −1 6 t 6 1}. Докажите, что существует движение четырехмерного пространства, переводящее в себя, ребро e и вершину v (из пункта а) в себя, а грань в f
2 7. Выведите из задачи, что многогранник Q
3
— правильный. Проверьте изученный метод на простом примере докажите, действуя как в задачах 5, 6 и 7, что многоугольник из задачи 3 — правильный. Какие правильные многогранники могут получаться при пересечении четырехмерного куба трехмерной гиперплоскостью. Примените изученный метод к более сложному примеру рассмотрите четырехмерный многогранник Q
4
, полученный пересечением пятимерного куба [−1, и гиперплоскости x
1
+ x
2
+ x
3
+ x
4
+ x
5

= Сколько у него вершин ребер двумерных граней трехмерных граней?
Является ли правильным

Гл. 11. Многомерный куб. Докажите, что любое мерное сечение (n + мерного куба,
перпендикулярное диагонали и проходящее через вершину, комбинатор- но эквивалентно зоне в мерном кубе между двумя аналогичными сечениями. Точнее, пусть, b) = {(x
1
, . . . , x n
) | x i
∈ [0, 1], a 6 x
1
+ . . . + x Докажите, что L
n+1
(k, k) комбинаторно эквивалентно L
n
(k − 1, k). Другими словами, между этими мерными многогранниками имеется взаимно однозначное соответствие, при котором вершинам, ребрами вообще граням всех размерностей одного многогранника отвечают вершины,
ребра и грани соответствующих размерностей другого многогранника.
Начните со случая n = 3, k = Зачетные задачи 3, 4, 6, 7, Решения. Ответа) Частичный ответ см. на рис. б) Вершины куба имеют координаты (±1, ±1, . . . , ±1), где сочетание знаков произвольно. На каждом месте в строке координат может стоять числа (1 и −1). Всего чисел в строке n. Поэтому общее количество вершин равно 2 · 2 · . . . · 2 = 2
n в) Вершины соединены между собой ребром, если соответствующие наборы координат отличаются ровно водной позиции, 1)
(−1, 1)
(−1, 1)
(−1, 1)
(−1, 1)
(−1, 1)
(−1, 1)
(−1, 1)
(−1, 1)
(−1, 1)
(−1, 1)
(−1, 1)
(−1, 1)
(−1, 1)
(−1, 1)
(−1, 1)
(−1, 1)
(−1, 1)
(−1, 1)
(−1, 1)
(−1, 1)
(−1, 1)
(−1, 1)
(−1, 1)
(−1, 1)
(−1, 1)
(−1, 1)
(−1, 1)
(−1, 1)
(−1, 1)
(−1, 1)
(−1, 1)
(−1, 1)
(−1, 1)
(−1, 1)
(−1, 1)
(−1, 1)
(−1, 1)
(−1, 1)
(−1, 1)
(−1, 1)
(−1, 1)
(−1, 1)
(−1, 1)
(−1, 1)
(−1, 1)
(−1, 1)
(−1, 1)
(−1, 1)
(−1, 1)
(−1, 1)
(−1, 1)
(−1, 1)
(−1, 1)
(−1, 1)
(−1, 1)
(−1, 1)
(−1, 1)
(−1, 1)
(−1, 1)
(−1, 1)
(−1, 1)
(−1, 1)
(−1, 1)
(−1, 1)
(−1, 1)
(−1, 1)
(−1, 1)
(−1, 1)
(−1, 1)
(−1, 1)
(−1, 1)
(−1, 1)
(−1, 1)
(1, 1)
(1, 1)
(1, 1)
(1, 1)
(1, 1)
(1, 1)
(1, 1)
(1, 1)
(1, 1)
(1, 1)
(1, 1)
(1, 1)
(1, 1)
(1, 1)
(1, 1)
(1, 1)
(1, 1)
(1, 1)
(1, 1)
(1, 1)
(1, 1)
(1, 1)
(1, 1)
(1, 1)
(1, 1)
(1, 1)
(1, 1)
(1, 1)
(1, 1)
(1, 1)
(1, 1)
(1, 1)
(1, 1)
(1, 1)
(1, 1)
(1, 1)
(1, 1)
(1, 1)
(1, 1)
(1, 1)
(1, 1)
(1, 1)
(1, 1)
(1, 1)
(1, 1)
(1, 1)
(1, 1)
(1, 1)
(1, 1)
(1, 1)
(1, 1)
(1, 1)
(1, 1)
(1, 1)
(1, 1)
(1, 1)
(1, 1)
(1, 1)
(1, 1)
(1, 1)
(1, 1)
(1, 1)
(1, 1)
(1, 1)
(1, 1)
(1, 1)
(1, 1)
(1, 1)
(1, 1)
(1, 1)
(1, 1)
(1, 1)
(1, 1)
(1, 1)
(1, −1)
(1, −1)
(1, −1)
(1, −1)
(1, −1)
(1, −1)
(1, −1)
(1, −1)
(1, −1)
(1, −1)
(1, −1)
(1, −1)
(1, −1)
(1, −1)
(1, −1)
(1, −1)
(1, −1)
(1, −1)
(1, −1)
(1, −1)
(1, −1)
(1, −1)
(1, −1)
(1, −1)
(1, −1)
(1, −1)
(1, −1)
(1, −1)
(1, −1)
(1, −1)
(1, −1)
(1, −1)
(1, −1)
(1, −1)
(1, −1)
(1, −1)
(1, −1)
(1, −1)
(1, −1)
(1, −1)
(1, −1)
(1, −1)
(1, −1)
(1, −1)
(1, −1)
(1, −1)
(1, −1)
(1, −1)
(1, −1)
(1, −1)
(1, −1)
(1, −1)
(1, −1)
(1, −1)
(1, −1)
(1, −1)
(1, −1)
(1, −1)
(1, −1)
(1, −1)
(1, −1)
(1, −1)
(1, −1)
(1, −1)
(1, −1)
(1, −1)
(1, −1)
(1, −1)
(1, −1)
(1, −1)
(1, −1)
(1, −1)
(1, −1)
(1, −1)
(−1, −1)
(−1, −1)
(−1, −1)
(−1, −1)
(−1, −1)
(−1, −1)
(−1, −1)
(−1, −1)
(−1, −1)
(−1, −1)
(−1, −1)
(−1, −1)
(−1, −1)
(−1, −1)
(−1, −1)
(−1, −1)
(−1, −1)
(−1, −1)
(−1, −1)
(−1, −1)
(−1, −1)
(−1, −1)
(−1, −1)
(−1, −1)
(−1, −1)
(−1, −1)
(−1, −1)
(−1, −1)
(−1, −1)
(−1, −1)
(−1, −1)
(−1, −1)
(−1, −1)
(−1, −1)
(−1, −1)
(−1, −1)
(−1, −1)
(−1, −1)
(−1, −1)
(−1, −1)
(−1, −1)
(−1, −1)
(−1, −1)
(−1, −1)
(−1, −1)
(−1, −1)
(−1, −1)
(−1, −1)
(−1, −1)
(−1, −1)
(−1, −1)
(−1, −1)
(−1, −1)
(−1, −1)
(−1, −1)
(−1, −1)
(−1, −1)
(−1, −1)
(−1, −1)
(−1, −1)
(−1, −1)
(−1, −1)
(−1, −1)
(−1, −1)
(−1, −1)
(−1, −1)
(−1, −1)
(−1, −1)
(−1, −1)
(−1, −1)
(−1, −1)
(−1, −1)
(−1, −1)
(−1, −1)
(1, 1, 1)
(1, 1, 1)
(1, 1, 1)
(1, 1, 1)
(1, 1, 1)
(1, 1, 1)
(1, 1, 1)
(1, 1, 1)
(1, 1, 1)
(1, 1, 1)
(1, 1, 1)
(1, 1, 1)
(1, 1, 1)
(1, 1, 1)
(1, 1, 1)
(1, 1, 1)
(1, 1, 1)
(1, 1, 1)
(1, 1, 1)
(1, 1, 1)
(1, 1, 1)
(1, 1, 1)
(1, 1, 1)
(1, 1, 1)
(1, 1, 1)
(1, 1, 1)
(1, 1, 1)
(1, 1, 1)
(1, 1, 1)
(1, 1, 1)
(1, 1, 1)
(1, 1, 1)
(1, 1, 1)
(1, 1, 1)
(1, 1, 1)
(1, 1, 1)
(1, 1, 1)
(1, 1, 1)
(1, 1, 1)
(1, 1, 1)
(1, 1, 1)
(1, 1, 1)
(1, 1, 1)
(1, 1, 1)
(1, 1, 1)
(1, 1, 1)
(1, 1, 1)
(1, 1, 1)
(1, 1, 1)
(1, 1, 1)
(1, 1, 1)
(1, 1, 1)
(1, 1, 1)
(1, 1, 1)
(1, 1, 1)
(1, 1, 1)
(1, 1, 1)
(1, 1, 1)
(1, 1, 1)
(1, 1, 1)
(1, 1, 1)
(1, 1, 1)
(1, 1, 1)
(1, 1, 1)
(1, 1, 1)
(1, 1, 1)
(1, 1, 1)
(1, 1, 1)
(1, 1, 1)
(1, 1, 1)
(1, 1, 1)
(1, 1, 1)
(1, 1, 1)
(1, 1, 1)
(1, 1, −1)
(1, 1, −1)
(1, 1, −1)
(1, 1, −1)
(1, 1, −1)
(1, 1, −1)
(1, 1, −1)
(1, 1, −1)
(1, 1, −1)
(1, 1, −1)
(1, 1, −1)
(1, 1, −1)
(1, 1, −1)
(1, 1, −1)
(1, 1, −1)
(1, 1, −1)
(1, 1, −1)
(1, 1, −1)
(1, 1, −1)
(1, 1, −1)
(1, 1, −1)
(1, 1, −1)
(1, 1, −1)
(1, 1, −1)
(1, 1, −1)
(1, 1, −1)
(1, 1, −1)
(1, 1, −1)
(1, 1, −1)
(1, 1, −1)
(1, 1, −1)
(1, 1, −1)
(1, 1, −1)
(1, 1, −1)
(1, 1, −1)
(1, 1, −1)
(1, 1, −1)
(1, 1, −1)
(1, 1, −1)
(1, 1, −1)
(1, 1, −1)
(1, 1, −1)
(1, 1, −1)
(1, 1, −1)
(1, 1, −1)
(1, 1, −1)
(1, 1, −1)
(1, 1, −1)
(1, 1, −1)
(1, 1, −1)
(1, 1, −1)
(1, 1, −1)
(1, 1, −1)
(1, 1, −1)
(1, 1, −1)
(1, 1, −1)
(1, 1, −1)
(1, 1, −1)
(1, 1, −1)
(1, 1, −1)
(1, 1, −1)
(1, 1, −1)
(1, 1, −1)
(1, 1, −1)
(1, 1, −1)
(1, 1, −1)
(1, 1, −1)
(1, 1, −1)
(1, 1, −1)
(1, 1, −1)
(1, 1, −1)
(1, 1, −1)
(1, 1, −1)
(1, 1, −1)
(1, −1, −1)
(1, −1, −1)
(1, −1, −1)
(1, −1, −1)
(1, −1, −1)
(1, −1, −1)
(1, −1, −1)
(1, −1, −1)
(1, −1, −1)
(1, −1, −1)
(1, −1, −1)
(1, −1, −1)
(1, −1, −1)
(1, −1, −1)
(1, −1, −1)
(1, −1, −1)
(1, −1, −1)
(1, −1, −1)
(1, −1, −1)
(1, −1, −1)
(1, −1, −1)
(1, −1, −1)
(1, −1, −1)
(1, −1, −1)
(1, −1, −1)
(1, −1, −1)
(1, −1, −1)
(1, −1, −1)
(1, −1, −1)
(1, −1, −1)
(1, −1, −1)
(1, −1, −1)
(1, −1, −1)
(1, −1, −1)
(1, −1, −1)
(1, −1, −1)
(1, −1, −1)
(1, −1, −1)
(1, −1, −1)
(1, −1, −1)
(1, −1, −1)
(1, −1, −1)
(1, −1, −1)
(1, −1, −1)
(1, −1, −1)
(1, −1, −1)
(1, −1, −1)
(1, −1, −1)
(1, −1, −1)
(1, −1, −1)
(1, −1, −1)
(1, −1, −1)
(1, −1, −1)
(1, −1, −1)
(1, −1, −1)
(1, −1, −1)
(1, −1, −1)
(1, −1, −1)
(1, −1, −1)
(1, −1, −1)
(1, −1, −1)
(1, −1, −1)
(1, −1, −1)
(1, −1, −1)
(1, −1, −1)
(1, −1, −1)
(1, −1, −1)
(1, −1, −1)
(1, −1, −1)
(1, −1, −1)
(1, −1, −1)
(1, −1, −1)
(1, −1, −1)
(1, −1, −1)
(−1, −1, −1)
(−1, −1, −1)
(−1, −1, −1)
(−1, −1, −1)
(−1, −1, −1)
(−1, −1, −1)
(−1, −1, −1)
(−1, −1, −1)
(−1, −1, −1)
(−1, −1, −1)
(−1, −1, −1)
(−1, −1, −1)
(−1, −1, −1)
(−1, −1, −1)
(−1, −1, −1)
(−1, −1, −1)
(−1, −1, −1)
(−1, −1, −1)
(−1, −1, −1)
(−1, −1, −1)
(−1, −1, −1)
(−1, −1, −1)
(−1, −1, −1)
(−1, −1, −1)
(−1, −1, −1)
(−1, −1, −1)
(−1, −1, −1)
(−1, −1, −1)
(−1, −1, −1)
(−1, −1, −1)
(−1, −1, −1)
(−1, −1, −1)
(−1, −1, −1)
(−1, −1, −1)
(−1, −1, −1)
(−1, −1, −1)
(−1, −1, −1)
(−1, −1, −1)
(−1, −1, −1)
(−1, −1, −1)
(−1, −1, −1)
(−1, −1, −1)
(−1, −1, −1)
(−1, −1, −1)
(−1, −1, −1)
(−1, −1, −1)
(−1, −1, −1)
(−1, −1, −1)
(−1, −1, −1)
(−1, −1, −1)
(−1, −1, −1)
(−1, −1, −1)
(−1, −1, −1)
(−1, −1, −1)
(−1, −1, −1)
(−1, −1, −1)
(−1, −1, −1)
(−1, −1, −1)
(−1, −1, −1)
(−1, −1, −1)
(−1, −1, −1)
(−1, −1, −1)
(−1, −1, −1)
(−1, −1, −1)
(−1, −1, −1)
(−1, −1, −1)
(−1, −1, −1)
(−1, −1, −1)
(−1, −1, −1)
(−1, −1, −1)
(−1, −1, −1)
(−1, −1, −1)
(−1, −1, −1)
(−1, −1, Риса) Ребро мерного куба — это множество наборов из n чисел,
в котором на всех местах, кроме одного (скажем, го, стоят числа одни и те же для всего ребра, а нам месте — произвольное число от −1 до +1. Поэтому чтобы задать ребро, нужно, во-первых, зафиксировать число i, а во-вторых — указать, какие именно числа (1 или −1)

Геометрия N -мерного куба
289
стоят на оставшихся n − 1 местах. Первый выбор можно сделать n способами, второй — способами. Поэтому общее число ребер куба равно б) Двумерная грань — это множество наборов из n чисел, где на двух местах стоят произвольные числа от −1 до 1, а на остальных местах числа ±1 (одни и те же для всей грани. Поэтому чтобы задать двумерную грань, нужно выбрать 2 свободные позиции это можно сделать n(n − 1)/2 способами — и указать, какие именно числа стоят на оставшихся позициях здесь количество способов равно 2
n−2
. Поэтому общее количество двумерных граней равно 2
n−2
C
2
n в) Аналогично общее количество мерных граней равно 2
n−k
C
k г) Грань произвольной размерности описывается так это множество наборов из n чисел, в которых на некоторых местах стоят фиксированные (для данной грани) числа ±1, а на некоторых произвольные числа от −1 до 1 (количество мест, на которых стоят произвольные числа,
равно размерности грани. Таким образом, на каждом из n мест может стоять одно из трех либо 1, либо −1, либо произвольное число. Тем самым общее количество всевозможных граней равно 3 · 3 · . . . · 3 = Одна из этих граней имеет размерность n (все числа произвольные) это сам куб. Для решения этой задачи необязательно знать все движения четырехмерного пространства — нужно лишь иметь достаточный запас. Например, для всякой перестановки i
1
, i
2
, i
3
, чисел 1, 2, 3, 4 существует такое движение — перестановка координат (x
1
, x
2
, x
3
, x
4
) 7→
7→ (x i
1
, x i
2
, x i
3
, x i
4
). Оно, очевидно, сохраняет (переводит в себя) куб, и гиперплоскость x
1
+ x
2
+ x
3
+ x
4
= 0 (напомним, что слово
«перестановка» означает, что среди i
1
, i
2
, i
3
, каждое число 1, 2, 3, встречается ровно один раз. Следовательно, это движение сохраняет и пересечение куба с гиперплоскостью. Если вы решили задачу 5, то легко увидите, что перестановками координат можно перевести любую вершину многогранника в любую другую.
Кстати (это пригодится в других задачах, имеется еще одно движение, переводящее в себя — смена знака всех координат, x
2
, x
3
, x
4
) 7→ (−x
1
, −x
2
, −x
3
, −x
4
).

ГЛАВА 12
МИНИКУРС ПО ТЕОРИИ ГРАФОВ
Простейшие понятия теории графов (А. Б. Скопенков
Данный раздел посвящен базовым определениями понятиям теории графов. Он не потребует никаких знаний и подходит для первого знакомства с этой теорией. а) Некоторые пары (из конечного числа) городов соединены (беспосадочными) авиалиниями. Обязательно ли найдутся два города, из которых можно перелететь (за один разв одинаковое число городов?
б) Агент иностранной разведки сообщил, что каждая из 15 бывших республик СССР заключила договор ровно с 3 другими. Можно ли ему доверять?
в) Выпуклый многоугольник (отличный от треугольника) разбит на треугольники несколькими диагоналями, не пересекающимися нигде,