Разделы 
Дополнительно
Задача по математике - 3281
2019-06-02 
Натуральные числа от 1 до n расставляются в ряд в произвольном порядке (число $n$ фиксировано). Расстановка называется плохой, если в ней можно отметить 10 чисел (не обязательно стоящих подряд), идущих в порядке убывания. Остальные расстановки называются хорошими. Докажите, что количество хороших расстановок не превосходит $81^n$.
Решение:
1°. Докажем, что если расстановка хорошая, то числа в ряду можно раскрасить в девять цветов так, чтобы числа каждого цвета шли в порядке возрастания. Действительно, будем красить числа слева направо, используя каждый раз такой цвет с наименьшим номером, что последнее покрашенное в этот цвет число меньше текущего. Предположим, что девяти цветов не хватило. Мы не можем покрасить очередное число (обозначим его $a_{10}$) в девятый цвет, так как в девятый цвет уже было покрашено большее число $a_9$. Число $a_9$ не было покрашено в восьмой цвет, поскольку до него встретилось большее число $a_8$, покрашенное в восьмой цвет. И так далее. Получается 10 чисел, которые идут в порядке убывания. Противоречие.
2°. Расстановка чисел от 1 до $n$ вместе с такой раскраской в девять цветов, что последовательность чисел каждого цвета возрастает, полностью определяется цветом каждого числа от 1 до $n$ и цветом каждого места в ряду. Числа от 1 до $n$ можно раскрасить в 9 цветов $9n$ способами. И столькими же способами можно раскрасить в 9 цветов $n$ мест, на которые эти числа будут расставлены. Таким образом, число хороших расстановок не превосходит $81^n$.
Натуральные числа от 1 до n расставляются в ряд в произвольном порядке (число $n$ фиксировано). Расстановка называется плохой, если в ней можно отметить 10 чисел (не обязательно стоящих подряд), идущих в порядке убывания. Остальные расстановки называются хорошими. Докажите, что количество хороших расстановок не превосходит $81^n$.
Решение:
1°. Докажем, что если расстановка хорошая, то числа в ряду можно раскрасить в девять цветов так, чтобы числа каждого цвета шли в порядке возрастания. Действительно, будем красить числа слева направо, используя каждый раз такой цвет с наименьшим номером, что последнее покрашенное в этот цвет число меньше текущего. Предположим, что девяти цветов не хватило. Мы не можем покрасить очередное число (обозначим его $a_{10}$) в девятый цвет, так как в девятый цвет уже было покрашено большее число $a_9$. Число $a_9$ не было покрашено в восьмой цвет, поскольку до него встретилось большее число $a_8$, покрашенное в восьмой цвет. И так далее. Получается 10 чисел, которые идут в порядке убывания. Противоречие.
2°. Расстановка чисел от 1 до $n$ вместе с такой раскраской в девять цветов, что последовательность чисел каждого цвета возрастает, полностью определяется цветом каждого числа от 1 до $n$ и цветом каждого места в ряду. Числа от 1 до $n$ можно раскрасить в 9 цветов $9n$ способами. И столькими же способами можно раскрасить в 9 цветов $n$ мест, на которые эти числа будут расставлены. Таким образом, число хороших расстановок не превосходит $81^n$.
