Viikkotehtävä: kolmen mittaiset osajonot (viikko 47/2018)

kombinatoriikka
epäyhtälöt

#1

Viikkotehtävä

Vastausaikaa su 25.11.2018 klo 24 asti
Vastausaika on päättynyt. Voit keskustella tehtävästä ja sen ratkaisuideoista vapaasti tässä ketjussa.

Tehtävä

Olkoon A=(a_1,a_2,\dots,a_{2019}) positiivisten kokonaislukujen jono. Olkoon M sellaisten kolmikoiden (i,j,k) lukumäärä, joille 1\le i<j<k\le 2019, a_j=a_i+1 ja a_k=a_j+1. Mikä on suurin mahdollinen M:n arvo, kun A voi olla mikä tahansa ehdot toteuttava lukujono?


#2

#3

#4

On helppo arvata, että maksimiarvo on M=\left(\frac{2019}{3}\right)^3, johon päästään esim. jonolla (0,\dots,0,1,\dots,1,2,\dots,2), jossa kutakin lukua on yhtä paljon. Mutta pitäisi tietysti todistaa, että suurempaa arvoa ei voi saada.

Havaitaan ensiksi, että sellainen operaatio, jossa vaihdetaan keskenään a_i ja a_{i+1}, ei pienennä M:n arvoa, jos a_i>a_{i+1}. (Kaikki mahdolliset vanhat kolmikot jäävät mahdollisiksi, lisäksi voi tulla uusia kolmikoita.) Siksi voidaan olettaa, että a_i\le a_{i+1} kaikilla i, toisin sanottuna A on kasvava jono.

Toiseksi havaitaan, että jos kasvavassa jonossa on sellaisia aukkoja, että a_{i+1}=a_i+1+d, missä d\gt 0, ei pienennä M:n arvoa jos indeksistä i+1 alkaen kustakin alkiosta vähennetään d. Voidaan siis olettaa, että jono on muotoa

(\underbrace{a,a,\dots,a}_{t_1}, \underbrace{a+1,a+1,\dots,a+1}_{t_2}, \dots, \underbrace{a+s-1,a+s-1,\dots,a+s-1}_{t_s}).

Tällaiselle jonolle

M=t_1t_2t_3 + t_2t_3t_4 + \dots + t_{s-2}t_{s-1}t_s.

Kyse on siis luvun 2019 partitioinnista positiivisten kokonaislukujen summaksi niin, että M maksimoituu. Oletetaan, että s>4. Jos partitio \left<t_1,t_2,\dots,t_s\right> korvataan partitiolla \left<t_2,t_3,t_4+t_1,\dots,t_s\right>, saadaan

M' = t_2t_3(t_4+t_1) + t_3(t_4+t_1)t_5 + \dots = t_1(t_2t_3 + t_3t_5 + t_5t_6) + M - t_1t_2t_3

(missä t_6=0 jos s=5). Selvästi M'>M, joten yli neljään osaan partitioimalla ei saada maksimaalista lopputulosta. Sama operaatio tapauksessa s=4 tuottaa partition kolmeen osaan, jolle M:n arvo on sama, joten maksimi voidaan saavuttaa, kun s=3. Silloin \left<673,673,673\right> on selvästi optimaalinen partitio. Myös partitiot muotoa \left<a,673,673,673-a\right> tuottavat saman arvon M:lle.