A B. 4938. feladat (2018. február)

B. 4938. Ismert, hogy a tórusz felületére rá lehet rajzolni a \(\displaystyle 7\) pontú teljes gráfot (lásd pl. a Császár-poliédert). Egy sárga görbe bögre oldalán kijelölünk 7 pontot, és bármelyik kettőt össze akarjuk kötni egy-egy görbével úgy, hogy semelyik két görbének ne legyen közös belső pontja. Legalább hány görbét kell ennek eléréséhez átvezetnünk a görbe bögre fülén?

(6 pont)

A beküldési határidő 2018. március 12-én LEJÁRT.

Megoldás. Először megmutatjuk, hogy a \(\displaystyle 7\)-pontú teljes gráf felrajzolásához legalább \(\displaystyle 6\) élt biztosan át kell vezetnünk a bögre fülén, majd egy példát mutatunk a gráf egy lehetséges felrajzolására, amikor éppen \(\displaystyle 6\) élt vezetünk át a fülön.

I. Ha elhagyjuk a bögre fülét és a rajta átvezetett görbéket, a fületlen görbe felülete a gömbbe folytonosan deformálható lesz, ezért a \(\displaystyle 7\) pont a megmaradó görbékkel egy síkba rajzolható gráfot alkot. Azt állítjuk, hogy ennek a \(\displaystyle 7\)-pontú síkgráfnak legfeljebb \(\displaystyle 15\) éle lehet. Ha esetleg a gráf nem összefüggő, néhány újabb élgörbe megrajzolásával összefüggővé tehetjük. Ezért állításunkat elég összefüggő gráfokra igazolni.

A gráf élei (a megmaradó, a fülön át nem vezetett görbék) a bögre felületét (legalább háromoldalú) tartományokra osztják; legyen az élek száma \(\displaystyle E\), a tartományok (lapok) száma \(\displaystyle L\); a csúcsok száma \(\displaystyle C=7\). Azt akarjuk megmutatni, hogy \(\displaystyle E\le 15\).

Az Euler-féle poliédertétel szerint \(\displaystyle C+L=E+2\), vagyis

\(\displaystyle L=E-5. \tag{1} \)

Számoljuk össze kétféleképpen az egymáshoz illeszkedő lap-él párokat. Mindegyik él pontosan két laphoz illeszkedik, és minden lap legalább 3 élhez, tehát

\(\displaystyle 2E \ge 3L. \)

Ebbe beírva (1)-et,

\(\displaystyle 2E \ge 3(E-5), \)

vagyis valóban \(\displaystyle E\le15\).

A \(\displaystyle 7\)-pontú teljes gráfnak \(\displaystyle \binom72=21\) éle van, tehát legalább \(\displaystyle 6\) élt biztosan át kell vezetnünk a bögre fülén a gráf lerajzolásához.

II. A bal oldali ábrán a \(\displaystyle 7\)-pontú teljes gráf egy jól ismert felrajzolása látható a tóruszfelületre. A téglalapot hajlítsuk meg, és a két függőleges oldalt ragasszuk egymáshoz; így egy csövet kapunk. A cső két végét is egymáshoz ragasztva megkapjuk a tóruszfelületet, rajta a a \(\displaystyle 7\)-pontú teljes gráffal. A kék élek és a lila él együtt egy \(\displaystyle 7\) hosszú kört alkotnak; ebben a piros élek a másod-, a zöld élek a harmadszomszédos pontokat kötik össze egymással.

A cső két, egymáshoz ragasztott végén (a téglalap alsó és felső oldalán) éppen \(\displaystyle 6\) él halad keresztül; ha tehát a csövet a bögre oldalára rajzoljuk, elég ezt a \(\displaystyle 6\) élt átvezetnünk a bögre fülén, ahogy a jobb oldali ábra is mutatja.

Válogatás a beküldött dolgozatok konstrukcióiból

Hervay Bence

Soós Máté

Pituk Gábor ötletéből
(A hatszög szemközti oldalait ragasztjuk össze; a fül lehet például a piros és narancsszínű oldalak által alkotott zárt görbe.)

Gáspár Attila

Statisztika:

30 dolgozat érkezett.
6 pontot kapott:	Döbröntei Dávid Bence, Gáspár Attila, Hegedűs Dániel, Hervay Bence, Kerekes Anna, Nagy Nándor, Schifferer András, Schrettner Jakab, Soós 314 Máté, Szabó 417 Dávid.
5 pontot kapott:	Füredi Erik Benjámin.
4 pontot kapott:	6 versenyző.
3 pontot kapott:	3 versenyző.
2 pontot kapott:	3 versenyző.
0 pontot kapott:	7 versenyző.

A KöMaL 2018. februári matematika feladatai