Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?

Problem B. 4955. (April 2018)

B. 4955. Let \(\displaystyle n\) be a positive integer. What is the largest possible number of ordered triples of non-negative integers \(\displaystyle (x_1,y_1,z_1),(x_2,y_2,z_2),\ldots\) such that the following conditions hold:

(1) For all \(\displaystyle i\), \(\displaystyle x_i + y_i + z_i = n\).

(2) The numbers \(\displaystyle x_1,x_2,\ldots\) are all different, the numbers \(\displaystyle y_1,y_2,\ldots\) are all different, and the numbers \(\displaystyle z_1,z_2,\ldots\) are also all different.

Give an example for such a sequence of maximum length with the required property.

Proposed by P. Erben, Budapest

(6 pont)

Deadline expired on May 10, 2018.


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

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\).


Statistics:

23 students sent a solution.
6 points: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 points:Fleiner Zsigmond, Pituk Gábor.
4 points:2 students.
3 points:2 students.
0 point:4 students.

Problems in Mathematics of KöMaL, April 2018