Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/circles/oim/stolymp/mechm.pdf Дата изменения: Sat Oct 24 05:33:38 2009 Дата индексирования: Mon Feb 4 09:08:51 2013 Кодировка: koi8-r Поисковые слова: stonehenge

СТУДЕНЧЕСКИЕ ОЛИМПИАДЫ МЕХМАТА МГУ И. В. Аржанцев, 1 В. И. Богачев, 2 А. А. Заславский, 3 В. Ю. Протасов, 4 А. М. Райгородский, 5 А. Б. Скопенков

6

n=1

Мы приводим задачи всемехматовских олимпиад 2001 (второй тур), 2008 и 2009 годов, а также указания, решения и комментарии. 7 См. введение в [BRST]. Благодарим Д. Янга за полезное замечание. 2001-1. Пусть ' : [0; +) [0; +) - монотонно убывающая функция, для которой '(n) < . Докажите, что существует последовательность n положительных чисел, монотонно убывающая к нулю, для которой



2001-2. Докажите, что для любого целого положительного n матрица
211 0 2 1 111
n

n=1

'( n n) < .

имеет два равных элемента на главной диагонали. 2001-3. Пусть Pn и Qn | правильные n-угольники, причем Pn вписан в круг диаметра 1, а Qn описан около этого круга. Обозначим через pn и qn их периметры. В какой трети интервала (pn ; qn ) лежит число ? 2001-4. Для любых целых p и обозначим через J (; p) число целочисленных решений (x1 ; : : : ; x6 ) уравнения x3 + x3 + x3 = x3 + x3 + x3 + , для которых 1 x1 ; : : : ; x6 p. Докажите, 1 2 3 4 5 6 что J (; p) J (0; p) для любого p. 2001-5. Пусть P | полином третьей степени, для которого множество L = {z C : |P (z )| = 1} не совпадает с окружностью S = {z C : |z | = 1}. Каково наибольшее возможное количество точек в пересечении L S (для различных полиномов P ???)? 2001-6. Можно ли покрыть пространство Rn семейством замкнутых шаров с положительными радиусами и попарно непересекающимися внутренностями?

2001-7. Докажите, что ряд
1 2 3 4



n=1

sin(2n x) сходится только в точках x = 2-k , k Z.

arjantse@mccme.ru; механико-математический факультет Московского Государственного Университета. vibogach@mail.ru; механико-математический факультет Московского Государственного Университета. zaslavsky@mccme.ru; Центральный Экономико-Математический Институт v-protassov@yandex.ru; механико-математический факультет Московского Государственного Университета. 5mraigor@yandex.ru; механико-математический факультет Московского Государственного Университета, факультет инноваций и высоких технологий Московского Физико-технического Института. 6skopenko@mccme.ru; http://dfgm.math.msu.su/people/skopenkov/papersc.ps. механико-математический факультет Московского Государственного Университета, Независимый Московский Университет и Московский Институт Открытого Образования. 7Вот по бедители этих олимпиад: А. Авилов (2009), В. Арутюнов (2008), В. Астахов (2008, 2009), А. Буфетов (2009), А. Гаврилюк (2009), Е. Горинов (2009), Р. Гимадеев (МФТИ, 2009), Р. Девятов (2008, 2009), А. Ефимов (2008), М. Илюхина (2008), А. Киселев (МФТИ, 2009), П. Козлов (2009), И. Митрофанов (2008), П. Мищенко (МФТИ, 2009), А. Перепечко (2009), С. Смирнов (2008), А. Трепалин (2008), В. Шмаров (2009). А вот кто предложили задачи на олимпиады: И. В. Аржанцев (2008-3), В. И. Богачев (2008-1, 2008-2, 20095), А. А. Заславский (2008-4, 2009-3), В. Ю. Протасов (2009-1), А. М. Райгородский (2008-5, 2009-2), А. Б. Скопенков (2008-3, 2009-4). В [BRST] приведены задачи первого тура олимпиады 2001 года, а задачи второго тура ошибочно названы утраченными. Большинство задач второго тура олимпиады 2001 | фольклорные. Фамилии авторов остальных задач утрачены, за что мы приносим свои извинения. Все варианты составлены В. И. Богачевым.
1


