Problem B. 5046. (October 2019)

B. 5046. Let \(\displaystyle n\ge3\), and consider the graph in which the vertices are the grid points \(\displaystyle (i,j)\), where \(\displaystyle 1\le i,j\le n\), and the distinct points \(\displaystyle (i,j)\) and \(\displaystyle (k,l)\) are connected by an edge if and only if \(\displaystyle i^2+j^2+k^2+l^2\) is divisible by \(\displaystyle 3\). For what values of \(\displaystyle n\) is it possible to walk the edges of the graph by traversing each edge exactly once?

Proposed by M. Pálfy, Budapest

(4 pont)

Deadline expired on November 11, 2019.

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

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

Statistics:

116 students sent a solution.
4 points:	66 students.
3 points:	22 students.
2 points:	9 students.
1 point:	15 students.
0 point:	4 students.

Problems in Mathematics of KöMaL, October 2019