Zadanie

Každá sušička, a teda aj tá, ktorú KMSáci ukradli z FKSka do KMSka, musí byť veľmi presne nakalibrovaná – jedna nedotiahnutá šrauba môže spôsobiť, že vám sušička namiesto rúk vysuší humor. Preto existuje dozorný orgán, takzvaný DRDOL – Dozorný Rád pre Dehydratáciu a Odvlažovanie Labiek (DRDOL), ktorý posudzuje či je sušička správne nakalibrovaná alebo nie. Ako určite viete, slovo rad je synonymum pre slovo postupnosť, preto:

Majme postupnosť reálnych čísel \(a_1, a_2, \dots, a_n\), ktoré spĺňajú, že súčty \(a_i+a_j\), kde \(1 \leq i < j \leq n\), tvoria v nejakom poradí aritmetickú postupnosť s \(\frac{1}{2}n(n-1)\) členmi, kde \(n\) je prirodzené číslo väčšie alebo rovné ako \(5\). Dokážte, že \(a_1=a_2=\ldots=a_n\).

Prvý (a asi najdôležitejší) krok je určiť si BUNV1 \(a_1\leq \dots \leq a_n\). Toto spraviť môžeme, pretože tak či tak sa každá dvojica \(a_i+a_j\) bude vyskytovať v usporiadanej aj neusporiadanej postupnosti práve raz. Môžeme dokonca uBUNVovať aj viac – môžeme povedať že \(a_0=0\) a diferencia výslednej aritmetickej postupnosti \(d=1\), ale toto nebudeme potrebovať.

Označme si pár vecí, aby sa nám krajšie pracovalo. Nech \(MAX=n(n-1)/2\). Našu aritmetickú postupnosť si označme ako \(\{b_k: k\leq MAX\}\), t. j. \(b_k=a_i+a_j\) je \(k\)-ty najmenší člen (pre nejakú dvojicu \(i,j\)). Taktiež si označme \(d=b_k-b_{k-1}\) jej diferenciu (diferencia je všeobecný pojem pre rozdiel dvoch členov aritmetickej postupnosti).

Zjavne najmenší súčet budú tvoriť dve najmenšie čísla, teda \(b_1=a_1+a_2\). Obdobne aj \(b_2=a_1+a_3\), \(b_{MAX}=a_{n-1}+a_n\) a \(b_{MAX-1}=a_{n-2}+a_n\). Verte či nie, už je to skoro vyriešené. Ak si vezmeme, že platí \[b_1+b_{MAX}=b_1+b_{MAX-1}+d=b_2+b_{MAX-1},\] tak po rozpísaní získame \[(a_1+a_2)+(a_{n-1}+a_n)=(a_1+a_3)+(a_{n-2}+a_n),\] \[a_2+a_{n-1}=a_3+a_{n-2}.\]

A máme hotovo. Čože? Kde je riešenie? Ak \(n>5\), tak obe strany rovnice sú niektoré rôzne členy v našej postupnosti \(\{b_k\}\), pretože postupnosť \(\{b_k\}\) je tvorená z členov \(a_i+a_j\) pre všetky \(i,j\leq n\). Ak sa ale dva členy v aritmetickej postupnosti rovnajú, tak musí byť celá postupnosť konštantná, pretože jej diferencia je 0. Teda aj pôvodná postupnosť \(\{a_k\}\) musí byť konštantná.

Treba ale rozlíšiť prípad \(n=5\), na ktorý sa ľahko zabudne. Pre \(n=5\) platí \(a_2+a_4=2a_3\), resp. \(a_4-a_3=a_3-a_2=b_2-b_1=d\). Za súčtom \(b_2=a_1+a_3\) musí nasledovať súčet \(b_3=a_1+a_4\), pretože je presne o \(d\) väčší. Z tohto rovno vyplývajú iba dve možné poradia, ktoré môžu nastať:

\[a_1+a_2<a_1+a_3<a_1+a_4<a_1+a_5<a_2+a_3<a_2+a_4<a_3+a_4<a_2+a_5<a_3+a_5<a_4+a_5,\]

\[a_1+a_2<a_1+a_3<a_1+a_4<a_2+a_3<a_2+a_4<a_3+a_4<a_1+a_5<a_2+a_5<a_3+a_5<a_4+a_5.\]

V prvom prípade stačí odčítať \(d=(a_1+a_5)-(a_1+a_4)=a_5-a_4\), z čoho dostávame \(a_2+a_5=a_2+a_4+d=a_3+a_4\).V druhom prípade dostaneme obdobne \(a_1+a_4=a_2+a_3\). Každopádne sme teda našli dva rôzne členy v \(b\)-čkovej postupnosti, ktoré majú rovnakú hodnotu, a teda nutne celá postupnosť musí byť konštantná.

  1. BUNV znamená bez ujmy na všeobecnosti. Teda môžeme predpokladať že niečo platí, pretože či to platí, či nie, výsledok vyjde rovnaký↩︎

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.