KöMaL - Középiskolai Matematikai és Fizikai Lapok
Sign In
Sign Up
 Magyar
Information
Contest
Journal
Articles

 

Problem C. 1422. (May 2017)

C. 1422. In a single-storey rectangular apartment, there is at most one door connecting any pair of rooms. In addition, in each room there is at most one exit from the apartment. If the apartment consists of four rooms, what is the maximum possible number of doors altogether?

(5 pont)

Deadline expired on 12 June 2017.


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

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ó.


Statistics:

126 students sent a solution.
5 points:51 students.
4 points:35 students.
3 points:12 students.
2 points:8 students.
1 point:10 students.
0 point:9 students.
Unfair, not evaluated:1 solution.

Our web pages are supported by:   Ericsson   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma   Nemzeti Tehetség Program    
MTA Energiatudományi Kutatóközpont   MTA Wigner Fizikai Kutatóközpont     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley