Az A. 872. feladat (2024. február)

A. 872. Minden \(\displaystyle k\) pozitív szám esetén legyen \(\displaystyle a_{k,1}\), \(\displaystyle a_{k,2}\), \(\displaystyle \ldots\) egy pozitív egész számokból álló sorozat. Minden \(\displaystyle k\) pozitív egész szám esetén legyen az \(\displaystyle \{a_{k+1,i}\}\) sorozat az \(\displaystyle \{a_{k,i}\}\) sorozat különbségsorozata, azaz minden \(\displaystyle k\) és \(\displaystyle i\) pozitív egészre teljesül, hogy \(\displaystyle a_{k,i+1}-a_{k,i}=a_{k+1,i}\).

Lehetséges-e, hogy minden pozitív egész pontosan egyszer szerepel az \(\displaystyle a_{k,i}\) számok között?

Javasolta Matolcsi Dávid (Berkeley)

(7 pont)

A beküldési határidő 2024. március 11-én LEJÁRT.

Válasz: Lehetséges.

Úgy készítjük el a konstrukciót, hogy átlókban haladunk, azaz az \(\displaystyle n.\) lépésben az összes \(\displaystyle a_{k,l}\) értékét adjuk meg, melyekre \(\displaystyle k+l=n+1\). Első lépésben majd megadjuk az \(\displaystyle a_{1,1}\) értékét. Ezek után, ha már megcsináltuk az első \(\displaystyle (n-1)\) lépést, tehát már meghatároztunk minden \(\displaystyle a_{k,l}\) értéket, melyre \(\displaystyle k+l \leq n\), akkor az \(\displaystyle n.\) lépésben elég megadni \(\displaystyle a_{n,1}\) értékét, és ez egyértelműen meghatározza az átlót: \(\displaystyle a_{n-1, 2}=a_{n,1}+a_{n-1,1}\), majd \(\displaystyle a_{n-2,3}=a_{n-1,2}+a_{n-2,2}=a_{n,1}+a_{n-1,1}+a_{n-2,2}\), és így tovább, végül eljutunk az átló végéhez, amire \(\displaystyle a_{1,n}=a_{n,1}+a_{n-1,1}+a_{n-2,2}+\ldots +a_{1,n-1}\). Tehát összefoglalva, ha megadjuk sorban az \(\displaystyle a_{n,1}\) számokat, azok egyértelműen meghatározzák az összes sorozat összes számát, és világos, hogy ha így definiáljuk a számokat, akkor a végén tényleg olyan sorozatokat fogunk kapni, hogy az \(\displaystyle \{a_{k+1,i}\}\) sorozat az \(\displaystyle \{a_{k,i}\}\) különbségsorozata.

Az ötlet az, hogy egyszerre akarunk arra figyelni, hogy minden mezőbe különböző pozitív egész szám kerüljön, és arra, hogy minden szám előbb-utóbb valahol megjelenjen a számok között. Így arra játszunk, hogy mindig be akarjuk írni a legkisebb pozitív egész számot, amit még nem használtunk úgy, hogy közben ne jelenjen meg olyan szám, ami már volt. Ha ezt sikerül elérnünk, akkor egy megfelelő konstrukciót kapunk.

Legyen \(\displaystyle a_{1,1}=1\). Ezután felválta építünk mindig két segédátlót és egy komoly átlót. A segédátlók célja az lesz, hogy azokat olyan nagy számokkal töltjük ki, amik sokkal nagyobbak, mint az eddigi meghatározott összes szám összege, és ezek után azt állítjuk, hogy ha a komoly átló első, \(\displaystyle a_{n,1}\) elemére beírjuk a legkisebb még nem szereplő \(\displaystyle x\) számot, akkor egy olyan átlót fogunk kapni, ami nem hoz létre ismétlődést.

Amikor egy segéd-átló jön, akkor \(\displaystyle a_{n,1}\)-nek egy olyan \(\displaystyle C\) számot válasszunk, ami több mint \(\displaystyle 10\)-szer nagyobb, mint az összes eddig beírt szám összege. Ekkor a segéd-átlóba kerülő számok, \(\displaystyle C, C+a_{n-1,1}, C+a_{n-1,1}+a_{n-2,2}, \ldots , C+a_{n-1,1}+a_{n-2,2}+\ldots +a_{1,n-1}\) mind nagyobbak, mint bármelyik korábbi átlóba beírt szám, és egymástól is nyilvánvalóan különbözőek.

Amikor egy komoly átló következik, akkor előtte felépítettünk két segédátlót, ezekből az előbbinek az első elemét nevezzük \(\displaystyle C\)-nek, a később felépített átló első elemét \(\displaystyle D\)-nek. Ezek után, ahogy már írtuk, a komoly átló első mezőjébe írjuk be \(\displaystyle x\)-et, a legkisebb pozitív egész számot, amit még nem írtunk be egyik korábbi átlóba se. Már csak azt kéne megmutatni, hogy ahogyan ez meghatározza a hozzá tartozó átlót, biztosan nem kerül bele olyan szám, ami már szerepelt valahol.

Világos, hogy \(\displaystyle C>10(x-1)\ge 5x\). A komoly átló elemei a képzési szabály miatt szigorúan monoton nőnek, így egymástól mind különbözőek. Az első elem, \(\displaystyle x\), definíció szerint különbözik az összes korábbi számtól. A második elem \(\displaystyle D+x\). Mivel ez nagyobb \(\displaystyle D\)-nél, ezért csak az előző átló valamelyik elemével lehetne egyenlő, de annak első eleme \(\displaystyle D\), a második \(\displaystyle D+C>D+x\), a többi pedig ennél is nagyobb, így \(\displaystyle D+x\) sem lehet egyenlő semelyik korábban beírt elemmel. A következő elem \(\displaystyle x+D+(D+C)=2D+C+x\), a komoly-átló további elemei pedig még ennél is nagyobbak. Azt állítjuk, hogy már \(\displaystyle 2D+C+x\) is nagyobb, mint bármelyik korábban beírt szám. Ugyanis a legnagyobb korábban beírt szám az előző átló utolsó száma, amit úgy kaptunk, hogy \(\displaystyle D\)-hez hozzáadtuk az azelőtti átló összes elemének összegét. Ám \(\displaystyle D\) definíció szerint több mint \(\displaystyle 10\)-szer nagyobb, mint az összes korábban beírt szám összege, így a \(\displaystyle D\)-vel kezdődő átló utolsó eleme is kisebb, mint \(\displaystyle 2D\), így tényleg kisebb, mint \(\displaystyle 2D+C+x\).

Ezzel megadtunk sorozatok egy megfelelő sorozatát, így készen vagyunk.

Statisztika:

9 dolgozat érkezett.
7 pontot kapott:	Czanik Pál, Holló Martin, Nguyen Kim Dorka, Simon László Bence, Szakács Ábel, Varga Boldizsár, Wiener Anna.
3 pontot kapott:	1 versenyző.
1 pontot kapott:	1 versenyző.

A KöMaL 2024. februári matematika feladatai