A C. 1422. feladat (2017. május)

C. 1422. Egy téglalap alaprajzú egyszintes lakásban bármely két helyiség között legfeljebb egy ajtó nyílik. Ezen kívül bármely helyiségből legfeljebb egy ajtó nyílik a lakáson kívülre. Legfeljebb hány ajtó tartozhat a lakáshoz, ha négy helyiség található benne?

(5 pont)

A beküldési határidő 2017. június 12-én LEJÁRT.

Megoldás. Szemléltessük a feladatot egy 5 csúcsú egyszerű gráffal, melynek csúcsai a négy szobát és a külső teret jelentik. Két pont között van él, ha a két térrész között van ajtó. Az 5 csúcsú teljes gráf éleinek száma 10. Tehát maximum 10 ajtó lehetne. De a gráfnak síkba rajzolhatónak kell lenni, mert két szoba között csak akkor lehet ajtó, ha a két szobának van közös fala. Ekkor a két szobának megfelelő két csúcs síkban közvetlenül összeköthető egy éllel. Ha két szobának nincs közös fala, akkor a gráfban a két szobának megfelelő csúcsukat összekötő él metszeni fog egy másik élt. Az ábrán látható példán a \(\displaystyle B\) és \(\displaystyle D\) szoba között nem lehet ajtó, vagyis a \(\displaystyle BD\) élt nem tudjuk síkban meghúzni.

Az öt csúcsú teljes gráfban, ha síkbarajzolható lenne, akkor az Euler-formula szerint 7 tartománynak kellene lennie (most a nagy tartományt is beleszámítjuk). Mivel minden tartományhoz legalább 3 él tartozik, és minden él pontosan két tartományhoz tartozik, ezért az élek számára \(\displaystyle \frac{3\cdot7}{2}\) egy alsó becslést ad, ami ellentmondás, hiszen csak 10 él van. Tehát az 5 csúcsú teljes gráfot nem tudjuk síkbarajzolni. Így a gráfnak csak 9 éle lehet, vagyis legfeljebb 9 ajtó tartozhat a lakáshoz. Ez az ábra szerint meg is valósítható.

Statisztika:

125 dolgozat érkezett.
5 pontot kapott:	51 versenyző.
4 pontot kapott:	35 versenyző.
3 pontot kapott:	12 versenyző.
2 pontot kapott:	8 versenyző.
1 pontot kapott:	10 versenyző.
0 pontot kapott:	9 versenyző.

A KöMaL 2017. májusi matematika feladatai