олимпиадная мат задачка (про 100 солдат)

tatra

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

k11122nu

ты имеешь в виду, 10 подряд?
по-моему, это баян. А еще прослеживается аналогия с теоремой ван дер Вардена

Lokomotiv59

поправка: среди них можно выбрать десять упорядоченных или десять "анти"-упорядоченных

Lokomotiv59

ты имеешь в виду, 10 подряд?
думаю, что тут имелось ввиду не подряд.

k11122nu

а, конечно

Vadim46

Прослеживается связь с теоремой Дилуорса: Минимальное число непересекающихся цепей, которыми можно покрыть конечное частично упорядоченное множество, равно максимальному числу попарно несравнимых элементов этого множества (максимальной мощности антицепи)
Частично упорядочим множество солдат таким образом: A > B := A левее B и A выше B. Тогда нам надо найти цепь либо антицепь мощности 10. Допустим, что максимальная мощность антицепи M <= 9. Тогда всех солдат можно покрыть M непересекающимися цепями, и в какой-то из них должно быть хотя бы 10 солдат.
(Собственно, вместо 100 солдат хватило бы 82).
Как это доказать красиво, не повторяя в частном случае док-во теоремы Дилуорса, я пока не знаю, хотя эту задачу видел много раз :(

Lokomotiv59

в оригинале задача звучит так:
В шеренге стоят 101 (n^2+1) солдат. Доказать, что среди них можно выбрать 11 (n+1) упорядоченных по росту по возрастанию или по убыванию.
Доказывается следующим образом. Шеренга разбивается на цепочки возрастающих по росту солдат.
Строятся цепочки следующим образом: выбирается самый левый, не вошедший ни в одну из цепочек. Затем, ищется самый левый из не вошедших ни в одну цепочку, больший по росту, чем уже выбранный и включается в текущую цепочку. И так далее. Если предположить, что длина каждой цепочки не превосходит 10, то цепочек всего будет не меньше 11. Тогда солдаты, соответствующие началу каждой цепочки образуют убывающую по росту подпоследовательность.

tatra

Если я правильно понял, что ты имеешь ввиду, то вот контрпример:

первые не образуют возрастающую последовательность.
И сразу контрпример, что последние из каждой цепочки не образуют убывающую последовательность:
99 97 95 ... 96 98 100

tatra

О, спасибо. Более легкого решения, мне кажется, не будет. Задачка школьная, но продвинутая.
Вот mccme.ru сама теорема и применения, если кому интересно.

Lokomotiv59

натупил, согласен
Оставить комментарий
Имя или ник:
Комментарий: