РЕШУ УРОК — выпускные экзамены по математике

Задания

Обозначим через P_n множество всех наборов (t₁, t₂, ..., t_n) целых чисел таких, что 0 ⩽ t_i ⩽ i. Сопоставим каждому такому набору число $N левая круглая скобка t_1, t_2,\ldots, t_n правая круглая скобка =t_1 умножить на 1! плюс t_2 умножить на 2! плюс \ldots плюс t_n умножить на n!.$

а)  Найдите все возможные наборы (t₁, t₂, t₃, t₄), для которых N(t₁, t₂, t₃, t₄)  =  15.

б)  Докажите, что $N левая круглая скобка t_1,t_2,\ldots,t_n правая круглая скобка меньше или равно левая круглая скобка n плюс 1 правая круглая скобка ! минус 1.$

в)  Докажите, что N определяет взаимно однозначное соответствие между P_n и множеством всех неотрицательных целых чисел, меньших (n + 1)!.

г)  Пусть j₀, j₁, ..., j_n  — некоторая перестановка чисел 0, 1, ..., n. Обозначим через t_i количество чисел, меньших i, но стоящих справа от него в данной перестановке. Найдите все перестановки j₀, j₁, ..., j_{6, для которых}

Решение. а)  Запишем условие в виде

$t_1 умножить на 1! плюс t_2 умножить на 2! плюс t_3 умножить на 3! плюс t_4 умножить на 4!=15$

и преобразуем его $t_1 плюс 2t_2 плюс 6t_3 плюс 24t_4=15.$ Ясно, что $t_4=0.$ Кроме того, $t_1 плюс 2t_2 меньше или равно 1 плюс 2 умножить на 2=5,$ откуда $6t_3 больше или равно 15 минус 5=10$ и $t_3 больше или равно 2.$ В то же время $6t_3 меньше или равно 15,$ откуда $t_3 меньше или равно 2.$ Итак, $t_3=2.$ Уравнение сводится к $t_1 плюс 2t_2=3.$ Ясно, что $t_1=1$ (при $t_1=0$ получилось бы четное значение), а тогда и $t_2=1.$ Ответ $t_1=t_2=1,$ $t_3=2,$ $t_4=0.$

б)  Ясно, что максимальное значение n достигается при $t_i=i.$ Докажем, что оно равно $левая круглая скобка n плюс 1 правая круглая скобка ! минус 1$ по индукции. База $n=1,$ $1 умножить на 1!=2! минус 1$   — верное утверждение.

Переход. Пусть $1 умножить на 1! плюс 2 умножить на 2! плюс \ldots плюс n умножить на n!= левая круглая скобка n плюс 1 правая круглая скобка ! минус 1,$ тогда

$1 умножить на 1! плюс 2 умножить на 2! плюс \ldots плюс n умножить на n! плюс левая круглая скобка n плюс 1 правая круглая скобка умножить на левая круглая скобка n плюс 1 правая круглая скобка !=$
$= левая круглая скобка 1 умножить на 1! плюс 2 умножить на 2! плюс \ldots плюс n умножить на n! правая круглая скобка плюс левая круглая скобка n плюс 1 правая круглая скобка умножить на левая круглая скобка n плюс 1 правая круглая скобка !=$
$= левая круглая скобка n плюс 1 правая круглая скобка ! минус 1 плюс левая круглая скобка n плюс 1 правая круглая скобка умножить на левая круглая скобка n плюс 1 правая круглая скобка !=$
$= левая круглая скобка n плюс 2 правая круглая скобка умножить на левая круглая скобка n плюс 1 правая круглая скобка ! минус 1= левая круглая скобка n плюс 2 правая круглая скобка ! плюс 1,$ $1 умножить на 1! плюс 2 умножить на 2! плюс \ldots плюс n умножить на n! плюс левая круглая скобка n плюс 1 правая круглая скобка умножить на левая круглая скобка n плюс 1 правая круглая скобка !=$
$= левая круглая скобка 1 умножить на 1! плюс 2 умножить на 2! плюс \ldots плюс n умножить на n! правая круглая скобка плюс левая круглая скобка n плюс 1 правая круглая скобка умножить на левая круглая скобка n плюс 1 правая круглая скобка !=$
$= левая круглая скобка n плюс 1 правая круглая скобка ! минус 1 плюс левая круглая скобка n плюс 1 правая круглая скобка умножить на левая круглая скобка n плюс 1 правая круглая скобка !=$
$= левая круглая скобка n плюс 2 правая круглая скобка умножить на левая круглая скобка n плюс 1 правая круглая скобка ! минус 1=$
$= левая круглая скобка n плюс 2 правая круглая скобка ! плюс 1,$

