Разделы 
Дополнительно
Задача по математике - 508
2014-06-08 
В пространстве с прямоугольной системой координат рассматривается множество Е точек с целочисленными координатами, принимающими значения от 0 до 1982. Каждая из этих точек окрашена либо в красный, либо в синий цвет. Сколько существует раскрасок, обладающих следующим свойством; число красных вершин у любого параллелепипеда (с вершинами из Е и ребрами, параллельными осям) делится на 4?
Решение:
Докажем прежде всего, что раскраска точек множества Е удовлетворяет условию задачи тогда и только тогда, когда любой прямоугольник с вершинами из E и сторонами, параллельными осям, имеет четное число красных вершин. Предположим, что число красных вершин некоторого прямоугольника $П_{0}$ нечетно и равно, скажем, I (случай, когда их 3, рассматривается аналогично). Рассмотрим два разных параллелепипеда с одной гранью $П_{0}$ и с противоположными гранями $П_{1}$ и $П_{2}$ соответственно. Тогда, если раскраска удовлетворяет условию задачи, то каждая из граней $П_{1}$ и $П_{2}$ имеет по 3 красных вершины, а параллелепипед с гранями $П_{1}, П_{2}$ имеет 6 красных вершин, что противоречит предположению. Пусть теперь любой прямоугольник имеет четное число красных вершин. Рассмотрим произвольный параллелепипед. Если все его вершины одноцветны, то число красных вершин делится на 4. Если же не все вершины одноцветны, то существует ребро с неодноцветными вершинами и все параллельные ему ребра также имеют неодноцветные вершины (ибо каждая грань имеет четное число красных вершин), а число красных вершин параллелепипеда равно 4. Утверждение доказано. Пусть заданы цвета $(1 + 3 \cdot 1982)$ точек $(0; 0; 0), (x; 0; 0), (0; y; 0), (0; 0; z)$, где $x, y, z$ пробегают все целые числа от 1 до 1982. Докажем, что существует единственная раскраска остальных точек из $E$, удовлетворяющая условию задачи. Для доказательства рассмотрим функцию
$f(x, y, z) = \begin{cases} 0,& \text{если точка}\: (x; y; z) \: \text(красная) \\
1,& \text{если точка}\: (x,y,z) \:\text(синяя) ;
\end{cases}$
по значению $f(x, y, z)$ однозначно восстанавливается цвет точки $(x; y; z)$. Зададим операцию $a \oplus b$ (сложение по модулю 2) следующим образом:
$ a \oplus b = \begin{cases} 0,& \text{если число}\: a+b \: \text(четно), \\
1,& \text{если число}\: a+b \:\text(нечетно). \end{cases}$
Теперь положим
$f(x, y, z) = f(x,0,0) \oplus f(0, y, 0) \oplus f(0, 0, z)$.
Проверка показывает, что для ранее заданных точек эта формула также справедлива и любой прямоугольник с ребрами, параллельными осям, имеет четное число красных вершин (например,
$f(x_{1}, y_{1}, z) \oplus f(x_{2}, y_{1}, z) \oplus f(x_{1}, y_{2}, z) \oplus f(x_{2}, y_{2}, z) = 0$).
т. е., согласно доказанному выше утверждению, полученная раскраска удовлетворяет условию задачи. В силу того же утверждения эта раскраска единственна, так как для нее необходимо выполнение следующих условий:
$f(x, y, 0) = f(0, 0, 0) \oplus f(x, 0, 0) \oplus f(0, y, 0)$,
$f(x, 0, z) = f(0, 0, 0) \oplus f(x, 0, 0) \oplus f(0, 0, z)$
$f(0, y, z) = f(0, 0, 0) \oplus f(0, y, 0) \oplus f(0, 0, z)$
$ f(x, y, z) = f(0, 0, z) \oplus f(x, 0, z) \oplus f(0, y, z) = f(0, 0, z) \oplus f(0, 0, 0) \oplus f(x, 0, 0) \oplus f(0, 0, z) \oplus f(0, 0, 0) \oplus f(0, y, 0) \oplus f(0, 0, z) = f(x, 0, 0) \oplus f(0, y, 0) \oplus f(0, 0, z)$.
Таким образом, число искомых раскрасок равно
$2^{1 + 3 \cdot 1982} = 2^{5947}$.
В пространстве с прямоугольной системой координат рассматривается множество Е точек с целочисленными координатами, принимающими значения от 0 до 1982. Каждая из этих точек окрашена либо в красный, либо в синий цвет. Сколько существует раскрасок, обладающих следующим свойством; число красных вершин у любого параллелепипеда (с вершинами из Е и ребрами, параллельными осям) делится на 4?
Решение:
Докажем прежде всего, что раскраска точек множества Е удовлетворяет условию задачи тогда и только тогда, когда любой прямоугольник с вершинами из E и сторонами, параллельными осям, имеет четное число красных вершин. Предположим, что число красных вершин некоторого прямоугольника $П_{0}$ нечетно и равно, скажем, I (случай, когда их 3, рассматривается аналогично). Рассмотрим два разных параллелепипеда с одной гранью $П_{0}$ и с противоположными гранями $П_{1}$ и $П_{2}$ соответственно. Тогда, если раскраска удовлетворяет условию задачи, то каждая из граней $П_{1}$ и $П_{2}$ имеет по 3 красных вершины, а параллелепипед с гранями $П_{1}, П_{2}$ имеет 6 красных вершин, что противоречит предположению. Пусть теперь любой прямоугольник имеет четное число красных вершин. Рассмотрим произвольный параллелепипед. Если все его вершины одноцветны, то число красных вершин делится на 4. Если же не все вершины одноцветны, то существует ребро с неодноцветными вершинами и все параллельные ему ребра также имеют неодноцветные вершины (ибо каждая грань имеет четное число красных вершин), а число красных вершин параллелепипеда равно 4. Утверждение доказано. Пусть заданы цвета $(1 + 3 \cdot 1982)$ точек $(0; 0; 0), (x; 0; 0), (0; y; 0), (0; 0; z)$, где $x, y, z$ пробегают все целые числа от 1 до 1982. Докажем, что существует единственная раскраска остальных точек из $E$, удовлетворяющая условию задачи. Для доказательства рассмотрим функцию
$f(x, y, z) = \begin{cases} 0,& \text{если точка}\: (x; y; z) \: \text(красная) \\
1,& \text{если точка}\: (x,y,z) \:\text(синяя) ;
\end{cases}$
по значению $f(x, y, z)$ однозначно восстанавливается цвет точки $(x; y; z)$. Зададим операцию $a \oplus b$ (сложение по модулю 2) следующим образом:
$ a \oplus b = \begin{cases} 0,& \text{если число}\: a+b \: \text(четно), \\
1,& \text{если число}\: a+b \:\text(нечетно). \end{cases}$
Теперь положим
$f(x, y, z) = f(x,0,0) \oplus f(0, y, 0) \oplus f(0, 0, z)$.
Проверка показывает, что для ранее заданных точек эта формула также справедлива и любой прямоугольник с ребрами, параллельными осям, имеет четное число красных вершин (например,
$f(x_{1}, y_{1}, z) \oplus f(x_{2}, y_{1}, z) \oplus f(x_{1}, y_{2}, z) \oplus f(x_{2}, y_{2}, z) = 0$).
т. е., согласно доказанному выше утверждению, полученная раскраска удовлетворяет условию задачи. В силу того же утверждения эта раскраска единственна, так как для нее необходимо выполнение следующих условий:
$f(x, y, 0) = f(0, 0, 0) \oplus f(x, 0, 0) \oplus f(0, y, 0)$,
$f(x, 0, z) = f(0, 0, 0) \oplus f(x, 0, 0) \oplus f(0, 0, z)$
$f(0, y, z) = f(0, 0, 0) \oplus f(0, y, 0) \oplus f(0, 0, z)$
$ f(x, y, z) = f(0, 0, z) \oplus f(x, 0, z) \oplus f(0, y, z) = f(0, 0, z) \oplus f(0, 0, 0) \oplus f(x, 0, 0) \oplus f(0, 0, z) \oplus f(0, 0, 0) \oplus f(0, y, 0) \oplus f(0, 0, z) = f(x, 0, 0) \oplus f(0, y, 0) \oplus f(0, 0, z)$.
Таким образом, число искомых раскрасок равно
$2^{1 + 3 \cdot 1982} = 2^{5947}$.
