Натуральные числа  от  1  до  n  расставляются  в ряд в произвольном
  порядке. Расстановка называется плохой, если в
  ней можно отметить 10 чисел (не обязательно стоящих подряд),  идущих
 в
  порядке убывания. Остальные расстановки называются хорошими.
 Докажите,
  что количество хороших расстановок не превосходит 81n.


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

  2) Расстановка  чисел  от  1 до n вместе с такой раскраской в девять
  цветов,  что  последовательность  чисел  каждого   цвета
 возрастает,
  полностью  определяется  цветом  каждого  числа  от  1 до n и цветом
  каждого места в ряду.  Числа от 1 до n можно раскрасить в  9  цветов
  9n способами.  И столькими же способами можно раскрасить в
  9
  цветов
  n мест, на которые эти числа будут расставлены. Таким образом, число
  хороших расстановок не превосходит 81n.
			
Отношение порядка Геометрическая прогрессия