ГЛАВНАЯ » РЕШЕБНИК

2014-02-26   
Пусть #d_{n}# - количество перестановок #\sigma : {1,2, \cdots, n} \rightarrow {1,2, \cdots, n}# таких, что выполнено неравенство #(\sigma(i) - \sigma(i - 1))(\sigma(i) - \sigma(i+1)) > 0# при любом #i = 2, 3, \cdots, n-1.# Доказать, что #2d_{2004} < d_{2005}.#


Решение:


Будем называть перестановки, удовлетворяющие условию, пилообразными. Ясно, что пилообразных перестановок с условием #\sigma(1) < \sigma(2)# ровно половина от общего количества. При этом таких перестановок с условием #\sigma(2006) = 2006# ровно #d_{2005}/2,# и в любой такой перестановке #\sigma(2005) < 2005,# иначе #\sigma(2004)# неопределена. Сопоставим перестановке #\sigma, \sigma(2006) = 2006,# перестановку #\sigma^{\prime}# такую, что #\sigma^{\prime} (i) = \sigma(i)# при #\sigma(i) < 2005, \sigma^{\prime}(2006) = 2005, \sigma^{\prime}(j) = 2006,# где #\sigma (j) = 2005.# Тогда #\sigma^{\prime}# - тоже пилообразная, причем разным #\sigma# соответствуют разные #\sigma^{\prime}# Поэтому #d_{2006} \geq 2d{2005}.# Осталось заметить, что существует хотя бы одна пилообразная перестановка с #\sigma(2005) < \sigma(2006) < 2005.#