что и требовалось доказать.

в)  Ясно, что каждому набору t_i (которых ровно $2 умножить на 3 умножить на \ldots умножить на левая круглая скобка n плюс 1 правая круглая скобка = левая круглая скобка n плюс 1 правая круглая скобка !,$ поскольку выбрать t_i можно $i плюс 1$ способом независимо от других выборов) соответствует ровно одно целое число, причем оно всегда от 0 до $левая круглая скобка n плюс 1 правая круглая скобка ! минус 1$ (см. пункт б). В этом промежутке как раз $левая круглая скобка n плюс 1 правая круглая скобка !$ целых чисел. Осталось доказать, что никакие два значения N для разных наборов не совпадают. Допустим, они совпали. Выберем максимальный индекс i для которого в первом наборе t_i отличается от p_i во втором наборе. Пусть в первом оно больше.

Тогда уже за счет слагаемого $t_i умножить на i!$ вместо $p_i умножить на i!$ сумма в первом наборе больше суммы во втором наборе минимум на $i!.$ Все большие слагаемые в суммах равны, а меньшие, даже если во втором наборе взять максимально возможные коэффициенты, а в первом нули, скомпенсируют лишь разницу

$1 умножить на 1! плюс 2 умножить на 2! плюс \ldots плюс левая круглая скобка i минус 1 правая круглая скобка умножить на левая круглая скобка i минус 1 правая круглая скобка !=i! минус 1$ $1 умножить на 1! плюс 2 умножить на 2! плюс \ldots плюс$
$плюс левая круглая скобка i минус 1 правая круглая скобка умножить на левая круглая скобка i минус 1 правая круглая скобка !=i! минус 1$

и сумма в первом наборе останется больше. Итак, суммы не могут совпасть. Значит, каждая потенциально возможная сумма получается ровно один раз.

г)  Сначала найдем набор $t_1,t_2,\ldots t_6$ такой, что

$t_1 плюс 2t_2 плюс 6t_3 плюс 24t_4 плюс 120t_5 плюс 720t_6=2002.$ $t_1 плюс 2t_2 плюс 6t_3 плюс 24t_4 плюс$
$плюс 120t_5 плюс 720t_6=2002.$

По доказанному выше, можно искать числа с конца, выбирая максимально возможное t_i, для которого сумма еще не превосходит нужной (если выбрать больше, то сумма будет больше чем надо, а если меньше, то даже максимально возможные меньшие слагаемые не смогут этого скомпенсировать).

Получаем последовательно, при $t_6=2,$ $t_5=4,$ $t_4=3,$ $t_3=1,$ $t_2=2,$ $t_1=0:$

$t_1 плюс 2t_2 плюс 6t_3 плюс 24t_4 плюс 120t_5=2002 минус 1440=562,$ $t_1 плюс 2t_2 плюс 6t_3 плюс 24t_4 плюс 120t_5=$
$=2002 минус 1440=562,$

$t_1 плюс 2t_2 плюс 6t_3 плюс 24t_4=562 минус 480=82,$

$t_1 плюс 2t_2 плюс 6t_3=82 минус 72=10,$

$t_1 плюс 2t_2=10 минус 6=4.$

Теперь можно установить место каждого из чисел $0, 1, \ldots 6$ в перестановке. Например, 1 должна стоять после 0 (иначе $t_1=1$ ). Теперь поставим двойку. Она должна стоять левее и 1 и 0, чтобы выполнялось $t_2=2.$ Аналогично добавляем остальные числа. Последовательно получим

$левая круглая скобка 2, 0, 1 правая круглая скобка \mapsto левая круглая скобка 2, 0, 3, 1 правая круглая скобка \mapsto левая круглая скобка 2, 4, 0, 3, 1 правая круглая скобка \mapsto левая круглая скобка 2, 5, 4, 0, 3, 1 правая круглая скобка \mapsto левая круглая скобка 2, 5, 4, 0, 6, 3, 1 правая круглая скобка .$

Комментарий. Поскольку все произведенные здесь действия легко алгоритмизируются, они представляют собой один из самых простых способов организации полного перебора всех перестановок данных чисел с помощью компьютера для решения какой-либо задачи о поиске перестановки с нужными свойствами.

Ответ: а) 1; 2; 0; г) 2, 5, 4, 0, 6, 3, 1.

№ п/п	№ задания	Ответ
1	2142	а) 1; 2; 0; г) 2, 5, 4, 0, 6, 3, 1.

Ключ