A B. 4955. feladat (2018. április)

B. 4955. Legyen \(\displaystyle n\) pozitív egész. Nemnegatív egészekből legfeljebb hány \(\displaystyle (x_1,y_1,z_1),(x_2,y_2,z_2),\ldots\) rendezett hármast lehet megadni úgy, hogy a következő feltételek teljesüljenek?

(1) Mindegyik \(\displaystyle i\)-re \(\displaystyle x_i + y_i + z_i = n\).

(2) Az \(\displaystyle x_1,x_2,\ldots\) számok mind különbözők, az \(\displaystyle y_1,y_2,\ldots\) számok mind különbözők, és a \(\displaystyle z_1,z_2,\ldots\) számok is mind különbözők.

Adjunk meg egy ilyen tulajdonságú, maximális hosszúságú sorozatot.

Javasolta: Erben Péter (Budapest)

(6 pont)

A beküldési határidő 2018. május 10-én LEJÁRT.

Megoldás. Tegyük fel, hogy meg lehet adni \(\displaystyle s\) darab hármast a feltételeknek megfelelően. Ekkor egyrészt

\(\displaystyle S:=\sum\limits_{i=1}^s (x_i+y_i+z_i)=sn\)

az (1) feltétel szerint, másrészt az

\(\displaystyle S_1:=\sum\limits_{i=1}^n x_i,S_2:=\sum\limits_{i=1}^n y_i,S_3:=\sum\limits_{i=1}^n z_i\)

összegek mindegyike legalább \(\displaystyle 0+1+2+\dots+(s-1)=\frac{(s-1)s}{2}\) a (2) feltétel alapján. Mivel \(\displaystyle S=S_1+S_2+S_3\), ezért

\(\displaystyle 3 \cdot \frac{(s-1)s}{2}\leq sn,\)

amiből \(\displaystyle s\leq\frac{2}{3}n+1\). Mivel a hármasok \(\displaystyle s\) száma egész, ezért \(\displaystyle s\leq \left\lfloor \frac{2}{3}n \right\rfloor+1\).

Most megmutatjuk, hogy \(\displaystyle s= \left\lfloor \frac{2}{3}n \right\rfloor+1\) darab hármast meg lehet adni a feltételeknek megfelelően.

Legyen először \(\displaystyle n=3k\) (ahol \(\displaystyle k\) nemnegatív egész szám), ekkor \(\displaystyle \left\lfloor \frac{2}{3}n \right\rfloor+1=2k+1\) darab hármast kell megadnunk. Könnyen ellenőrizhetjük, hogy az alábbi például egy megfelelő konstrukció:

\(\displaystyle (0,k,2k),(2,k-1,2k-1),(4,k-2,2k-2),\dots,(2k,0,k),\)

\(\displaystyle (1,2k,k-1),(3,2k-1,k-2),(5,2k-2,k-3),\dots,(2k-1,k+1,0).\)

(Például \(\displaystyle n=6\) esetén \(\displaystyle (0,2,4),(2,1,3),(4,0,2),(1,4,1),(3,3,0)\).)

Ha itt minden hármas első koordinátáját 1-gyel növeljük, akkor egy olyan megfelelő konstrukciót kapunk \(\displaystyle n=3k+1\) esetén, ami \(\displaystyle 2k+1\) hármasból áll. Mivel \(\displaystyle \left\lfloor \frac{2}{3}(3k+1) \right\rfloor+1=2k+1\), ezért ezekben az esetekben is találtunk megfelelő méretű konstrukciót.

(Például \(\displaystyle n=7\) esetén \(\displaystyle (1,2,4),(3,1,3),(5,0,2),(2,4,1),(4,3,0)\).)

Ha pedig a fenti konstrukcióban minden hármas első koordinátáját 1-gyel csökkentjük, és a legelső hármast (aminek első koordinátája így már negatívvá vált) elhagyjuk, akkor egy olyan megfelelő konstrukciót kapunk \(\displaystyle n=3k-1\) esetén, ami \(\displaystyle 2k\) hármasból áll. Mivel \(\displaystyle \left\lfloor \frac{2}{3}(3k-1) \right\rfloor+1=2k\), ezért ezekben az esetekben is találtunk megfelelő méretű konstrukciót.

(Például \(\displaystyle n=5\) esetén \(\displaystyle (1,1,3),(3,0,2),(0,4,1),(2,3,0)\).)

(Megjegyezzük, hogy az \(\displaystyle n=0\) eset vizsgálatát a feladat nem kérte, de a fenti gondolatmenetet követve \(\displaystyle n=1\) esetén a konstrukció megadásához használtuk az \(\displaystyle n=0\) esetén adott konstrukciót. Természetesen \(\displaystyle n=1\) esetén más módon is könnyen mutathatunk megfelelő konstrukciót.)

Ezzel minden \(\displaystyle n\) pozitív egész számra megadtunk egy \(\displaystyle \left\lfloor \frac{2}{3}n \right\rfloor+1\) darab hármasból álló konstrukciót, mely bizonyítja, hogy a megadható hármasok maximális száma valóban \(\displaystyle \left\lfloor \frac{2}{3}n \right\rfloor+1\).

Statisztika:

23 dolgozat érkezett.
6 pontot kapott:	Beke Csongor, Deák Bence, Dobák Dániel, Füredi Erik Benjámin, Gáspár Attila, Janzer Orsolya Lili, Kántor András Imre, Schrettner Jakab, Soós 314 Máté, Szabó 417 Dávid, Szabó 864 Blanka, Szabó 997 Balázs István, Weisz Máté.
5 pontot kapott:	Fleiner Zsigmond, Pituk Gábor.
4 pontot kapott:	2 versenyző.
3 pontot kapott:	2 versenyző.
0 pontot kapott:	4 versenyző.

A KöMaL 2018. áprilisi matematika feladatai