Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/circles/oim/stolymp/stolymp.pdf Дата изменения: Wed Oct 21 17:51:08 2009 Дата индексирования: Mon Feb 4 12:10:26 2013 Кодировка: koi8-r Поисковые слова: ngc 4676

СТУДЕНЧЕСКИЕ ОЛИМПИАДЫ И МЕЖКАФЕДРАЛЬНЫЙ СЕМИНАР НА МЕХМАТЕ МОСКОВСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА
В.И.Богачев, А.М.Райгородский, А.Б.Скопенков и Н.А.Толмачев
2

1

тику разумнее всего заниматься решением конкретно поставленных задач. А значит, умение решать сложные задачи является одним из важнейших для молодого математика. В этой заметке рассказывается о б опыте поддержания престижа умения решать трудные задачи, а также универсальности математического о бразования, при помощи студенческих математических олимпиад и межкафедрального семинара имени А. Н. Колмогорова на механикоматематическом факультете Московского Государственного Университета им. М. В. Ломоносова. Приводятся задачи олимпиад и семинара (тема `теорема Бэра' перенесена в [Sk]). Примерно с 2001 года на мехмате МГУ возо бновлена замечательная традиция проведения студенческих олимпиад. Отдельные кафедры проводят олимпиады и заочные конкурсы по теории вероятностей (http://mech.math.msu.su/probab/olimpia/olimpia.htm), геометрии и топологии (http://dfgm.math.msu.su/ les/skopenkov/geomolym.pdf [OS07]), алге бре (http://www.math.msu.su/department/algebra/olymp-06.html), анализу, механике, дифференциальным уравнениям и уравнениям с частными производными. Большинство этих соревнований проводятся для студентов 1-2 курса и помогают студенту выбрать кафедру. Проводятся также о бщематематические олимпиады | олимпиада, посвященная Пифагору (2004 и 2005, [AM]), и Заключительный тур всемехматовской олимпиады (с 2006; председатель жюри зав. отделением математики акад. РАН А. Т. Фоменко, зам. председателя жюри проф. В. И. Богачев). Важно, что при правильной организации студенческих олимпиад участие в них помогает (а не мешает) студенту начать научную работу [Sk03, Ef06]. Команда мехмата МГУ участвует в международной студенческой математической олимпиаде IMC (http://www.imc-math.org), когда это участие оплачивается спонсорами. С 2006 спонсором является Попечительский Совет мехмата МГУ, а руководителем команды Н. А. Толмачев. По бедители международных студенческих олимпиад регулярно получают приглашения учиться в престижнейших университетах мира, но, как правило, отказываются от них в пользу продолжения о бучения в Московском Государственном Университете. 3 Задачи заключительных туров | плод коллективного труда сотрудников мехмата МГУ (окончательные варианты задач готовятся В. И. Богачевым). Эти задачи приводятся ниже и в [ABZPRS]. Работы проверяют авторы этой заметки и другие сотрудники и аспиранты
Полный о бновляемый текст: http://dfgm.math.msu.su/ les/skopenkov/stolymp.pdf Авторы являются сотрудниками Московского Государственного Университета им. М. В. Ломоносова. Кроме того, А.М.Райгородский является сотрудником Московского Физико-технического Института и А.Б.Скопенков является сотрудником Независимого Московского Университета и Московского Института Открытого Образования. Адрес для замечаний: skopenko@mccme.ru 3 Составы команд: (2001) Лившиц Е., Никокошев И., Поярков А., Скопенков М. и Черепанов Е. (2006) Ефимов А. (гран-при), Калинин М. (1 премия), Козлов П. (1 премия) и Смирнов С. (3 премия) (Астахов В. прошел в команду, но не смог участвовать в олимпиаде). (2007) Астахов В. (1 премия), Баранов Д. (1 премия), Ефимов А. (гран-при), Перепечко А. (1 премия) и Смирнов С. (1 премия) (Прасолов М. и Абрамов Я. прошли в команду, но не участвовали в олимпиаде ввиду отсутствия загранпаспортов). (2008) Астахов В. (1 премия), Арутюнов В. (1 премия), Ефимов А. (гран-при), Смирнов С. (2 премия), Прасолов М. (грамота). (2009) Астахов В. (1 премия), Горинов Е. (1 премия), Девятов Р. (1 премия), Ефимов А. (гран-при), Кудык Н. (грамота), Перепечко А. (1 премия). В неофициальном командном зачете команда занимала II места в 2006{2008 годах и III место в 2009 году.
1 2

Аннотация. Великий ученый А. Н. Колмогоров говорил, что до тридцати лет матема-

Студенческие олимпиады.


мехмата МГУ. Мы приглашаем всех математиков передавать В. И. Богачеву задачи для олимпиад (не по электронной почте!). Отбор студентов мехмата на заключительный тур и на международную олимпиаду происходит по четко определенным и публично о бъявленным правилам, см. http://dfgm.math.msu.su/ les/skopenkov/rules.pdf. Призы ждут всех по бедителей Заключительного тура (в т.ч. не прошедших на международную олимпиаду). 4 Мы благодарим М. Скопенкова за полезные замечания, Д. Вельтищева и М. Вельтищева за предоставление компьютерных версий рисунков, а также А. Москвина, Р. Авдеева и С. Конягина за предоставление своих решений задач 1, 2 и 4 2006 года, соответственно. Традиция нео бязательных (про)семинаров для младшекурсников, направленных на изучение математики посредством решение задач и не являющихся узкоспециализированными, восходит к А.С. Кронроду (1950-е) и Е.М. Ландису (1970-е); наш семинар проводится с 2006 года. На нем решаются и разбираются интересные задачи: как простые ключевые, так и более трудные (в том числе олимпиадные и нерешенные). По формулировкам большинство задач доступно даже первокурсникам (знающим текущий лекционный материал), но решения многих из них сложны. Такие конкретные красивые задачи встречаются и на студенческих олимпиадах, и в научной работе. Эти задачи подо браны так, что в процессе их решения и о бсуждения участники познакомятся с важными математическими понятиями и теориями. Активные участники семинара познакомятся с идеями из разных о бластей математики (без долговременного изучения их языка). Изучение сложных вещей на простом языке поможет грамотно выбрать научное направление и руководителя. На семинаре о бсуждаются задачи из разных о бластей математики (этим наш семинар отличается от других). Занятия семинара о бъединяются в циклы из 1{2 занятий, связанных о бщей темой или идеей. Эти циклы независимы друг от друга (поэтому можно изучать только те циклы, которые студенту наиболее интересны). Тем более занятия каждого семестра не зависят от занятий прошлого семестра! Некоторые материалы лежат на http://dfgm.math.msu.su/materials.php. Некоторые занятия проводятся замечательными математиками, не являющимися соруководителями Семинара (весна 2006 | А. А. Черный, осень 2006 | А. А. Клячко мл. и В. Ю. Протасов, весна 2007 | А. Я. Белов-Канель и Э. Б. Винберг). Мы приглашаем всех математиков присылать руководителям предложения о проведении занятий Семинара. Семинар назван именем великого математика А.Н. Колмогорова, который начал свой путь в науку в 19 лет с решения трудной про блемы о рядах Фурье, а в дальнейшем внес выдающийся вклад в разные о бласти математики, тесно связанные с приложениями: теорию вероятностей, теорию динамических систем, гидродинамику и теорию сложности.

Межкафедральный семинар.

ранг матрицы порядка n > 2, все элементы которой, кроме элементов главной диагонали, не превосходит n - 2, то хотя бы три элемента на главной диагонали равны 1. (Э. Винберг?) 2001-3, 2006-4. Пусть k1 ; : : : ; kn | натуральные числа (не о бязательно различные). Доказать, что сумма абсолютных величин коэффициентов многочлена n=1 (1 - z kj ) не меньше j 2n. (С. Конягин)
По решению Оргкомитета Летней Школы 'Современная Математика' (http://www.mccme.ru/dubna) одним из призов является осво бождение всех кандидатов в команду (не более 12 человек) от оргвзноса для участии в этой школе (при условии своевременного заполнения анкеты). 5 После условия задачи в ско бках указывается фамилия предложившего, который не о бязательно является автором ; некоторые фамилии утрачены. Задачи второго тура олимпиады 2001 приводятся в [ABZPRS].
4

Задачи заключительных туров всемехматовских олимпиад. 5 2001-1. Докажите, что для любых чисел a и b если a > b > 0, то aba > bab : (П. Бородин) 2001-2. Нужна правильная формулировка от В. И. Богачева!!! Докажите, что если


dx = . (С. Конягин) 0 |f (x) - a| 2001-5. Существует ли такая постоянная C , что для любой непрерывно дифференцируемой на прямой действительной функции f , имеющей вторую производную, определенную всюду, кроме, может быть, конечного числа точек, условия |f (x)| 1 для всех x (-; ) и |f (x)f "(x)| 1 во всех точках существования f "(x) влекут неравенство |f (x)| C для всех x (-; )? 2001-6. Пусть G | группа нечетного порядка, не превосходящего 2001. Доказать, что существует такое множество S G, содержащее не более 20 элементов, что каждый элемент G есть произведение нескольких различных элементов множества S . 2006-1. Пусть f | неотрицательная непрерывная функция на [0; +), причем 0T f (x) dx f (x) T для всех T 0. Докажите, что функция имеет конечный интеграл по [0; +). 1 + x2 2006-2. Существуют ли два таких коммутирующих линейных оператора в R3 , что нет базиса, в котором матрицы о боих операторов имеют жорданову форму? (А. Ошемков и А. Скопенков) 2006-3. См. теорему Петерсена-Морли [Sk07', §3]. 2006-5. Дан набор 11-мерных векторов, у каждого из которых 5 нулевых и 6 единичных координат. Диаметр набора (т.е. максимум попарных расстояний между его точками) равен 8. (a) Какова максимальная возможная мощность такого набора? (б) Докажите, что данный набор можно разбить на не более чем 18 частей меньшего диаметра. (А. Райгородский) 2006-6. Дана бесконечно дифференцируемая функция f на R2 . Пусть U | такой открытый круг, что |f (x) - f (y )| |f (x) - f (y )| dx dy < ; где := 0 при x = y: 3 |x - y | |x - y |3 U

2001-4. Доказать, что для любой непрерывной на [0; 1] действительной функции f най1

дется такое число a, что

Докажите, что функция f постоянна на U . (В. Богачев) 2007-1. Пусть P | многочлен степени d на прямой со старшим коэффициентом 1. Докажите, что длина множества {t: |P (t)| c} не превосходит 2dc1=d . (В. Богачев) 2007-2. (i) В конечном множестве выбрано конечное число подмножеств, пересечение любых двух из которых содержит не менее двух элементов. Докажите, что элементы данного множества можно так раскрасить в два цвета, что бы никакое выбранное подмножество не было бы одноцветным. (ii) То же с заменой условия 'пересечение любых двух из которых содержит не менее двух элементов' на 'пересечение никаких двух из которых не может содержать ровно один элемент'. (А. Райгородский) 2007-3. Докажите, что для всякой вещественной матрицы A = (aij )i;jn выполнено неравенство | det(I + A)| exp trace A + 1 n =1 a2 : (неравенство Карлемана) ij 2 i;j 2007-4. Дана последовательность вещественных чисел an . Известно, что для всякого (1; 2) последовательность чисел a[n ] , имеет конечный предел. (Здесь [r] | целая часть числа r.) Обязана ли сходиться сама последовательность {an }? (А. Черный) 2007-5. Существует ли в трехмерном пространстве многогранник (не обязательно выпуклый), все грани которого | шестиугольники? Определение многогранника и его грани см. в [Do, стр.4. строка 2 снизу]. (М. Скопенков)


для любого t > 0. Для M > 0
M

Указания и решения к некоторым задачам всемехматовских олимпиад. 2006-1. Введем функцию g(T ) := 0T f (t)dt. Тогда из условия следует, что 0 g(t)
0



t

f (t)dt = 1 + t2

M

0

g (t)dt = 1 + t2

M

0

dg(t) g (t) M 2 = 1 + t2 |0 + 1+t

M

0

2tg(t)dt : (1 + t2 )2

Оценим этот интеграл. Первое слагаемое в последнем выражении стремится к нулю при M . Подынтегральная функция второго слагаемого положительна и ограничена инте2tg(t)dt 2t2 грируемой на [0; +) функцией: 0 . Значит, второе слагаемое имеет (1 + t2 )2 (1 + t2 )2 предел при M . Отсюда следует утверждение задачи. 2006-2. Ответ: да. Рассмотрим два линейных оператора, заданных в стандартном базисе следующими матрицами: 110 112 A = 0 1 0 ; B = 0 1 0 : 001 012 Непосредственно проверяется, что эти два оператора коммутируют. Предположим, что существует о бщий базис (e1 ; e2 ; e3 ), в котором о бе матрицы приводятся к жордановой форме. У матрицы B два со бственных значения 1 и 2, которым соответствуют со бственные вектора e1 = (; 0; 0)T и e3 = (2; 0; )T . Поскольку в жордановой форме матрицы B присутствует жорданова клетка размера 2 в 2 с со бственным значением 1 и e1 | единственный (с точностью до пропорциональности) со бственный вектор матрицы B c со бственным значением 1, то можно выбрать вектор e2 = ( ; ; ), для которого (B - E )e2 = e1 . Из этого равенства получаем e2 = ( ; -; )T . Заметим, что e1 и e3 | со бственные векторы оператора A, отвечающие со бственному значению 1. В жордановой форме матрицы A тоже присутствует клетка размера 2 в 2 с со бственным значением 1. Поэтому вектор (A - E )e2 = (-; 0; 0)T равен либо e1 , либо e3 . Это не так (поскольку = 0). Получили противоречие. 2006-4. Обозначим рассматриваемый многочлен через f (z ). Так как f (1) = 0, то r r f (z ) = z mj - z lj ; где никакое слагаемое из первой суммы не совпадает ни с каким j =1 j =1 слагаемым из второй. Поэтому искомая сумма модулей коэффициентов равна 2r. Далее, r rp f (1) = : : : = f (n-1) (1) = 0. Поэтому mp = lj ; p = 1; : : : ; n - 1: Значит, имеем соотj j =1 j =1 ветствующие равенства для элементарных симметрических многочленов: i (m1 ; : : : ; mr ) = i (l1 ; : : : ; lr ); i = 1; : : : ; n - 1. Если бы r n - 1, то наборы (m1 ; : : : ; mr ) и (l1 ; : : : ; lr ) совпадали бы с точностью до перестановки, и тогда f (z ) 0. Полученное противоречие показывает, что r n. 4 2006-5-a. Ответ: C10 . 11-мерный вектор, состоящие из 5 нулевых и 6 единичных координат, можно интерпретировать как 5-элементное подмножество 11-элементного множества. Каждому такому вектору можно сопоставить набор из номеров тех мест, на которых стоят нули. При этом на бору из 11-мерных векторов, диаметр которого равен 8, соответствует набор 5-элементных подмножеств 11-элементного множества, каждые два из которых пересекаются. Теперь вопрос можно переформулировать следующим о бразом: каково максимально возможное число 5-элементных подмножеств 11-элементного множества, любые два из которых пересекаются? 4 Примером из C10 таких подмножеств является набор 5-элементных множеств, содержащих элемент 11 множества Z11 := {1; 2; :::; 10; 11}.


Определим 5-элементные подмножества
As () := {(s); (s + 1); (s + 2); (s + 3); (s + 4)}; где S
11

и s Z11 :

Подмножество As () не пересекается ни с As+5 (), ни с As+6 (). Поэтому произвольный набор 5-элементных подмножеств 11-элементного множества Z11 , любые два из которых пересекаются, содержит не более пяти подмножеств из A1 (); A2 (); :::; A11 (). Всего 55 элементных подмножеств C11 . Значит, число 5-элементных подмножеств в нашем наборе не 5 C5 = C4 : превосходит 11 11 10 2006-5-b. Разо бьем множество всех 11-мерных векторов из нулей и единиц на 16 подмножеств следующим о бразом. Каждое подмножество определяется первыми четырьмя числами в первых четырех разрядах. Очевидно, что таких подмножеств ровно 16. Нетрудно проверить, что расстояние между любыми двумя векторами из пересечения одного подмножества с данным набором не превосходит 7 < 8. 2006-6. Для всякой дважды непрерывно дифференцируемой функции f разность f (y) - f (x) - f (x)(y - x) есть O(|x - y|2 ). Так как функция |x - y|-1 интегрируема на U в U ввиду интегрируемости функции |x|-1 на U (последнее легко проверить в полярных координатах), получаем интегрируемость |x - y|-3 f (x)(y - x) на U в U . По теореме Фубини при почти каждом x U функция y |x - y|-3 f (x)(y - x) интегрируема по U . Заметим, что это возможно лишь при f (x) = 0. Для этого достаточно проверить, что для ненулевого вектора v функция z |z |-3 (v; z ) не интегрируема в окрестности нуля. Действительно, поворотом системы координат приходим к случаю, когда v = ce1 , e1 = (1; 0). В полярных координатах интеграл модуля указанной функции есть интеграл от cr-1 | cos | по (0; r0 ) в [0; 2], т.е. бесконечен. Итак, f (x) = 0 при почти всех x U , откуда f (x) = 0 в U , т.е. f { постоянная. Комментарий к задаче 2006-6. Доказанное легко о бо бщить на случай, когда от f тре буется лишь измеримость (этот случай значительно более сложным спосо бом был рассмотрен в [Br02]). Такой более о бщий случай сводится к случаю гладкой функции f с помощью сверток f (x) = U f (x + u)%(u) du; x (1 - )U; (0; 1); где % { неотрицательная гладкая функция с носителем в U и интегралом 1. Остается заметить, что при фиксированном " > 0 и < " интегралы от |x - y|-3 |f (x) - f (y)| по (1 - ")U в (1 - ")U конечны (тогда функции f постоянны в (1 - ")U , значит, их предел f равен почти всюду некоторой постоянной). Это ясно из оценки
|
(1-")U

f (x) - f (y)| dx dy |x - y |3

|
U

f (x) - f (y)| dx dy; |x - y |3

получаемой непосредственно из определения f с учетом того, что x + u; y + u U при x; y (1 - ")U , u U , < ". 2007-5. Ответ: существует. Основная идея состоит в том, что бы искать тре буемый многогранник среди невыпуклых (и даже не гомеоморфных шару) многогранников. Вот набросок только одной из возможных конструкций "тороо бразного" многогранника, удовлетворяющего условию. Возьмем многранник в форме "рамки", то есть о бъединение четырех усеченных четырехугольных пирамид, с подходящим о бразом склеенными боковыми гранями. Он имеет 16 четырехугольных граней. Что бы получить искомый многогранник, нужно теперь выбрать подходящим о бразом 8 попарно несмежных ре бер и "срезать" их малые окрестности (а для тех ре бер, двугранные углы при которых больше , нужно, нао борот, "нарастить" многранник). Получим 8 новых шестиугольных граней и из каждой четырехугольной грани получим шестиугольную, то есть у построенного многогранника все грани будут шестиугольниками. Замечание. Очевидный подсчет эйлеровой характеристики показывает, что не существует выпуклого многогранника с тре буемым свойством.


Иными словами,

Про блема Борсука. Универсальные покрышки. (А.М. Райгородский) Про блема Борсука. Требуется найти минимальное число f (n) частей меньшего диаметра, на которые может быть разбито произвольное множество диаметра 1 в Rn .
=
1 : : : f

f (n) = max min{f :

; diam

i

< diam для любого i}; где diam = sup |x-y|:
x;y


шестиугольником с расстоянием 1 между параллельными сторонами. (b) Разбейте шестиугольник из (a) на три части диаметра 23 . Выведите отсюда справедливость гипотезы Борсука на плоскости. (c) (неулучшаемость результата (b)). Приведите на плоскости пример такой фигуры диаметра 1, которую нельзя разбить на три части диаметра < 23 . 2. Разбейте трехмерный шар на четыре части диаметра (а) < 1, (b) = 3+6 3 . 3. Разбейте n-мерный шар на n + 1 часть диаметра (а) < 1, (b) как можно меньшего диаметра. 4. (a) Докажите теорему Юнга: всякое множество Rn диаметра 1 покрывается шаром радиуса 2nn [DGK68]. +2 (b) Выведите из теоремы Юнга, что f (n) 2n . 5*. Теорема Борсука - Люстерника - Шнирельмана. Докажите, что (a) трехмерный шар нельзя разбить на три части меньшего диаметра [BG65]. (b) n-мерный шар нельзя разбить на n частей меньшего диаметра [LS30]. Для изучения функции f (n) уже оказалось полезным следующее понятие. Множество U Rn называется универсальной покрышкой, если для любого множества Rn диаметра 1 существует такое движение ', что '(U ). Задача 1a означает, что в качестве универсальной покрышки в R2 можно взять правильный шестиугольник с расстоянием 1 между параллельными сторонами. 6. (a) Докажите, что универсальной покрышкой (в Rn ) является множество B1 B2 Rn , где B1 | шар радиуса 2nn и B2 | шар радиуса 1 с центром на границе шара B1 . +2 (b) Выведите из (a), что f (n) 2n-1 + 1. (c)* Можно ли в какой-нибудь размерности уточнить результат (b)? (d)* Докажите, что множество B1 B2 нельзя разбить на 4 части меньшего диаметра. 7. (a) Докажите, что правильный октаэдр является универсальной покрышкой в размерности 3, если расстояние между его параллельными гранями равно 1 (т.е. если октаэдр задается уравнением |x| + |y| + |z | 3=2). (b) Отсечем от октаэдра из (a) в трех взаимно перпендикулярных направлениях три пирамиды; отсечения производятся посредством плоскостей, параллельных координатным и отстоящих от начала координат на расстояние 0.5. Докажите, что полученный 11-гранник U1 является универсальной покрышкой. (c) Разбейте 11-гранник U1 на 4 части диаметра < 1. Выведите отсюда справедливость гипотезы Борсука в пространстве. (d) Разбейте 11-гранник U1 на 4 части диаметра 0:9888. 8*. Ромбододекаэдром зазывается многогранник, являющийся выпуклой о болочкой множества точек в R3 вида (±1; ±1; ±1) (восемь вершин) и (0; 0; ±2) (шесть вершин). Это двенадцатигранник, грани которого суть ромбы. (a) Докажите, что в качестве универсальной покрышки в R3 можно взять ромбододекаэдр, у которого расстояние между любыми двумя параллельными гранями равно 1.

Гипотеза Борсука. f (n) = n + 1 [BG65, Sk96, Ge99, Sk99, Ra01, Ra04, Ra06]. 1. (a) Докажите, что каждое множество R2 диаметра 1 покрывается правильным


(b) отсечь (c) (d)

Докажите, что данный от него "шапочки" по т Разбейте множество без Разбейте множество без

ромбододекаэдр останется универсальной покрышкой, если ому же принципу, что и в задаче 7b. шапочек из (a) на 4 части диаметра < 1. шапочек из (a) на 4 части диаметра 0:98.

Многогранники U1 и U

2

кая от правильного октаэдра шесть пирамид шестью плоскостями, параллельными диагональным сечениям октаэдра. Три из этих плоскостей (взаимно перпендикулярные) проходят на расстоянии 0.5 от центра октаэдра, три остальные плоскости (тоже взаимно перпендикулярные) | на расстоянии 0.525. (a) Докажите, что для любого множества R3 диаметра 1 существует такое движение ', что либо '(U1 ), либо '(U2 ). (b) Разбейте каждое из множеств U1 ; U2 на 4 части диаметра < 1. (c) Разбейте каждое из множеств U1 ; U2 на 4 части диаметра 0:9843. 10*. Про блема Гэйла. Существует ли множество в R3 , которое нельзя разбить на 4 части диаметра < 0:9? 11*. Верна ли гипотеза Борсука (а) в R4 , (b) для конечных наборов точек в R4 ? 12*. Назовем множество точек двухдистанционным, если расстояние между любыми двумя его элементами принадлежит некоторому множеству {a; b}. Верна ли гипотеза Борсука для двухдистанционных множеств (а) в R4 , (b) в Rn ? Задачи 10, 11 и 12b являются нерешенными. 13. [YB51] Выпуклое множество Rn называется множеством постоянной ширины, если расстояние между любыми двумя его параллельными опорными гиперплоскостями (т.е. прямыми для n = 2) одно и то же. Примеры: круг, треугольник Рело. (a) Докажите, что любое выпуклое множество R2 диаметра 1 покрывается множеством постоянной ширины 1 (и, как следствие, диаметра 1). (b) То же с заменой R2 на Rn . (c) Докажите теорему Ленца: n-мерное множество постоянной ширины нельзя разбить на n частей меньшего диаметра. 14. Про блема Грюнбаума. [Gr71] Требуется найти минимальное число g(n) (открытых) шаров диаметра 1, которыми может быть покрыто произвольное множество диаметра 1 в Rn . Иными словами,
g(n) = max min{g :


9. 11-гранник U1 определен в задаче 7b. Определим многогранник U2 аналогично, отсе-

B1 : : : Bg ; diam Bi = diam для любого i}:


(a) Найдите g(2). (b) Найдите или оцените g(3). (с) Докажите, что при достаточно большом n выполнено неравенство g(n) > n + 1. Найдите как можно меньшее значение размерности n, в которой это так. (d) Докажите, что g(n) > n + 1 при n 4. (e)* Докажите, что для g(n) > сn для некоторого c > 1.

треугольник Рело

торое число t > 0. Двое - До бытчик и Повторитель - играют в игру, которую мы о бозначим E H R(G; H; t). Всего в игре t раундов. На каждом раунде сперва делает ход До бытчик, затем настает черед Повторителя. Всякий раз До бытчик выбирает по своему усмотрению один из двух графов и из множества его вершин извлекает какую-нибудь одну. Таким о бразом, на i - ом раунде игры До бытчик, делая свой ход, берет либо произвольную вершину xi V , либо произвольную вершину yi W . Повторитель вслед за До бытчиком также должен достать из какого-то графа некоторую его вершину; только у него уже нет такой сво боды выбора, как у До бытчика, и свою вершину он о бязан брать из графа G, коль скоро его противник воспользовался графом H , и нао борот. В конечном итоге выбранными окажутся x1 ; : : : ; xt V и y1 ; : : : ; yt W . Мы скажем, что Повторитель выиграл, если ему удалось так "скопировать" действия До бытчика, что бы графы G|{x1 ;:::;xt } и H |{y1 ;:::;yt } были "упорядоченно изоморфны". Здесь G|{x1 ;:::;xt } = ({x1 ; : : : ; xt }; E ), так что (xi ; xj ) E тогда и только тогда, когда (xi ; xj ) E . Графы упорядоченно изоморфны, коль скоро условие (xi ; xj ) E равносильно условию (yi ; yj ) F . 1. Пусть в графе G есть изолированная вершина, а в графе H таких вершин нет. Докажите, что у До бытчика всегда имеется выигрышная стратегия в игре E H R(G; H; 2). 2. Пусть граф G содержит K4 (полный подграф на четырех вершинах). Предположим, что в H таких подграфов нет. При каком минимальном t у До бытчика заведомо есть выигрышная стратегия в игре E H R(G; H; t)? 3. Пусть граф G содержит K5 . Допустим, граф H планарен. Существует ли t, при котором у До бытчика всегда есть выигрышная стратегия в игре E H R(G; H; t)? Определение радиуса графа. Назовем расстоянием между двумя вершинами x; y графа G = (V ; E ) длину d(x; y ) кратчайшего ре берного пути, соединяющего эти вершины. Для x V о бозначим e(x) = max d(x; y ). Радиусом графа G называется r(G) = min e(x). y V xV 2, а выигрышная стратегия 5. Для каждого t > выигрышная стратегия


Графы и игры. А.М. Райгородский Игра Эренфёйхта. Даны графы G = (V ; E ) и H = (W; F ). Также фиксировано неко-

4. Пусть r(G)

r в 0 в

(H ) > 2. Существует ли t, при котором у До бытчика всегда есть игре E H R(G; H; t)? постройте примеры таких графов G; H , что у Повторителя есть игре E H R(G; H; t).


Язык первого порядка для графов. Алфавит языка первого порядка для описания тех или иных свойств графов состоит из символов x; y; : : :, о бозначающих вершины графа. Далее, имеются значки " = " и " "; здесь под x y подразумевается смежность вершин x; y. Есть также стандартные логические символы типа кванторов и , импликации, конъюнкции, дизъюнкции, отрицания и пр. Фразы должны быть конечными. 6. Запишите свойство "граф имеет изолированную вершину" на языке первого порядка. 7. Запишите свойство "граф содержит K4 " на языке первого порядка. 8. Запишите свойство "граф имеет радиус 2" на языке первого порядка. 9. Можно ли записать на языке первого порядка свойство "граф связен"? 10. Можно ли записать на языке первого порядка свойство "граф не планарен"? 11*. Докажите, что если граф G обладает свойством A, которое можно записать на языке первого порядка, а граф H этим свойством не о бладает, то существует t = t(A), при котором До бытчик заведомо располагает выигрышной стратегией в игре E H R(G; H; t). Cлучайные графы. Для каждого целого положительного n положим Vn = {1; : : : ; n} и зафиксируем p = p(n) (0; 1). Рассмотрим вероятностное пространство ( n ; Bn ; P2n ), в 2 котором n = {G = (Vn ; E )}, так что | n | = 2Cn , Bn = 2 n и Pn (G) = p|E | (1 - p)Cn -|E | . Назовем произвольный элемент из n случайным графом в модели G(n; p). Можно понимать это так: в случайном графе на данных n вершинах ре бра проводятся независимо друг от 2 друга с вероятностью p. Иными словами, речь идет о схеме Бернулли с Cn независимыми испытаниями. Найти вероятность того, что случайный граф G n о бладает некоторым свойством A, - это то же самое, что найти вероятность множества B Bn всех графов G n , которые этим свойством о бладают. Мы скажем, что G о бладает свойством A (асимптотически) почти наверное (п.н.), если limn Pn (G о бладает свойством A) = 1. 1 12. Докажите, что при p = o n граф п.н. двудолен. 1 13. Докажите, что при p = o n граф п.н. не содержит треугольников. 14. Докажите, что при p 3 log n граф п.н. связен. n 15. Пусть дана функция p = p(k) (0; 1), G - случайный граф в модели G(n; p(n)), а H случайный граф в модели G(m; p(m)). Пусть, далее, A - некоторое свойство графа, которое можно записать на языке первого порядка. Предположим, наконец, что для данного p и для произвольного фиксированного t выполнено
n

lim m P (Повторитель имеет выигрышную стратегию в игре E H R(G; H; t)) = 1: lim

С помощью результата задачи 11 докажите, что тогда свойство A либо п.н. выполнено, либо п.н. не выполнено. 16. Скажем, что граф G = (V ; E ) о бладает свойством Fs (где s | целое положительное), если для любых натуральных a; b, a + b s, и для произвольных u1 ; : : : ; ua ; v1 ; : : : ; vb V найдется такая вершина x V , что x смежна с каждой вершиной ui , i = 1; : : : ; a, и x не смежна ни с одной из вершин vj , j = 1; : : : ; b. Предположим, что графы G и H о бладают свойством Fs . Докажите, что тогда Повторитель заведомо располагает выигрышной стратегией в игре E H R(G; H; t) c любым t s. 17. Докажите, что при p = const и s = const п.н. граф о бладает свойством Fs . 18. C помощью результатов задач 15, 16 и 17 докажите, что при любом постоянном p имеет место закон нуля и единицы для свойств графов, которые записываются на языке первого порядка: такое свойство либо п.н. выполнено, липо п.н. не выполнено. 19*. Докажите, что при p = n- , Q, не всегда имеет место закон нуля и единицы для свойств графов, которые записываются на языке первого порядка. (Нужно привести


пример числа , а также некоторого свойства, асимптотическая вероятность которого в модели G(n; p) не есть ни 0, ни 1.) 20**. Докажите, что результат задачи 18 верен при всех p = n- , Q. Многие книги из этого списка можно найти на http://ilib.mccme.ru/. Журнал Мат. Просвещение: www.mccme.ru/free-books/matprosa.html [ABZPRS] И. В. Аржанцев, В. И. Богачев, А. А. Заславский, В. Ю. Протасов, А. М. Райгородский, А. Б. Скопенков, Студенческие олимпиады мехмата МГУ, Мат. Посвещение, 2010, http://dfgm.math.msu.su/ les/skopenkov/mechm.pdf [AM] Р. Авдеев и А. Москвин, Мат. Посвещение, 2008. [AS00] N. Alon and J. Spencer, The probabilistic method, Wiley - Interscience Series in Discrete Math. and Optimization, Second Edition, 2000. [BG65] В.Г. Болтянский и И.Ц. Гохберг, Теоремы и задачи комбинаторной геометрии, Москва, "Наука", 1965. [Bo01] B. Bollob Random Graphs, Cambridge Univ. Press, Second Edition, 2001. as, [Br02] Брезис Х. Как распознать постоянные функции. Связь с пространствами Со болева. Успехи мат. наук. 2002. T. 54, N 4. C. 59{74. [DGK68] Л. Данцер, Б. Грюнбаум и В. Кли, Теорема Хелли, Москва, "Мир", 1968. [Do] Н. П. Долбилин, Жемчужины теории многогранников. [Ef06] A. E mov, The asymptotics for the number of real roots of the Bernoulli polynomials, arXiv:math/0606361. [ES76] П. Эрдеш и Дж. Спенсер, Вероятностные методы в комбинаторике, Москва, "Мир", 1976. [Gr71] Б. Грюнбаум, "Этюды по комбинаторной геометрии и теории выпуклых тел", Москва, "Наука", 1971. [Ge99] М. Л. Гервер, Про блема Борсука, Мат. Просвещение 3 (1999) [LS30] Л.А. Люстерник и Л.Г. Шнирельман, Топологические методы в вариационных задачах, М., 1930. [OS07] А. Ошемков и А. Скопенков, Олимпиады по геометрии и топологии, Мат. Просвещение, 11 (2007), 131-140. [Ra01] А.М. Райгородский, Проблема Борсука и хроматические числа некоторых метрических пространств, Успехи Матем. Наук, Т. 56 (2001), Вып. 1, стр. 107 - 146. [Ra04] A.M. Raigorodskii, The Borsuk partition problem: the seventieth anniversary, Mathematical Intelligencer, V. 26 (2004), N4, 4 - 12. [Ra06] А.М. Райгородский, Проблема Борсука, Москва, МЦНМО, 2006. [Sk96] A. Skopenkov, Borsuk's problem, Quantum, 7:1 (1996) 16{21, 63 [Sk99] А. Скопенков, N -мерный куб, многочлены и решение про блемы Борсука, Мат. Просвещение, 3 (1999) 184{188 [Sk03] M. Skopenkov, On approximability by embeddings of cycles in the plane, Topol. Appl. 134 (2003) 1{22. [Sk07] A. Skopenkov, A characterization of submanifolds by a homogeneity condition, Topol. Appl. 154 (2007) 1894-1897, http://arxiv.org/abs/math.GT/0606470 [Sk07'] М. Скопенков, Теорема о высотах треугольника и тождество Яко би, Мат. Просвещение, сер. 3, вып. 11, 2007, 86{88. [Sk] А. Скопенков, Объемлемая однородность, представлено к публикации. [YB51] И.М. Яглом и В.Г. Болтянский, Выпуклые фигуры, Гостехиздат, М., 1951.

Литература