Новости
12.12.2018  Порядок сдачи досрочного экзамена
подробнее...

10.12.2018  Предварительные результаты олимпиады 09 декабря 2018 года
подробнее...

05.12.2018  Изменения в расписании
подробнее...

 
 
Содержание Все заметки на одной странице

Задачи IMC 2009

Перевод задач на русский не дословный, но смысл по возможности сохранён. Оригинальные тексты задач первого дня и второго дня доступны на официальном сайте IMC.

День 1

  1. Предположим, что f, g : R → R — функции, такие что f(r) ≤ g(r) для всех рациональных r. Следует ли отсюда неравенство f(x) ≤ g(x) для всех действительных x, если:
    а) f и g монотонны;
    б) f и g непрерывны.
  2. Пусть A, B, C — квадратные матрицы одинакового размера, причём A обратима. Докажите, что из
    (A-B)C=BA-1
    следует
    C(A-B) = A-1B.
  3. Пусть в графе G на n вершинах любые несмежные вершины имеют общего соседа, и ни одна вершина не является смежной со всеми остальными. Пусть также сумма квадратов степеней вершин равна n2-n. Найдите все возможные значения длины минимального цикла G.
  4. Пусть p(z) = a0 + a1z + ··· + anzn — комплексный многочлен. Рассмотрим последовательность действительных чисел
    1 = c0 ≥ c1 ≥ ··· ≥ cn ≥ 0
    которая является выпуклой, т.е. 2ck ≤ ck-1 + ck+1. Рассмотрим также многочлен
    q(z) = c0a0 + c1a1z + ··· + cnanzn.
    Докажите, что максимум модуля q на единичном круге не превосходит максимума модуля p там же.
  5. Для всякого симплекса S в Rn обозначим v(S) его объём, а C(S) — центр описанной сферы. Рассмотрим точку P внутри симплекса S. Обозначим симплексы, которые получаются при замене одной из вершин S на P как S0, S1, ... , Sn. Докажите что
    v(S0)C(S0) + v(S1)C(S1) + ··· + v(Sn)C(Sn) = v(S)C(S).

День 2

  1. Рассмотрим в пространстве R3 прямую l и точку P. Рассмотрим множество S точек X таких что
    dist(X, l) ≥ 2dist(X, P).
    Найдите объём S.
  2. Пусть f: R → R — дважды дифференциируемая функция, у которой f(0)=1, f'(0) = 0. Предположим, что
    f''(x)-5f'(x)+6f(x) ≥ 0
    для всех x ∈ [0, +∞). Докажите что для всех x ∈ [0, +∞)
    f(x) ≥ 3e2x - 2e3x.
  3. Предположим A и B — комплексные квадратные матрицы одинакового размера и
    A2B+BA2 = 2 ABA.
    Докажите, что матрица AB-BA нильпотентна.
  4. Пусть p>3 — простое число, а Fp — поле вычетов по модулю p. Пусть W — минимальное множество многочленов с коэффициентами в Fp, обладающее следующими свойствами
    • Многочлены x+1 и xp-2+xp-3 + ··· + x2 + 2x + 1 содержатся в W;
    • Если a(x) и b(x) содержатся в W, то остаток от деления a(b(x)) на xp-x тоже содержится в W.
    Сколько многочленов содержится в W?
  5. Пусть M — пространство всех матриц m×p. Для линейного подпространства S ⊆ M обозначим δ(S) размерность пространства всех образов операторов A ∈ S.
    Линейное подпространство T ⊆ M называется накрывающим, если объединение ядер всех операторов A ∈ T совпадает с Rp. Если в накрывающем пространстве матриц нет накрывающих подпространств, то назовём такое пространство матриц минимальным. Пусть далее T — минимальное накрывающее пространство размерности n.
    а) (8 очков) Докажите что δ(T) ≤ Cn2 (биномиальный коэффициент);
    б) (2 очка) Докажите, что для всякого n можно найти такие m, p и минимальное накрывающее пространство матриц T, для которого в предыдущем пункте имеет место равенство.

Комментарии к задачам

Первые две задачи в каждый день рассматривались как очень простые. Однако в задаче 1-2 можно было не заметить сведения задачи к очевидному свойству AB=I ⇒ BA=I. В задаче 2-2 не все помнили формулу для решения линейного дифференциального уравнения первого порядка.

В задаче 1-3 имелись любопытные критерии оценок: за отсутствие доказательства существования циклов решили не снимать. Но, за отсутствие примера того, что граф G вообще существует, снимали 1 очко.

Задачу 1-4 практически никто не решил, хотя некоторые части решения присутствовали в разных работах. Сначала надо было перейти на единичную окружность с помощью принципа максимума (за это баллов не давали), потом представить q(z) в виде свёртки p(z) с некоторым ядром, которое является вещественным и неотрицательным. Неотрицательность следует из выпуклости последовательности, в этом случае ядро является суммой δ-функции и нескольких ядер Фейера. Любопытно, что одна из аудиторий, где проходила проверка работ, называлась зал Фейера.

Задача 1-5 по факту оказалась проще 1-4. Надо было просто знать известный факт, что сумма нормалей граней, умноженных на (n-1)-мерные меры граней, равна нулю, и добавить к этому факту теорему синусов для треугольника. Несколько участников решили эту задачу полностью.

Задача 2-3 оказалась известной теоремой (теорема Джейкобсона). Более того, некоторые из участников знали её доказательство в варианте для гильбертовых пространств с заменой нильпотентности на квазинильпотентность (некоторое свойство, выражаемое через норму оператора). Для гильбертовых пространств это утверждение называется теоремой Кляйнеке-Широкова.

Задача 2-4 по сложности была проще, чем 2-3. Видимо, её поставили на такое почётное место, так как это единственная задача на олимпиаде по алгебре вообще. Хотя сведения из алгебры для её решения требуются минимальные: деление многочленов с остатком, корни многочленов, и строение группы перестановок.

Задачу 2-5, по правде говоря, даже среди членов жюри мало кто понял. Хотя приведённое решение (вариант 2) вполне короткое и не использует ничего, кроме элементарной линейной алгебры. По сути эту задачу никто из студентов не решил, но некоторые студенты всё же получили за неё по несколько баллов.

В целом, многие члены жюри (они же руководители команд) отметили, что способ выбора задач на олимпиаду голосованием за каждое место подряд не вполне адекватен. В частности, задач по линейной алгебре оказалось 3 из 10, плюс задачи 1-5 и 2-1 тоже очень близки к линейной алгебре.

 
© 2009 Роман Карасёв