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