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

Problem A. 823. (March 2022)

A. 823. For positive integers \(\displaystyle n\) consider the lattice points \(\displaystyle S_n=\big\{(x,y,z)\colon 1\le x\le n\), \(\displaystyle 1\le y\le n\), \(\displaystyle 1\le z\le n\), \(\displaystyle x,y,z\in \mathbb{N}\big\}\). Is it possible to find a positive integer \(\displaystyle n\) for which it is possible to choose more than \(\displaystyle n\sqrt{n}\) lattice points from \(\displaystyle S_n\) such that for any two chosen lattice points at least two of the coordinates of one is strictly greater than the corresponding coordinates of the other?

Proposed by Endre Csóka, Budapest

(7 pont)

Deadline expired on April 11, 2022.


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

Megoldás. Válasz: Igen.

Nevezzünk érdekes kiválasztásnak egy rácsban egy a feladat feltételeinek megfelelő részhalmazt, azaz ahol bármely két kiválasztott pontból az egyiknek legalább két koordinátája szigorúan nagyobb, mint a másiknak a megfelelő koordinátái.

Először tekintsünk a konstrukció szempontjából egy egyszerűbb feladatot: \(\displaystyle a \times b \times c\) méretű rácsban szeretnénk kiválasztani \(\displaystyle \sqrt{abc}\)-nél több rácspontot érdekes módon.

1. lemma: Tegyük fel, hogy az \(\displaystyle a \times b \times c\) méretű rácsnak van \(\displaystyle x\) méretű érdekes kiválasztása, és a \(\displaystyle d \times e \times f\) méretű rácsnak van \(\displaystyle y\) méretű érdekes kiválasztása. Ekkor egy \(\displaystyle ad \times be \times cf\) méretű rácsnak van \(\displaystyle xy\) elemből álló érdekes kiválasztása.

Bizonyítás: Osszuk fel az \(\displaystyle ad \times be \times cf\) méretű rácsot \(\displaystyle a \times b \times c\) darab \(\displaystyle d \times e \times f\) méretű rácsra. Tekintsük az \(\displaystyle x\) méretű érdekes konstrukciót az \(\displaystyle a \times b \times c\) méretű rácsban, és jelöljük be azokat a \(\displaystyle d \times e \times f\) rácsokat, amik benne vannak az \(\displaystyle x\) kiválasztott mezőben. Ezek után minden bejelölt kis rácsban vegyük eltolva a \(\displaystyle d \times e \times f\)-es rácsban az \(\displaystyle y\) méretű érdekes konstrukciót. Ezzel tehát összesen \(\displaystyle x\) darab kis \(\displaystyle d \times e \times f\)-es rácsban választottunk, mindben \(\displaystyle y\) pontot, így összesen \(\displaystyle xy\)-t. Könnyű látni, hogy ez tényleg érdekes kiválasztás.

2. lemma: Tegyük fel, hogy valamilyen \(\displaystyle a,b,c\) esetén tudunk érdekes konstrukciót mutatni több, mint \(\displaystyle \sqrt{abc}\) kiválaszott ponttal. Ekkor \(\displaystyle n=abc\) esetén tudunk érdekes konstrukciót mutatni az \(\displaystyle n \times n \times n\) méretű rácson is több, mint \(\displaystyle n\sqrt{n}\) ponttal.

Bizonyítás: Legyen \(\displaystyle x>\sqrt{abc}\) az érdekes konstrukció mérete. Ekkor az előző lemmát alkalmazva az \(\displaystyle a \times b \times c\) és a \(\displaystyle b \times c \times a\) méretű rácsra kapjuk, hogy van \(\displaystyle x^2\) méretű konstrukció az \(\displaystyle ab \times bc \times ca\) méretű rácsra. Még egyszer alkalmazva a lemmát erre és a \(\displaystyle c \times a \times b\) méretű rácsra kapjuk, hogy az \(\displaystyle n \times n \times n\)-es rácson van \(\displaystyle x^3\) méretű konstrukció, és \(\displaystyle x^3 > \sqrt{abc}^3=n\sqrt{n}\), pont ahogy akartuk.

Tehát a feladat megoldásához most már elég az általánosabb feladatra egy konstrukciót találni. Megmutatjuk, hogy \(\displaystyle 4 \times 4 \times 5\) méretű rácsban van \(\displaystyle 9\)-re konstrukció, amivel kész vagyunk, mivel \(\displaystyle 9>\sqrt{80}=\sqrt{4 \cdot 4 \cdot 5}\).

Nézzünk rá a rácsra felülről, azaz hogy egy \(\displaystyle 4 \times 4\) méretű táblázatot lássunk, mindenhol egymás alatt \(\displaystyle 5\) pont. Minden ilyen \(\displaystyle 5\) magas oszlopból csak egy pontot választhatunk, így egy konstrukciót egyértelműen meg lehet adni úgy, hogy egy \(\displaystyle 4 \times 4\) méretű táblázat minden mezőjébe beírjuk, hogy onnan hányadik pontot választjuk, vagy nem írunk semmit, ha abból az oszlopból nem választunk semmit. Azaz ha az \(\displaystyle (i,j,k)\) mezőt kiválasztjuk, az azt jelenti, hogy a táblázat \(\displaystyle (i,j)\) mezőjébe \(\displaystyle k\)-t írunk. Könnyű meggondolni, hogy egy ilyen táblázat által meghatározott kiválasztás pontosan akkor érdekes, ha soronként és oszloponként a beírt számok szigorúan monoton nőnek, és nincsenek olyan \(\displaystyle (i,j)\) és \(\displaystyle (i',j')\) mezők, melyekbe ugyanazt a számot írtuk, és \(\displaystyle (i-i')(j-j')<0\). Ezzel a jelöléssel látható, hogy a következő konstrukció megfelelő, így a megoldás készen van.


Statistics:

0 student sent a solution.

Problems in Mathematics of KöMaL, March 2022