Problem B. 5462. (May 2025)

B. 5462. Abel has written down the positive integers from 1 to \(\displaystyle n\) in a certain order. Any positive integer from 1 to \(\displaystyle \frac{n(n+1)}{2}\) can be obtained as the sum of some consecutive terms from Ábel's sequence. For which values of \(\displaystyle n\) is this possible?

Proposed by: Erik Füredi, Budapest

(4 pont)

Deadline expired on June 10, 2025.

Sorry, the solution is available only in Hungarian. Google translation

Megoldás. Először vizsgáljuk meg, hogy egyáltalán hányféle összeg állhat elő. Ha az első \(\displaystyle n\) számot \(\displaystyle a_1,a_2,...,a_n\) sorrendben írjuk le, és az összeg első tagja \(\displaystyle a_i\), míg utolsó tagja \(\displaystyle a_j\) (ahol \(\displaystyle i \leq j\) megengedve az \(\displaystyle i=j\) esetet, azaz az ,,egytagú összegeket''), akkor az \(\displaystyle (i,j)\) indexpár \(\displaystyle i=j\) esetén \(\displaystyle n\)-féleképpen, míg \(\displaystyle i<j\) esetén \(\displaystyle \binom{n}{2}=\frac{n(n-1)}{2}\)-féleképpen választható ki, azaz összesen legfeljebb \(\displaystyle n+\frac{n(n-1)}{2}=\frac{n(n+1)}{2}\) különböző összeg lehet. Emiatt ha van olyan összeg, ami legalább kétféleképpen előáll, akkor nem jöhet ki minden lehetséges összeg \(\displaystyle 1\)-től \(\displaystyle \frac{n(n+1)}{2}\)-ig.

\(\displaystyle n=1,2,3\) esetén az \(\displaystyle 1\), \(\displaystyle 12\) és \(\displaystyle 132\) sorrendek jók. Megmutatjuk, hogy további \(\displaystyle n\)-ekre nincsenek jó sorrendek.

Legyen \(\displaystyle n >3\), és vizsgáljuk az \(\displaystyle 1,2,...,n\) számok egy sorrendjét.

Ha helyes sorrendet szeretnénk, akkor az \(\displaystyle 1\) csak a szélén lehet, és a szomszédja csak \(\displaystyle n\) lehet, mivel ha lenne \(\displaystyle n\)-nél kisebb szomszéd, mondjuk \(\displaystyle k\), akkor \(\displaystyle k+1 \leq n\) többféleképpen (egytagú és kéttagú összegként is) előállna. Mivel \(\displaystyle n\) az \(\displaystyle 1\) szomszédja, emiatt az \(\displaystyle n+1\) összeg előállítását meg is kaptuk.

Hasonlóan gondolkozva a \(\displaystyle 2\) szomszédjai csak \(\displaystyle (n-1)\) és \(\displaystyle n\) lehetnének, de az \(\displaystyle (n-1)\) nem lehet (mert az előzőek alapján akkor az \(\displaystyle (n+1)\)-es összeg állna elő legalább kétféleképp). Azaz \(\displaystyle 2\) egyetlen szomszédja csak \(\displaystyle n\) lehet. De akkor az \(\displaystyle 1\) és a \(\displaystyle 2\) is a szélén van, és mindkettő szomszédja \(\displaystyle n\), ami nem fordulhat elő \(\displaystyle n>3\) esetén.

Azaz \(\displaystyle n\) csak \(\displaystyle 1\), \(\displaystyle 2\) vagy \(\displaystyle 3\) lehet.

Statistics:

62 students sent a solution.
4 points:	Ali Richárd, Aravin Peter, Balla Ignác , Baran Júlia, Beinschroth Máté, Bencze Mátyás, Blaskovics Ádám, Bodor Ádám, Bogdán Balázs Ákos, Bolla Donát Andor, Bővíz Dániel, Bui Thuy-Trang Nikolett, Csató Hanna Zita , Fajszi Horka, Guthy Gábor, Gyenes Károly, Hajba Milán, Halmosi Dávid, Hideg János, Hodossy Réka, Holló Martin, Horák Zsófia, Illés Dóra, Kerekes András, Klement Tamás, Kurucz Lilien Jázmin, Li Mingdao, Ligeti Ábel, Maróti Bálint, Miszori Gergő, Molnár Lili, Pázmándi József Áron, Péter Hanna, Rajtik Sándor Barnabás, Sajter Klaus, Sánta Gergely Péter, Sárdinecz Dóra, Sha Jingyuan, Sütő Áron, Szaszkó Benedek, Szekrényes Sára Róza, Tóth László Pál, Török Eszter Júlia, Várhegyi Hanna, Varsányi Benedek, Vigh 279 Zalán, Wágner Márton, Wiener Marcell, Zhai Yu Fan.
3 points:	2 students.
2 points:	4 students.
1 point:	1 student.
0 point:	4 students.

Problems in Mathematics of KöMaL, May 2025