Областная олимпиада по математике, 2003 год, 9 класс
Комментарий/решение:
$Ответ:30$ нечетных чисел
Сразу удалим четные числа на доске. Рассмотрим $6$ чисел, где $k$ из которых четные, а $6-k$ - нечетные, добавим седьмое число и найдем наибольшее число нечетных чисел на доске. Пусть $f(a_i, a_j)=$ количество выписанных чисел для $a_i$ и $a_j$, тогда $f(чет, чет)=0, f(чет, нечет)=2, f(нечет, нечет)=1$
Есть два случая:
$1) k>2$, пусть $S=$ количество выписанных нечетных чисел на доске, рассмотрим насколько изменяется $S$. Если добавленное $7$-ое число четно, тогда $S_7=S_6+0 \cdot k +2\cdot(6-k)=S_6+12-2k$, если добавленное число нечетно, тогда $S_7=S_6+2 \cdot k+1 \cdot (6-k)=S_6+6+k.$ $$S_6+12-2k < S_6+6+k,$$ поэтому добавлять нечетное число будет эффективнее. Перебирая варианты $k=3,4,5,6$ получаем, что
$1) k=3,$ 3 четных и 3 нечетных, $S_6=6+6+6+2+1=21, S_7=21+6+3=30;$
$2) k=4,$ 4 четных и 2 нечетных, $S_6=4+4+4+4+1=17, S_7=17+6+4=27;$
$3) k=5,$ 5 четных и 1 нечетное, $S_6=2+2+2+2+2=10, S_7=10+6+5=21;$
$4) k=6$, $S_6=0, S_7=0+6+6=12;$
$max(S_7)=30$
$2) k \leq 2$, тогда выгодно брать четное число.
$1) k=2,$ 2 четных и 4 нечетных, $S_6=8+8+3+2+1=22, S_7=22+12-4=30;$
$2) k=1,$ 1 четное и 5 нечетных, $S_6=10+4+3+2+1=20, S_7=20+12-2=30;$
$3)k=0,$ 0 четных и 6 нечетных, $S_6=5+4+3+2+1=15, S_7=15+12-0=27.$
Пример для $30$ $(k=1)$: $a_1=1, a_2=7, a_3=31, a_4=127, a_5=511, a_6=2020, a_7=6060.$
Вот другая оценка что максимум $30$ через неравенство:
Пусть $k$ число нечетных чисел из семи. То $S=2k(7-k)+\dfrac{k(k-1)}{2}$, так как $k(7-k)$ число пар $(чётное,нечётное)$, а $\dfrac{k(k-1)}{2}$ число пар $(нечётное,нечётное)$
$S=\dfrac{27k-3k^2}{2}=\dfrac{243-12(k-4,5)^2}{8} \leq \dfrac{243-12*0,5^2}{8}=30$
Для тех кто не понял почему последнее неравенство AbenSad-а верно:
Рассмотрим параболу $\dfrac{-3}{2} k^2+ \dfrac{27}{2}k$. Ее максимальная точка равна при $k=\dfrac{-\dfrac{27}{2}}{2 \cdot \dfrac{-3}{2}}=4,5$, при которой $S=30.375,$ но $S \in Z, \Rightarrow S \leq 30$
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.