Опубликуем ещё одну задачу с олимпиады «JetBrains Youth Challenge», автор — К. А. Кноп.

В лиге младших классов она была 8-й из 8, и её решила всего 1 команда. Коллектив жюри ожидал большего количества решений этой задачи🙂

А оригинальная версия этой задачи была заметно сложнее — причём настолько, что методкомиссия даже не решилась вставлять её в лигу старших классов. Для продвинутых комбинаторов опубликуем и оригинальную формулировку тоже!

#мт_задача

Пользуясь случаем, напомню следующую задачу.

У Белочки есть бесконечно много орехов: по одному ореху каждой из
масс 1 г, 2 г, 3 г, \dots. Она взяла n мешков, положила в каждый по
конечному числу орехов, после чего написала на каждом мешке суммарную
массу лежащих в нем орехов.

а) Докажите, что можно было собрать мешки с
такими же массами, использовав не более 4n-3 орехов.

б*) Какова точная оценка на число орехов, которого заведомо достаточно?

Пункт б) я решать не умею.

Прочитал про теорему Дена о разрезании: если прямоугольник можно разрезать на квадраты, то отношение его сторон рационально. Интуитивно это кажется логичным, но доказать не так уж и просто. Обратное утверждение тривиально: если отношение сторон рационально и скажем равно p/q, то увеличив масштаб в q раз, получим прямоугольник с целыми сторонами, который можно разрезать на квадраты 1x1.

Линейная алгебра помогает построить простые и красивые доказательства:

Отношение длин сторон прямоугольника W,H иррационально - это то же, что "W,H линейно независимы как векторы в пространстве R над Q". Это в свою очередь значит, что существует Q-линейная функция f:R->R, так, что f(W) и f(H) - любые удобные нам значения.

Для любой Q-линейной функции f определим f-площадь прямоугольника со сторонами A,B как f(A)*f(B). Тогда легко увидеть, что при разрезании прямоугольника на другие прямоугольники f-площадь целого равна сумме f-площади частей (это очевидно при разрезании одного прямоугольника на два, и к повторению этого можно свести любое разрезание, если сделать из него "сетку", продлив все внутренние линии до краев).

Как ни странно, доказательство почти закончено. f-площадь любого квадрата равна f(A)*f(A), то есть неотрицательна. Отсюда f-площадь любого прямоугольника размером W:H, разрезанного на квадраты, неотрицательна. Но если W/H не рационально, то мы можем выбрать такую f, что f(W)=1, f(H)=-1, и его f-площадь равна -1, это противоречие.

Другое доказательство с помощью линейной алгебры вместо f-площади пользуется тензорным произведением R@R. Если стороны прямоугольника w,h линейно независимы, то {w,h} можно продлить до базиса, и поэтому ясно, что в R@R линейно независимы также векторы w@w, w@h, h@w, h@h. С другой стороны, если прямоугольник разбит на квадраты, то w@h является суммой членов вида a@a (доказательство аналогично примеру с площадью). Это значит, что изоморфизм в R@R, который меняет координаты местами, одновременно переводит w@h в h@w и оставляет неизменным, т.е. w@h = h@w, а это противоречит их независимости.

Еще есть красивое доказательство с помощью гармонических функций на конечных графах (второе в этой заметке). А в древней книжке Яглома "Как разрезать квадрат?" (1968) есть элементарное доказательство через систему уравнений, связывающих длины сторон.

P.S. Вспоминается также замечательная статья "Fourteen proofs of a result about tiling a rectangle", где дается много доказательство похожего, но другого по сути утверждения: что если прямоугольник разрезан на прямоугольники и у каждого внутренного прямоугольника хотя бы одна из сторон - целое число, то и у всего прямоугольника тоже хотя бы одна из сторон целая.

1 и 2 день, решения