2001-8. Пусть { n } | последовательность вещественных чисел, для которой последовательность функций sin( n x) сходится на множестве, имеющем положительную меру Ле бега. Докажите, что последовательность { n } имеет конечный предел. 2001-9. Найдите все выпуклые равноугольные многоугольники с вершинами в узлах целочисленной решетки на плоскости. 2008-1. Докажите, что для всякого n найдется число cn > 0 со следующим свойством: каждое открытое выпуклое множество о бъема v в единичном шаре из Rn содержит шар радиуса cn v. 2008-2. Для возрастающих функций f ; g : [0; =2] R докажите неравенство 8
=2

2008-3. Обозначим через A подгруппу Z2 0 0 группы Z4 . Для каких элементов (b1 ; b2 ; c1 ; c2 ) Z4 существует такая подгруппа D группы Z4 , что (b1 ; b2 ; c1 ; c2 ) D и Z4 =

0

f (x)g (x) sin x dx

=2

0

f (x) sin x dx

=2

0

g (x) sin x dx:

A D? Дайте ответ в терминах делимости чисел b1 ; b2 ; c1 ; c2 и наибольших о бщих делителей подмножеств этого множества. 9 2008-4. Докажите, что существует выпуклая ограниченная фигура на плоскости, не имеющая центра симметрии, но о бладающая следующим свойством: всякая прямая, делящая пополам ее периметр, делит пополам и ее площадь. 2008-5. Пусть W | 11n -элементное подмножество пространства Rn , любое 10n -элементное подмножество которого содержит две точки x; y на расстоянии 1: |x - y| = 1. Докажите, что для достаточно большого n количество единичных расстояний между точками множества W больше, чем 0; 99 · 12:1n : 1 #{(x; y) Wn в Wn : |x - y| = 1} > 0; 99 · 12:1n ; 2 где через #A о бозначено число элементов в множестве A. 10 2009-1. Для каких размерностей n существует гиперплоскость в Rn , пересекающая все (n - 1)-мерные замкнутые грани n-мерного куба, но не имеющая о бщих точек со вписанным в этот куб замкнутым шаром? 11 2009-2. Обозначим через m(k) максимальное число попарно не ортогональных векторов из {-1; 0; 1}2k , ровно k координат каждого из которых нулевые. (а) Докажите, что m(k) 22k-1 при нечетном k. (б) Докажите, что 80 m(4) 140. 2009-3. Пусть n нечетно. 12 На сторонах произвольного (`первого') n-угольника как на основаниях построены во внешнюю сторону равно бедренные треугольники с углом при вершине 2=n. Их вершины о бразуют второй n-угольник. На его сторонах как на основаниях построены во внешнюю сторону равно бедренные треугольники треугольники с углами при вершине 4=n. Их вершины о бразуют третий n-угольник. Аналогично из k-го n-угольника
Общий результат принадлежит П.Л. Че быш еву. Неравество Че быш из `элементарной' математики | ева дискретный аналог этого неравенства. 9Аналогично решается следующая более о бщая задача. Пусть A есть прямая сумма сво бодных абелевых конечно порожденных подгрупп B и C . Для каких элементов (b; c) A найдется такая подгруппа D A, что (b; c) D и A = B D? 10На олимпиаде задача предлагалась в несколько другой формулировке. Хотя это и не о бязательно для формулировки или решения задачи, заметим, что для достаточно большого n такое подмножество W действительно существует. Это доказывается аналогично [R, стр. 16, §2.3, первые две выключные формулы]. 11Эта задача интересна как еще один пример того, что в высоких размерностях вписанный в куб шар `маленький'. 12Имеется естественный аналог этой задачи для четного n.
8Здесь можно заменить sin x на любую интегрируемую функцию % : [0; =2] [0; +) с интегралом 1.


