Новости
07.02.2019  Занятия для первокурсников
подробнее...

03.02.2019  Спецкурсы в весеннем семестре 2019 года
подробнее...

28.12.2018  Результаты олимпиады 09 декабря 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 Роман Карасёв