Feladat:	B.5100	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Baski Bence ,  Füredi Erik Benjámin ,  Kovács Tamás ,  Nádor Benedek ,  Németh Márton ,  Sztranyák Gabriella
Füzet:	2021/április, 219 - 220. oldal		PDF  |  MathML
Témakör(ök):	Feladat, Oszthatósági feladatok, Egész számok összege, Skatulyaelv
Hivatkozás(ok):	Feladatok: 2020/április: B.5100

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre. $\begin{array}{c}{\displaystyle 1+2+\text{...}+n=\frac{n\left(n+1\right)}{2}\mathrm{.}}\end{array}$ $n$ darab egymást követő egész szám teljes maradékrendszert alkot modulo $n$, az $\left(n+1\right)$-gyel osztva pedig egy kivételével (legyen ez a kivétel $d$) minden maradékot felvesz. Az $n$ darab egymást követő egész szám közül kössünk össze kék színű éllel két számot, ha az összegük osztható $n$-nel, illetve pirossal, ha $\left(n+1\right)$-gyel osztható az összegük. Így egy $n$ csúcsú gráfot kapunk, amiben minden csúcs fokszáma legfeljebb 2, és minden csúcsból legfeljebb egy piros és egy kék él indul ki. Tekintsük a gráf összefüggő komponenseit. Mivel minden csúcs legfeljebb másodfokú, egy ilyen komponens csak kör, alternáló (váltakozó színű egymáshoz csatlakozó élekből álló) út, vagy izolált pont lehet. Minden számból kiindul egy piros és egy kék él, kivéve az $n$-nel osztva $0$ és ‐ páros $n$ esetén ‐ $\frac{n}{2}$ maradékot adó ($A$ és $B$), valamint az $\left(n+1\right)$-gyel osztva $0$ és (páratlan $n$ esetén) $\frac{n+1}{2}$ maradékot adó ($C$ és $E$), illetve esetleg az $n+1-d$ maradékot adó $D$ számokból. Tekintsük az $A$ csúcsot tartalmazó komponenst, ami ‐ mivel $A$-ból nem indul kék él ‐ csakis alternáló út lehet. Ha ennek az alternáló útnak a másik végpontja nem a $D$ csúcs, akkor ezen alternáló út csúcsainak megfelelő számok összege osztható $n\left(n+1\right)/2$-vel: 1. Ha a másik végpont $B$, akkor $n$ páros, és $A+B\equiv 0+\frac{n}{2}\left(\text{mod}n\right)$ osztható $\frac{n}{2}$-vel, a többi szám a kék élek mentén párokba állítható, ezért összegük osztható $n$-nel. Az út valamennyi csúcsát a piros élek mentén párokba állítva adódik, hogy a megfelelő számok összege osztható $\left(n+1\right)$-gyel. Az egymáshoz relatív prím $\frac{n}{2}$ és $n+1$ számokkal való oszthatóságból következik, hogy az összeg $\frac{n}{2}\cdot \left(n+1\right)$-gyel is osztható. 2. Ha a másik végpont $C$, akkor a kék élek mentén történő párokba állításból csak az ($n$-nel osztható) $A$ marad ki, a többiek összege osztható $n$-nel. A piros élek mentén párokba állításból csak a $C$ marad ki, ami viszont osztható $\left(n+1\right)$-gyel, ezért ekkor az útba eső számok összege még $n\left(n+1\right)$-gyel is osztható. 3. Ha a másik végpont $E$, akkor a helyzet az előbbihez hasonló, mindössze $E$ csupán $\frac{n+1}{2}$-vel osztható, amiből pontosan a kívánt állítást kapjuk. Ha viszont a $D$ csúcs a másik végpont, akkor $C$ is csúcsa a gráfnak, és a $C$-t tartalmazó alternáló út komponens másik végpontja ‐ $n$ párosságától, illetve páratlanságától függően ‐ $B$ vagy $E$. Ekkor ‐ a fenti esetekhez hasonlóan ‐ ez utóbbi alternáló úthoz tartozó összeg lesz $n\left(n+1\right)/2$ többszöröse, tehát készen vagyunk.   Nádor Benedek (Budapesti Fazekas M. Gyak. Ált. Isk. és Gimn., 9. évf) megoldása alapján