|
|
 |
Условие
На доске написано несколько целых положительных чисел: a0, a1, a2, ... , an. Пишем на другой доске следующие числа: b0 – сколько всего чисел на первой доске, b1 – сколько там чисел, больших единицы, b2 – сколько чисел, больших двойки, и т.д., пока получаются положительные числа. На этом заканчиваем – нули не пишем. На третьей доске пишем числа c0, c1, c2, ... , построенные по числам второй доски по тому же правилу, по которому числа b0, b1, b2, ... строились по числам первой доски. Докажите, что наборы чисел на первой и третьей досках совпадают.
Решение
Можно считать, что a0 ≥ a1 ≥ ... ≥ an.
Первый способ. Для удобства добавим к этому набору число an+1 = 0.
Первые bk чисел этой последовательности (то есть числа a0, a1, ..., abk–1) больше k, а остальные – не больше k. Таким образом, числа bk однозначно определены по числам первой доски соотношениями: abk–1 > k, abk ≤ k. Аналогичными соотношениями определяются числа ck по числам второй доски. Поэтому, чтобы доказать равенства ck = ak, достаточно проверить, что bak–1 > k, bak ≤ k.
Но bak–1 – количество чисел на первой доске, больших ak – 1. Такими числами заведомо будут a0, a1, a2, ..., ak. Значит, bak–1 ≥ k + 1 > k.
С другой стороны, bak – количество чисел на первой доске, больших ak. Такими числами могут быть только a0, a1, a2, ..., ak–1. Значит, bak ≤ k.
Второй способ. Каждому неубывающему набору соответствует диаграмма Юнга. Легко видеть, что в первой строке этой диаграммы b0 клеток, в следующей – b1 и т.д. Это значит, что переходу от набора a0, a1, ... к набору b0, b1, ... соответствует переворот диаграммы. Набор c0, c1, ... соответствует положению исходной диаграммы после второго переворота. Но это положение, очевидно, совпадает с исходным, поэтому наборы a0, a1, ... и c0, c1, ... совпадают.
Замечания
1. Эта задача – переформулировка теоремы А. Лебега.
2. 8-9 кл. – 4 балла, 10-11 кл. – 3 балла.
