Liczby na tablicy

[mol_ksiazkowy]

Na tablicy są wypisane liczby \(\displaystyle{ 1,...,n}\). Dwie dowolne z nich: \(\displaystyle{ x, y}\) wymazuje się i dodaje na ich miejsce liczbę \(\displaystyle{ 2x+2y}\); aż w końcu zostanie tylko jedna liczba. Udowodnić, że jest ona nie mniejsza niż \(\displaystyle{ \frac{4}{9}n^3}\)

[PoweredDragon]

Ciekawe zadanie...
Zauważmy, że najmniejszą możliwą sumę otrzymamy poprzez wymazywanie dwóch najmniejszych liczb z tablicy i zastępowanie ich podaną sumą. Masz więc ciąg wyników minimalnych, w zależności od ilości liczb na tablicy (czyli liczby n):

Są to wyniki, jakie zostaną na tablicy po skończeniu operacji:

Ukryta treść:    

\(\displaystyle{ a_1 = 2 = 1 \cdot 2}\)
\(\displaystyle{ a_2 = 6 = (1+2) \cdot 2}\)
\(\displaystyle{ a_3 = 18 = ((1+2) \cdot 2 +3) \cdot 2}\)
\(\displaystyle{ a_4 = 40 = ((1+2) + (3+4)) \cdot 2 \cdot 2}\)
\(\displaystyle{ a_5 = 72 = (((1+2) \cdot 2 +5) \cdot 2 + (3+4) \cdot 2) \cdot 2}\)
\(\displaystyle{ a_6 = 124 = [([((1+2) \cdot 2 +5) \cdot 2] + [6+(3+4) \cdot 2] \cdot 2)] \cdot 2}\)

Trzeba udowodnić, że \(\displaystyle{ a_n \ge \frac{4}{9} n^3}\)

Ciąg połówkowy z kolei:

Ukryta treść:    

\(\displaystyle{ b_1 = 1}\)
\(\displaystyle{ b_2 = 3}\)
\(\displaystyle{ b_3 = 9}\)
\(\displaystyle{ b_4 = 20}\)
\(\displaystyle{ b_5 = 36}\)
\(\displaystyle{ b_6 = 62}\)

\(\displaystyle{ \frac{a_n}{2} = b_n \ge \frac{2}{9} n^3}\)
W sumie myślałem, że będzie łatwo. Pobawiłbym się w poszukanie wzoru jawnego ciągu jeśli istnieje

[dec1]

Z nierówności między średnimi \(\displaystyle{ \sqrt{2x+2y}\geq \sqrt x + \sqrt y}\), zatem \(\displaystyle{ \sqrt z \geq \sum_{k=1}^n \sqrt k}\), gdzie \(\displaystyle{ z}\) to ta pozostała liczba. Lecz \(\displaystyle{ \sqrt z\geq \sum_{k=1}^n \sqrt k \geq \int_0^n \sqrt x\,\mathrm dx =\frac 23n^{3/2}}\), a stąd \(\displaystyle{ z\geq \frac 49n^3}\), cnd.

[a4karo]

Jak z \(\displaystyle{ z>2n\sqrt{n}/3}\) ma wynikać \(\displaystyle{ z>4n^3/9}\)?

[dec1]

literówka, fixed