при помощи угла 2k=n строится (k + 1)-й n-угольник; равно бедренные треугольники строятся вовне k-го n-угольника при 2k=n < и внутрь при 2k=n > . Докажите, что (n - 1)-й n-угольник правильный. 2009-4. Докажите, что всякое линейное ото бражение в се бя пространства матриц n в n с комплексными коэффициентами, сохраняющее определитель, является о братимым. 2009-5. Для непрерывной функции f : R2 [0; +), некоторого C > 0, любого квадрата K с единичным ре бром и любого x K выполнено неравенство f (x) C + C K f (x) dx: Докажите, что f (x) M eC x при некотором M 0. 13 размерности n - 1. Можно считать, что данное тело K компактно (взяв выпуклое компактное подмножество исходного тела о бъема более v=2). Пусть a = min{xn : (x1 ; : : : ; xn ) K }; b = max{xn : (x1 ; : : : ; xn ) K }; l = b - a: Среди сечений Kt := {(x1 ; : : : ; xn-1 ) : (x1 ; : : : ; xn-1 ; t) K } возьмем сечение максимального (n - 1)-мерного о бъема. Пусть это сечение Kc , где a c b, а соответствующий (n - 1)-мерный о бъем равен v0 . Можно считать, что b - c l=2. По предположению индукции в Kc есть (n - 1)-мерный шар B с центром в Z = (z1 ; : : : ; zn-1 ; c) радиуса r = cn-1 v0 . По построению в K есть точка X = (x1 ; : : : ; xn-1 ; b). Положим Y = (x1 ; : : : ; xn-1 ; c). Ввиду выпуклости тела K конус Q с вершиной в X и основанием B входит в K . Проверим, что он содержит нужный шар. Заметим, что |Z - Y | 2. 1 1 rl rl: Пусть |Z - Y | l. Тогда указанный конус Q содержит шар радиуса % = 4 |Z - Y | 8 Это видно из прямоугольного треугольника в вершинами в точках X; Y ; Z , имеющего катеты l и |Z - Y |. В самом деле, на катете Y Z возьмем такую точку W , что |W - Z | = r. Обозначим через U точку пересечения перпендикуляра в W с гипотенузой. Из подо бия треугольников lr |U - W | = . Кроме того, |U - W | r. Остается заметить, что радиус вписанной |Z - Y | окружности в прямоугольный треугольник с меньшим катетом |U - W | больше |U - W |=4. Итак, 1 1 1 % rl = cn-1 v0 l cn-1 v; 8 8 8 ибо v lv0 , что очевидно из принципа Кавальери. Пусть |Z - Y | l. Тогда при r l конус Q содержит шар радиуса 1 1 1 v1 r = cn-1 v0 cn-1 cn-1 v: 4 4 4 l8 Наконец, при r l конус Q содержит шар радиуса l=4. Ясно, что l не меньше v=sn-1 , где sn-1 | (n - 1)-мерный о бъем единичного шара в Rn-1 . 2. Положим %(x) := sin x (см. сноску к условию). Заменяя g на g - c, где c | интеграл от g%, переходим к случаю g% dx = 0. В этом случае надо доказать, что интеграл от f g% неотрицателен. Так как интегралы от (f - f (0))g% и f g% равны, то приходим к случаю, когда f 0. Пусть x0 := inf {x : g(x) 0}. Ясно, что x0 > 0. Тогда g(x) < 0 при x < x0 , g(x) 0 при x > x0 . Ввиду оценок 0 f (x) f (x0 ) при x < x0 и f (x) f (x0 ) при x > x0 получаем x0 x0 f (x)g(x)%(x) dx f (x0 ) g(x)%(x) dx;
0 =2 0
x0

Решения и указания к задачам 2008 года. 1. Применим индукцию по n. При n = 1 все очевидно. Пусть наше утверждение верно в

f (x)g(x)%(x) dx f (x0 )

=2

x0

g(x)%(x) dx;

