Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

Az A. 823. feladat (2022. március)

A. 823. Legyen \(\displaystyle n\) pozitív egész, és tekintsük az \(\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\}\) kockarácsot. Létezik-e olyan \(\displaystyle n\) pozitív egész, melyre ki lehet választani \(\displaystyle S_n\) elemei közül több, mint \(\displaystyle n\sqrt{n}\)-t úgy, hogy bármely két kiválasztott rácspont közül az egyiknek legalább két koordinátája szigorúan nagyobb legyen, mint a másik megfelelő két koordinátája?

Javasolta: Csóka Endre (Budapest)

(7 pont)

A beküldési határidő 2022. április 11-én LEJÁRT.


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.


Statisztika:

0 dolgozat érkezett.

A KöMaL 2022. márciusi matematika feladatai