Республиканская олимпиада по математике, 2018 год, 11 класс

Дано натуральное число $m\geq2.$ Последовательность натуральных чисел $(b_0,b_1,\ldots,b_m)$ назовем вогнутой, если $b_k+b_{k-2}\le2b_{k-1}$ для всех $2\le k\le m.$ Докажите, что существует не более $2^m$ вогнутых последовательностей, начинающихся с $b_0=1$ и $b_1=2.$ ( Д. Елиусизов )

Комментарий/решение

Комментарии от администратора Комментарии от администратора №1.    
Решение. Из условия следует, что $$b_m-b_{m-1} \le b_{m-1}-b_{m-2} \le \ldots \le b_1-b_0=1.$$ Значит каждая вогнутая последовательность имеет вид $$1,2,\ldots,n,n,\ldots,n,b_{n+k},\ldots,b_m,$$ где $2 \le n \le m+1,$ число $n$ записано $(k+1)$ раз, $0 \le k \le m+1-n$ и $n > b_{n+k} > \ldots > b_m.$ Количество последовательностей $b_{n+k}, \ldots, b_m$ не более $C_{n-1}^{m+1-n-k}$ (так как $b_{n+k}, \ldots,b_m$ различные натуральные числа которые меньше чем $n$). Для $n=m+1$ таких последовательностей ровно 1. Для $2 \le n \le m$ таких последовательностей будет не более чем $$C_{n-1}^{m+1-n}+C_{n-1}^{m-n}+ \ldots+C_{n-1}^{0} \le C_{n-1}^{0}+C_{n-1}^{1}+\ldots+C_{n-1}^{n-1}=2^{n-1}$$ (мы просуммировали по всем $k=0,1, \ldots,m+1-n).$ Значит всего вогнутых последовательностей будет не более чем $$2^1+2^2+\ldots+2^{m-1}+1=2^m-1 < 2^m.$$