Задания
Версия для печати и копирования в MS Word
 № 2147

Обозначим через Pn множество всех наборов (t1, t2, ..., tn) целых чисел таких, что 0 ⩽ ti ⩽ i. Сопоставим каждому такому набору число N(t_1, t_2,\ldots, t_n)=t_1 умножить на 1! плюс t_2 умножить на 2! плюс \ldots плюс t_n умножить на n!.

а) Найдите все возможные наборы (t1, t2, t3, t4), для которых N(t1, t2, t3, t4) = 15.

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

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

г) Пусть j0, j1, ..., jn — некоторая перестановка чисел 0, 1, ..., n. Обозначим через ti количество чисел, меньших i, но стоящих справа от него в данной перестановке. Найдите все перестановки j0, j1, ..., j6, для которых N(t_1,t_2,\ldots,t_6)=2002.

Спрятать решение

Решение.

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

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,

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

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

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

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.

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

Получаем последовательно, при 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=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.


-------------
Дублирует задание № 2142.
Спрятать критерии
Критерии проверки:

? Источник: Профильно-элитарный выпускной экзамен по математике. Санкт-Петербург, 2002 год, вариант 2
? Классификатор: Доказательство тождеств, неравенств, Комбинаторика, вероятности, Прогрессии
?
Сложность: 11 из 10
Спрятать решение · Прототип задания · ·