Задача с Турнира Городов (немножко усложнила условие)

[Xenia1996]

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

*В оригинальном условии стояло "десять целых чисел" (не обязательно попарно различных). Но тогда задача решается уж слишком легко.

[EtCetera]

Если первая строка состоит из неотрицательных целых чисел, то справедливы следующие соображения.

Пусть в первой строке $n$ попарно различных неотрицательных целых чисел. Тогда в $k$-й строке ($k>1$) будет по меньшей мере $k-1$ нулей, располагающихся последовательно в конце строки (справа), так как 0 не больше любого другого неотрицательного числа. Следовательно, в лучшем случае "ненулевых" строк будет $n$ (включая первую).

$\begin{tabular}{|c|c|c|c|c|c|c|} \hline № строки & \dots & 5 & 4 & 3 & 2 & 1 \\ \hline 1 & \dots & \dots & \dots & \dots & \dots & \dots \\ \hline 2 & \dots & \dots & \dots & \dots & \dots & 0 \\ \hline 3 & \dots & \dots & \dots & \dots & 0 & 0 \\ \hline 4 & \dots & \dots & \dots & 0 & 0 & 0 \\ \hline 5 & \dots & \dots & 0 & 0 & 0 & 0 \\ \hline 6 & \dots & 0 & 0 & 0 & 0 & 0 \\ \hline \end{tabular}$

Можно показать, что это число "ненулевых" строк и будет максимальным, поскольку оно достигается, если первая строка организована следующим образом (для удобства заполнения строки взяты числа $1\dots n$):
$\underbrace{\dots\ 8\ 5\ 6\ 3\ 4\ 1\ 2}\atop n$

$\begin{tabular}{|c|c|c|c|c|c|c|c|c|} \hline № строки & \dots & 7 & 6 & 5 & 4 & 3 & 2 & 1 \\ \hline 1 & \dots & 8 & 5 & 6 & 3 & 4 & 1 & 2 \\ \hline 2 & \dots & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\ \hline 3 & \dots & 1 & 0 & 1 & 0 & 1 & 0 & 0\\ \hline 4 & \dots & 0 & 1 & 0 & 1 & 0 & 0 & 0 \\ \hline 5 & \dots & 1 & 0 & 1 & 0 & 0 & 0 & 0\\ \hline 6 & \dots & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ \hline 7 & \dots & 1 & 0 & 0 & 0 & 0 & 0 & 0\\ \hline 8 & \dots & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ \hline \end{tabular}$

Соответственно, при $n=10$ максимальное число "ненулевых" строк равно 10 (включая первую строку).

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

[Xenia1996]

Ну мне, в принципе, и добавить-то нечего...разве что первая строчка у меня была другая, а именно 9-10-7-8-5-6-3-4-1-2

-- Пт окт 01, 2010 22:58:12 --

Пардон, уже вижу, что не другая

[lim0n]

Ещё один вариант: $1\ 10\ 2\ 9\ 3\ 8\ 4\ 7\ 5\ 6$

[lim0n]

Поздно заметил...

to EtCetera
$8\ 5\ 6\ 3\ 4\ 1\ 2$
$0\ 1\ 0\ 1\ 0\ 1\ 0$
${\color{red} 3}\ 0\ {\color{red} 2}\ 0\ {\color{red} 1}\ 0\ 0$
$0\ {\color{red} 2}\ 0\ {\color{red} 1}\ 0\ 0\ 0$
${\color{red} 2}\ 0\ {\color{red} 1}\ 0\ 0\ 0\ 0$
\dots

[EtCetera]

lim0n
Ой! И правда! Ошибся. Спасибо.
Хотя на результат это все равно не влияет.

(Оффтоп)

В оправдание хочется заметить, что таблички я вообще не собирался набивать, и только под конец понял, что без них будет как-то ненаглядно. И набирал уже второпях...

[maxal]

Усложним:

1) Выразите количество перестановок чисел $1, 2, \dots, n$, которые дают $n-1$ ненулевых строк, как функцию от $n$.

2) Тот же вопрос, если в исходном правиле "больше" заменено на "больше или равно".