Задача IMO 2007, на которой 473 школьника получили ноль

В июле 2007 года в Ханое прошла 48-я Международная математическая олимпиада (IMO). За медали боролись 520 школьников со всего мира. Шестая задача, последняя во втором туре, оказалась настоящей мясорубкой: 473 участника получили за неё ноль баллов, и только пятеро набрали полные семь. Одним из этих пятерых был 19-летний Петер Шольце из Германии. В 2018 году он получил Филдсовскую премию, самую престижную награду в математике.

Условие задачи

Пусть n натуральное число. Рассмотрим множество S всех точек (x, y, z), у которых каждая координата принимает целые значения от 0 до n, кроме начала координат (0, 0, 0). Всего в S получается (n+1)³ – 1 точек. Нужно найти наименьшее количество плоскостей, которые вместе покрывают все точки S, причём ни одна из плоскостей не проходит через начало координат.

Формулировка умещается в три строки и выглядит как разминка. В этом и коварство.

Ответ находится за пять минут

Возьмём плоскости x = 1, x = 2, …, x = n и такие же наборы для y и z. Получается 3n плоскостей. У любой точки из S есть хотя бы одна ненулевая координата, поэтому она лежит на одной из них. Начало координат не лежит ни на одной, условие выполнено.

Есть и другая конструкция: плоскости x + y + z = k для k от 1 до 3n. Их снова 3n. Когда два совершенно разных подхода дают одно и то же число, хочется поверить, что меньше не бывает. Но олимпиада оценивает доказательство, и голый ответ 3n почти ничего не приносит.

Где застряли почти все

Нижнюю оценку пытались получить комбинаторикой: считать точки на гранях куба, искать плоскость, которая покрывает слишком мало, вести индукцию по n. Все эти попытки упираются в одно препятствие. Плоскость может быть наклонена как угодно и задевать точки в самых неожиданных сочетаниях, поэтому прямой подсчёт быстро разваливается.

Решение приходит из алгебры. Каждую плоскость можно записать уравнением ax + by + cz = d. Раз плоскость не проходит через начало координат, d не равно нулю. Перемножим выражения ax + by + cz – d для всех плоскостей и получим многочлен P(x, y, z). Его степень равна числу плоскостей m. Он обращается в ноль во всех точках S, потому что каждая точка лежит хотя бы на одной плоскости. В начале координат он равен произведению чисел -d, то есть отличен от нуля.

Геометрическая задача превратилась в утверждение о многочленах: если многочлен зануляется на всей решётке {0, 1, …, n}³, кроме одной угловой точки, то его степень не меньше 3n.

Доказательство через конечные разности

Для функции одной переменной введём разность Δf(x) = f(x+1) – f(x). Каждое применение Δ понижает степень многочлена на единицу, поэтому n-кратная разность уничтожает любой многочлен степени меньше n. При этом Δⁿf(0) раскрывается в знакочередующуюся сумму значений f(0), f(1), …, f(n) с биномиальными коэффициентами.

Применим к P разность n раз по x, n раз по y и n раз по z и посмотрим на результат в начале координат. С одной стороны, это сумма значений P по всем точкам куба {0, …, n}³ с ненулевыми коэффициентами. Все значения, кроме P(0, 0, 0), равны нулю, а коэффициент при P(0, 0, 0) равен ±1. Значит, результат не равен нулю.

С другой стороны, если степень P меньше 3n, то в каждом одночлене xᵃyᵇzᶜ хотя бы один показатель меньше n. Соответствующая n-кратная разность его убивает, и весь результат равен нулю. Получаем противоречие, значит плоскостей не меньше 3n.

Тот же вывод следует из комбинаторной теоремы о нулях (Combinatorial Nullstellensatz), которую Нога Алон опубликовал в 1999 году. Полиномиальный метод с тех пор стал одним из главных инструментов комбинаторики и теоретической информатики. Школьнику в 2007 году нужно было либо знать этот приём, либо изобрести его за четыре с половиной часа, параллельно решая ещё две задачи тура.

Кто такой Петер Шольце

Шольце выступал на IMO четыре года подряд и привёз три золотые медали и одну серебряную. В 24 года он стал полным профессором Боннского университета, одним из самых молодых в истории Германии. Его теория перфектоидных пространств дала новый язык для задач арифметической геометрии и теории чисел, и в 2018 году в Рио-де-Жанейро ему вручили Филдсовскую медаль. Сегодня он директор Института математики Макса Планка в Бонне.

История задачи №6 хорошо показывает, как устроена сильная математика. Ответ видели почти все участники. Решающим оказалось умение перевести вопрос о геометрии на язык алгебры, где у него находится короткое и точное доказательство.