A B. 5046. feladat (2019. október)

B. 5046. Legyen $\displaystyle n\ge3$, és tekintsük azt a gráfot, amelynek csúcsai az $\displaystyle (i,j)$ rácspontok, ahol $\displaystyle 1\le i,j\le n$, és a különböző $\displaystyle (i,j)$ és $\displaystyle (k,l)$ pontokat akkor kötjük össze éllel, ha $\displaystyle i^2+j^2+k^2+l^2$ osztható $\displaystyle 3$-mal. Mely $\displaystyle n$-ekre lehet a gráf éleit úgy bejárni, hogy mindegyik élen pontosan egyszer haladunk át?

Javasolta: Pálfy Máté (Budapest)

(4 pont)

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

Megoldás. Egy ilyen bejárást, ahol minden élen pontosan egyszer haladunk át (de nem feltétlenül szükséges a kiindulási csúcsba visszaérnünk) Euler-sétának (vagy Euler-vonalnak) hívnak. Ismert, hogy egy véges gráfban pontosan akkor létezik Euler-séta, ha egyetlen olyan komponense van, ami tartalmaz élt (más szavakkal: izolált pontok elhagyása után összefüggő gráfot kapunk), és legfeljebb két kivétellel minden csúcs foka páros. (A feltételek szükségessége nyilvánvaló, az elégségesség pedig indukcióval igazolható.)

Azt kell tehát megvizsgálnunk, összefüggő-e a gráf (izolált csúcsoktól eltekintve), és páros-e az összes fokszám esetleg két kivételtől eltekintve.

Egy egész szám négyzetének 3-as maradéka 0, ha a szám 3-mal osztható, különben pedig 1. Így négy négyzetszám összege pontosan akkor 3-mal osztható, ha mind a négy szám 3-mal osztható vagy ha közülük pontosan egy osztható 3-mal.

Ezek alapján osszuk a gráf csúcsait három csoportba:

• $\displaystyle A=\{(i,j):1\leq i,j\leq n,3\mid i,3\mid j\}$
• $\displaystyle B=\{(i,j):1\leq i,j\leq n,3\mid i,3\nmid j\}\cup \{(i,j):1\leq i,j\leq n,3\nmid i,3\mid j\}$
• $\displaystyle C=\{(i,j):1\leq i,j\leq n,3\nmid i,3\nmid j\}$

Korábbi megfigyelésünk szerint $\displaystyle A$-n belül bármely két csúcs össze van kötve, továbbá minden $\displaystyle B$-beli csúcs össze van kötve minden $\displaystyle C$-beli csúccsal. A gráfnak más éle nincsen.

Megjegyezzük, hogy sem $\displaystyle B$, sem $\displaystyle C$ nem üres (például $\displaystyle (1,3)\in B,(1,2)\in C$), így a gráf egyik összefüggőségi komponense $\displaystyle B\cup C$. Ha $\displaystyle A$-n belül van él, akkor biztosan nincs Euler-séta, hiszen két olyan komponense is van ekkor a gráfnak, amiben van él. Ha $\displaystyle n\in\{3,4,5\}$, akkor $\displaystyle A=\{(3,3)\}$, vagyis $\displaystyle A$ csak egyetlen izolált csúcsot tartalmaz. Ha $\displaystyle n\geq 6$, akkor $\displaystyle A$-n belül már van legalább 2 csúcs, és így él is, például a $\displaystyle (3,3)$ és $\displaystyle (3,6)$ csúcsok között.

Ezek alapján $\displaystyle n\geq 6$ esetén nincsen Euler-körséta, $\displaystyle 3\leq n\leq 5$ esetén pedig azt kell megvizsgálni, hogy mi a csúcsok fokszáma.

Legyen tehát $\displaystyle 3\leq n\leq 5$. Ilyenkor minden $\displaystyle A$-beli csúcs fokszáma 0, minden $\displaystyle B$-beli csúcs fokszáma $\displaystyle |C|$ és minden $\displaystyle C$-beli csúcs fokszáma $\displaystyle |B|$. Vagyis $\displaystyle B$ és $\displaystyle C$ méretét kell megvizsgálnunk. Az $\displaystyle 1,2,\dots,n$ számok között $\displaystyle [n/3]$ darab 3-mal osztható van, így

$\displaystyle |B|=2[n/3]\left(n-[n/3]\right)$

(kiválasztunk egy 3-mal osztható és egy 3-mal nem osztható értéket, az egyik lesz $\displaystyle i$, a másik $\displaystyle j$),
illetve

$\displaystyle |C|=(n-[n/3])^{2}.$

Ezek alapján $\displaystyle 3\leq n\leq 5$ esetekben $\displaystyle B$ és $\displaystyle C$ mérete így alakul:

Így az $\displaystyle n=3,4,5$ esetekben a páratlan fokú csúcsok száma rendre $\displaystyle 0,6,0$. Tehát Euler-séta az $\displaystyle n=3,5$ esetekben létezik, hiszen ekkor teljesül, hogy legfeljebb 2 páratlan fokú csúcs van.

Megmutattuk, hogy pontosan akkor járhatók be az élek úgy, hogy minden élt pontosan egyszer használjunk, ha $\displaystyle n\in\{3,5\}$.

Statisztika:

116 dolgozat érkezett.
4 pontot kapott:	66 versenyző.
3 pontot kapott:	22 versenyző.
2 pontot kapott:	9 versenyző.
1 pontot kapott:	15 versenyző.
0 pontot kapott:	4 versenyző.

A KöMaL 2019. októberi matematika feladatai