Feladat:	1147. matematika gyakorlat	Korcsoport: 14-15	Nehézségi fok: átlagos
Megoldó(k):	Bauer Katalin ,  Greskovics Klára ,  Gönczi István
Füzet:	1968/május, 215 - 216. oldal		PDF  |  MathML
Témakör(ök):	Gráfelmélet, Gyakorlat
Hivatkozás(ok):	Feladatok: 1967/október: 1147. matematika gyakorlat

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.   1. ábra   a) Nevezzük az ábra két szomszédos csomópont közti vonaldarabjait útszakaszoknak, éspedig sugárútszakasznak azokat, amelyeknek egyik meghosszabbítása is útszakasz, a többieket körútszakasznak. Az ábra bármelyik csomópontjából bármelyik másikba eljuthatunk legföljebb $5$ útszakasz, éspedig $3$ körút- és $2$ sugárútszakasz megtételével. Ezért pl. az $1$-es számtól a $17$-eshez egy legrövidebb útvonalon átmenve, a $17-1=16$ egységnyi növekedésből még akkor is legalább $1$ útszakaszra $3$-nál nagyobb növekedés jut, ha az $5$ útszakasz mindegyikének megtételével nagyobb számhoz jutottunk, hiszen $16>5\cdot 3$.     2. ábra   b) A 2. ábra három olyan elrendezést mutat, amelyben a legkisebb különbség $6$ (abszolút értékben). Ezt az I. és II. elrendezésben úgy sikerült elérni, hogy számainkat kettéosztottuk ,,kicsikre'': $\mathrm{1,2,}\text{...}\mathrm{,9}$, és ,,nagyokra'': $10$, $\mathrm{11,}\text{...}\mathrm{,18}$, és minden kicsi szám szomszédainak nagyokat írtunk be és viszont. A III. elrendezés enélkül a többletkövetelmény nélkül jutott célba. Az I. és III. elrendezésben viszont a külső és belső körút egymástól $5$ útszakasznyira (vagyis legtávolabb) levő csomópont-párjain egymást $19$-re kiegészítő számok állnak, úgyszintén a középső körút átellenes pontpárjain is. Mindkét önként vállalt többlet-követelmény könnyítette, gyorsította az elrendezést.     Gönczi István (Miskolc, Földes F. gimn. II. o. t.)   Greskovics Klára (Budapest, Eötvös J. gimn. I. o. t.)   Megjegyzések. 1. Az állítást beláthatjuk a következő lokális (az ábrának csak egy kis részére vonatkozó) meggondolással is. Tekintsük az $1$-es szám szomszédait. Ha az $1$-es a középső körút valamelyik csomópontján áll, akkor $4$ szomszédja van, ezért már akkor is fellép egy $4$-es különbség, ha szomszédainak a legközelebb álló $2$, $3$, $4$, $5$-öt választjuk. Ha az $1$-esnek csak $3$ szomszédja lesz, ezeknek $2$-t, $3$-at és $4$-et véve ‐ és csak így ‐ még nincs $3$-nál nagyobb különbség. Így a $2$-es nem szomszédja $3$-nak és $4$-nek, mindenképpen van két további szomszédja. Ha ezek a lehető legkisebbek is: $5$ és $6$, akkor is fellép a $6-2=4$ különbség. Az utóbbiakhoz hasonlóan az is adódik, hogy a legkisebb különbség nem lehet $8$: Különben ugyanis $9$ szomszédai csak $1$, $17$ és $18$ lehetnének, $10$ szomszédai pedig csak $1$, $2$ és $18$, tehát sem $9$, sem $10$ nem a középső körúton állna, és mégis lenne két közös szomszédjuk: $1$ és $18$. Ez lehetetlen.     Bauer Katalin (Budapest, Berzsenyi D. gimn. II. o. t.)   2. További megjegyzéseket tartalmaz az ezen szám 202. oldalán közölt cikk.