13На олимпиаде задача предлагалась для C = 1 с оценкой f (x) M (1 + x ).


откуда
0

=2

f (x)g(x)%(x) dx f (x0 )

=2

Возможно другое короткое решение: с помощью приближений утверждение сводится к случаю непрерывно дифференцируемых функций. Функция (x) = 0x g(t)%(t) dt в предположении, что g% имеет нулевой интеграл, удовлетворяет таким условиям: (0) = (=2) = 0, (x) 0 (если (x0 ) = g(x0 )%(x0 ) = 0, то (x) 0 при x x0 и (x) 0 при x x0 из-за возрастания g). Интегрируя по частям, находим
=2

0

g (x)%(x) dx = 0:

Возможно третье короткое решение с помощью двойных интегралов (придуманное на олимпиаде А. Трепалиным). 3. Ответ: нео бходимое и достаточное условие | · либо b1 = b2 = c1 = c2 = 0, · либо одно из чисел c1 ; c2 ненулевое и о ба числа b1 и b2 делятся на GC D(c1 ; c2 ). 4. Ответ [Z]. Например, подходит фигура, ограниченная кривой 1 1 x = 12 cos + cos 2 + cos 4; y = 12 sin - sin 2 + sin 4: 2 2 Указание. Убедиться в этом, а также получить другие примеры искомых кривых, можно следующим о бразом. Заметим, что каждому направлению (задаваемому углом ) соответствует ровно одна прямая, делящая площадь и периметр фигуры пополам. Обозначим длину соответствующего отрезка этой прямой через 2l(), а координаты его середины через (x(); y ()). Напишем параметрическое уравнение границы фигуры. Теперь из условия задачи нетрудно вывести следующие свойства функций x, y, l: 1. l не зависит от . 2. Прямая, делящая фигуру пополам, касается кривой (x(); y ()). n Примеры функций x и y, удовлетворяющих условию 2, будем искать в виде (ak cos k + k=0 bk sin k'). (Для знакомых с рядами Фурье поиск решения в таком виде естественен.) Получим уравнения на коэффициенты ak ; bk (с параметром l), о беспечивающие выполнение условия 2. При этом для достаточно больших l полученная фигура будет выпуклой. 5. Указание. Take the graph whose set of vertices is W , and two vertices are joined by an edge if the distance between them is 1. Тогда более слабая оценка 2n-1 легко получается из следующего о бщеизвестного результата: if for each k vertices of a graph with v vertices there is an edge joining two of the k vertices, then the number of edges is at least (k - 1)q(q - 1)=2, where v q := . Для доказательства оценки 2n нужно уточнить рассуждения, применяемые k-1 при доказательстве сформулированного результата, используя несуществование n + 2 точек в n-мерном пространстве Rn с попарными расстояниями 1.

0

f (x)g(x)%(x) dx = -

=2

0

f (x) (x) dx 0:

При каждом n 5 гиперплоскость x1 + · · · + xn = n - 2 пересекает все замкнутые (n - 1)-мерные грани n-мерного куба In = (x1 ; : : : ; xn ) Rn : |xi | 1 . В самом деле: n-3 n-3 ;:::; и -1; 1; : : : ; 1 этой гиперплоскости лежат на гранях x1 = 1 и точки 1; n-1 n-1 x1 = -1 куба In , соответственно. Аналогично с остальными гранями. Эта гиперплоскость не пересекает вписанного шара, поскольку расстояние от начала координат до неё равно n-2 > 1. n

Решения и указания к задачам 2009 года. 1. Ответ: n = 5.


Несуществование такой гиперплоскости при n = 4 доказывается так (доказательство предложено В. Шмаровым; случай n 3 аналогичен). Предположим, напротив, что нашлась такая плоскость a1 x1 + · · · + a4 x4 = b для 4-мерного куба I4 . Без ограничения о бщности, считаем, что a1 a2 a3 a4 0 и b 0. Поскольку данная гиперплоскость пересекает грань x1 = -1, имеем -a1 + a2 x2 + a3 x3 + a4 x4 = b для некоторых x2 ; x3 ; x4 [-1; 1]. Тогда 0 b -a1 + a2 + a3 + a4 a3 + a4 ; поэтому b2 < (a3 + a4 )2 = a2 + 2a3 a4 + a2 a2 + a2 + a2 + a2 : 3 4 1 2 3 4 Следовательно, гиперплоскость пересекает вписанный шар. Противоречие. 2a. Указание. Пусть H1 ; : : : ; H2k-1 | все подмножества множества {1; 2; : : : ; k}, имеющие четное число элементов. Положим Ms := {(a1 ; b1 ; : : : ; ak ; bk ) {-1; 0; 1}2k : (ai ; bi ) = (±1; 0) при i Hs , (ai ; bi ) = (0; ±1) при i Hs }: k- Докажите, что 2=11 Ms и есть искомое множество из 22k-1 векторов. s 2b. Доказательство неравенства 80 m(4). Возьмем векторы · e1 ; : : : ; e5 , у которых первые три координаты равны +1, среди последних пяти координат ровно одна равна +1; а остальные координаты нулевые; · e6 ; : : : ; e10 , у которых первые три координаты равны +1, среди последних пяти координат ровно одна равна -1; а остальные координаты нулевые; · f1 ; : : : ; f30 , у которых среди первых трех координат ровно две равны +1 и одна нулю, а среди последних пяти координат ровно две равны +1 и ровно три нулю. Ясно, что ei · ej 2, fk · fl 1 and ei · fk 2 - 1 = 1. Поэтому векторы e1 ; : : : ; e10 ; -e1 ; : : : ; -e10 ; f1 ; : : : ; f30 ; -f1 ; : : : ; -f30 попарно неортогональны. 2b. Доказательство неравенства m(4) 140. (Это решение принадлежит В. Арутюнову; аналогичное решение предложил В. Вановский.) Для каждого вектора рассмотрим множество позиций, на которых стоят нули. Поскольку никакие два вектора не ортогональны, у любых двух векторов эти множества не "противоположны" (т.е. не дополняют друг друга). Существует 8 = 70 вариантов расположения нулевых позиций. Если, вопреки 4 утверждению задачи, найдется 141 таких попарно неортогональных векторов, то некоторые 5 из этих векторов будут иметь о бщие нулевые позиции. Мы можем считать, что указанные позиции суть 1,2,3,4 и что (1; 1; 1; 1; 0; 0; 0; 0) | один из пяти векторов. Ясно, что не более одного из оставшихся четырех векторов имеет ровно четыре координаты -1. Ни один из оставшихся четырех векторов не имеет ровно двух координат -1 (поскольку такой вектор ортогонален вектору (1; 1; 1; 1; 0; 0; 0; 0)). Не более одного из оставшихся четырех векторов имеет ровно одну координату -1 (поскольку два различных вектора такого вида ортогональны). Аналогично, не более одного из оставшихся четырех векторов имеет ровно одну координату 1. Противоречие. k k 3. Обозначим через z1 ; : : : ; zn комплексные числа, соответствующие вершинам k-го nk := (z k ; : : : ; z k ) Cn . Комплексные ко ординаты на пло ско сти выб ер ем так, угольника, и z n 1 k k что бы выполнялось условие z1 + · · · + zn = 0. Вершины равно бедренных треугольников, построенных на сторонах первого многоугольника, являются линейными функциями вершин этого многоугольника. Поэтому z2 = A1 z1 для некоторой матрицы A1 . Аналогично, z3 = A2 z2 , z4 = A3 z3 и т.д. для некоторых матриц A2 ; A3 ; : : : . Заметим, что 1. Векторы vi = (1; e2i=n ; e4i=n ; : : : ; e2(n-1)i=n ) для i = 0; : : : ; n - 1 о бразуют набор со бственных векторов матрицы Ak для любого k. 2. Одно из со бственных чисел матрицы Ak равно нулю. 3. Ему соответствует ровно один со бственный вектор vn-k . Условие 2 означает, что умножение на матрицу Ak задает проектирование пространства n на некоторую гиперпло ско сть. Из условия 3 получаем, что эти гиперпло ско сти различны C для разных k. Следовательно, умножение на произведение матриц An-2 An-3 : : : A2 A1 задает


проекцию подпространства z1 + · · · + zn = 0 на одномерное подпространство, задающее правильные n-угольники. Утверждение задачи доказано. 4. Обозначим данное ото бражение через T . Пусть, напротив, существует A = 0, для которой T (A) = 0. Существует вырожденная матрица B , для которой A + B невырождена (докажите!). Тогда следующая цепочка равенств дает противоречие. 0 = det B = det T (B ) = det(T (B ) + T (A)) = det T (A + B ) = 0: 5. Пусть для непрерывной функции f1 : R [0; +), некоторого C > 0 и любых единичного отрезка K и точки x K выполнено неравенство f (x) C + C K f (x) dx: Тогда f1 (x) C + C xx-1 f1 (y) dy: Напомним неравенство Гронуолла нужна формулировка!!!. При x 1=2 оно дает оценку
f1 (x) C + C
0
-

Аналогичная оценка верна и при x < -1=2, что в итоге дает
f (x) C + C
1=2
-1=

1=2

f1 (y) dy

eC x

C +C

1=2

-1=

2

f1 (y) dy eC x :

поскольку при |x| 1=2 это верно по условию. Пусть x R2 и |x| > 1=2. Повернем систему координат так, x R2 записываются в виде x = (z ; x2 ), z R Бессмыслица. 1 считать, что x2 > 1=2. Введем функцию (t) := -=22 f (z ; t) dz . 1= supK f (x)=C 1 + K f (y) dy по [-1=2; 1=2] Бессмыслица. Как
(t)=C 1 +

2

f1 (y) dy e

C |x

|

;

Как правильно?. Можно
Интегрированием условия правильно? находим

что x = (0; x2 ), где точки

что по одномерному случаю дает
(t)=C 1 +

[-1=2;1=2]в[t;t-1]

f (y) dy = 1 +

t

t-1

(u) du;
C |t
|

1=2
=2

Следовательно,
f (0; x2 )=C 1 +

-1

(s) ds e

C |t

|

= 1+
x2 x2 -1

[-1=2;1=2]2

f (x) dx e

: f (y) dy;

что завершает доказательство. Другой спосо б изложить это решение, придуманный участниками олимпиады, основан на следующей лемме (приведем ее формулировку для C = 1): f (x) 2 + max f (y) для любого yK 1 единичного квадрата K и любой точки x, лежащей прямоугольнике 1 в 2 , пересекающемся с K по о бщему ре бру. Справедливо следующее более о бщее утверждение. Пусть f : Rd [0; +) | локально ограниченная измеримая функция, причем для любых куба K с ребром единичной длины и x K выполнено неравенство f (x) C1 + C2 K f (y) dy, где C1 и C2 не зависят от K . Тогда f (x) M exp(C2 |x|), где
2 M = C1 + C1 C2 + max(C2 ; 1) sup

[-1=2;1=2]в[x2 -1;x2 ]

f (y) dy = 1 +

(t) dt 1 + C + C e

C |x2

|

[-1=2;1=2]2

[BRST] В.И.Богачев, А.М.Райгородский, А.Б.Скопенков и Н.А.Толмачев, Студенческие олимпиады и межкафедральный семинар на мехмате московского государственного университета, Мат.Просвещение, 12(2008),205-222. http://dfgm.math.msu.su/ les/skopenkov/stolymp.pdf [R] А.М. Райгородский, Линейно-алге браический метод в комбинаторике, Москва, МЦНМО. [Z] А.А. Заславский, Свойства и признаки окружности, Квант, N6, 2001.

Литература

AS Od A([-1=2;1=2]d )

f (y) dy: