16 человек (все разного роста) постороены в шеренгу произвольным образом. Доказать, что всегда можно скомандовать некоторым 5-ым из них "шаг вперёд" и, теперь эти пятеро будут стоять по росту (в ту или другую сторону). Можно ли уменшить число 16?

Расставим эти 16 человек следующим незамысловатым образом -

4,3,2,1,8,7,6,5,12,11,10,9,16,15,14,13

У меня стойкое убеждение граничащее с уверенностью что никакие пять из них не могут выйти из шеренги и оказаться при этом стоящими по росту

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

да, мне тоже казалось, что способ должен найтись, но после часа переборов надоело и забросил :) Наверное формула, при которой как минимум х человек стоят по росту x^2+1.

Так оно и есть http://mathworld.wolfram.com/LongestIncrea...ubsequence.html.
Это легко увидеть если неожиданно вспомнить или доказать, что длина максимальной возрастающей подпоследовательности равна минимальному числу покрывающих исходную последовательность убывающих подпоследовательностей

Конечно формулировка немного фрустрирует, но если на примере то суть проста Возьмем последовательность 2,4,1,3,5 Возрастающая подпоследовательность 2,3,5 соответствует набору убывающих подпоследовательностей {2,1}{4,3}{5}. Длины равны, экстремальные свойства видны невооруженным взглядом.

И в принципе уже из примера видно каким путем должно идти доказательство утверждения.