Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/circles/oim/materials/spring06/steel/s06-raig.ps Дата изменения: Sun Apr 16 11:39:00 2006 Дата индексирования: Sun Dec 23 01:26:17 2007 Кодировка: koi8-r

Задачи комбинаторной геометрии
А.М. Райгородский
1. В группе школьников 20 человек. Из них 5 человек одинаково хорошо и лучше всех остальных
решают задачи по комбинаторике, 5 - по комбинаторной геометрии, 5 - по классической геометрии, 5
- по теории чисел и т.д. (всего 18 предметов, так что, очевидно, некоторые школьники в равной мере
сильны в нескольких дисциплинах). Требуется составить из этих школьников команду для участия в
олимпиаде. При этом хочется, чтобы для каждого предмета в команде нашелся специалист в нем и
чтобы размер команды был как можно меньше.
а) Докажите, что всегда есть команда из < 14 человек. б) Докажите, что всегда есть команда из
семи человек. в) Докажите, что при некотором раскладе заведомо нужно взять в команду четверых.
г) шестерых. д) Можно ли улучшить результат пункта б), т.е. всегда ли удастся собрать команду
из шестерых школьников?
2. Рассмотрим в двадцатимерном пространстве некоторое множество точек V , содержащееся в мно-
жестве :
V #  = {x = (x 1 ; : : : ; x 20 ) : x i # {0; 1}; i = 1; : : : ; 20; x 1 + : : : + x 20 = 5}:
Иными словами, V - это произвольный набор точек, координаты которых суть 0 или 1, причем единиц
у каждой точки ровно 5. Допустим, |V | = 20. Соединим точки x; y # V отрезком, если расстояние
между ними есть # 10. Докажите, что все наши точки можно так раскрасить в 7 цветов, чтобы концы
любого отрезка были разноцветными.
3. Рассмотрим в десятимерном пространстве некоторое множество точек V , содержащееся в множе-
стве :
V #  = {x = (x 1 ; : : : ; x 10 ) : x i # {0; 1}; i = 1; : : : ; 10; x 1 + : : : + x 10 = 5}:
Иными словами, V - это произвольный набор точек, координаты которых суть 0 или 1, причем единиц
у каждой точки ровно 5. Допустим, |V | = 20. Соединим точки x; y # V отрезком, если расстояние
между ними есть # 8. Докажите, что все наши точки можно так раскрасить в 9 цветов, чтобы концы
любого отрезка были разноцветными.
4. Рассмотрим в n - мерном пространстве репер E = {e 1 ; : : : ; e n }, состоящий из векторов
e 1 = (1; 0; 0; : : : ; 0); e 2 = (0; 1; 0; : : : ; 0); : : : ; e n-1 = (0; : : : ; 0; 1; 0); e n = (0; : : : ; 0; 0; 1):
Возьмем множество всех целочисленных комбинаций векторов из E , т.е. множество вида { 1 e 1 + : : : +
 n e n }, где  1 ; : : : ;  n # Z. Такое множество называется целочисленной решеткой и обозначается Z n .
Пусть a 1 ; : : : ; a t - это векторы, у которых все координаты рациональны. Положим
 =  a1 ;:::;a t
= { 1 a 1 + : : : +  t a t + b};  1 ; : : : ;  t # Z; b # Z n :
Обозначим через d n (E ; ) величину
d n (E ; ) = min {d : найдутся такие векторы e i 1
; : : : ; e i n-d # E и такие векторы b 1 ; : : : ; b d # ; что
 = { 1 e i 1
+ : : : +  n-d e i n-d +  1 b 1 + : : : +  d b d };  i ;  j # Z}:
Эта величина называется дефектом репера E относительно , и словами можно сказать так: де-
фект - это минимальное количество векторов, которые необходимо удалить из репера с тем, чтобы
оставшаяся система векторов могла быть дополнена до базиса (см. [2]) в .
а) Докажите, что для любого d # {0; 1; 2} найдется такой вектор a, что d 2 (E ;  a ) = d. б) Докажите
аналогичное утверждение в произвольной размерности. в) Пусть O n = {x = (x 1 ; : : : ; x n ) : |x 1 | +
: : : + |x n | # 1} - единичный n - мерный октаэдр. Докажите, что существует t и такой набор векторов
a 1 ; : : : ; a t , для которого  a1 ;:::;a t #O n = {O; ±E} (O - начало координат) и d n (E ;  a1 ;:::;a t ) # n-10 log 2 n.
г) Пусть # 15 = {1; : : : ; 15} - множество из пятнадцати элементов. Возьмем произвольную совокупность
мощности 14, состоящую из некоторых (различных) шестиэлементных подмножеств (сочетаний) в # 15 .
Обозначим эту совокупность M = {M 1 ; : : : ; M 14 }. Рассмотрим какие-нибудь несовпадающие простые
числа p 1 ; : : : ; p 14 : например, p 1 = 2; p 2 = 3; p 3 = 5; p 4 = 7 и т.д. Положим q i = p 1
1 · p 2
2 · : : : · p 14
14 , где
  = 1, если i # M  ,   = 0 в противном случае ( # {1; : : : ; 14}; i # # 15 ). Обозначим a = # 1
q1
; : : : ; 1
q15 # .
Докажите, что d 15 (E ;  a ) # 5.

Выход на серьезную науку
[1] Хроматическим числом графа G = (V; E) называется величина (G), равная минимальному коли-
честву цветов, в которые можно так покрасить V , чтобы вершины, соединенные ребрами, были
разноцветны. В задачах 2 и 3 речь идет как раз о хроматическом числе графа расстояний, т.е.
графа, вершины которого суть точки пространства, а ребра - отрезки определенной длины, со-
единяющие некоторые из этих точек.
1.1. Докажите, что хроматическое число любого графа расстояний конечно и как можно точнее
оцените его.
1.2. Докажите, что хроматическое число любого двумерного графа расстояний не превосходит
семи.
1.3. Пусть V # {0; 1} n , а E порождено теми и только теми парами точек из V , квадрат расстояния
между которыми равен k. Докажите, что (G) # 2 n-k+1 , коль скоро G = (V; E).
[2] Решеткой называется совокупность точек в пространстве, являющихся целочисленными комби-
нациями некоторых линейно-независимых векторов. Сами эти векторы образуют базис в решетке.
Вообще говоря, базис в решетке не единственен. Множество  из четвертой задачи - решетка.
Объем фундаментальной ячейки решетки  называется ее определителем и обозначается det .
2.1. Докажите, что если  - решетка,
а
- выпуклое n - мерное тело, симметричное относительно
начала координат, причем
объем
строго больше 2 n det , то
в
есть по крайней мере две
точки решетки .
2.2. Докажите, что если a = # a1
q
; : : : ; an
q # и НОД(a 1 ; : : : ; a n ; q) = 1, то det  a = 1
q
.
2.3 # . Докажите, что, каков бы ни был вектор a, d n (E ;  a ) # c n
log n
(log log n) 2 , коль скоро  a #O n =
{O; ±E}.