Trek een lijn

Beste mede-beantwoorders,
Vandaag kreeg ik een vraag in de kroeg :D waarop ik geen 'snel' antwoord kon geven. Heb thuis ook nog even gepuzzeld, maar kwam er toch niet uit. Het moet volgens mij via grafen theorie wel te beantwoorden zijn,maar ja das weer jaren geleden voor mij.
De vraag ging over een tekening die er ongeveer als volgt uitzag:

______ 
|  |  | 
------- 
|_|_|_|

Het is lastig tekenen, maar ga ervan uit dat het dus allemaal doorgetrokken lijnen zijn, twee rechthoeken boven, drie rechthoeken onder.

De vraag is nu, om een lijn te tekenen die door alle zijden van dit figuur gaat, maar overal slechts 1x doorheen gaat.
De lijn zelf mag zo lang zijn als men maar wilt, en zichzelf ook kruisen.

Weet iemand of dit uberhaupt kan, zo ja hoe, zo nee graag waarom niet.

Alvast heeeel erg bedankt.

M.v.g.
PHS

Peter
Docent - maandag 1 september 2003

Antwoord

Beschouw het geheel als 6 kamers: 5 "inwendige" en de omgeving. Bekijk de zijden als deuren. De lijn, te visualiseren als een draad, komt dan een kamer binnen langs een deur en gaat weer buiten langs een andere deur en elke deur mag slechts een keer worden gebruikt.

De buitenste vierkante kamers hebben elk 4 deuren. De andere inwendige kamers hebben 5 deuren en de omgeving heeft 9 deuren.

Bedenk nu dat in een kamer met een oneven aantal gebruikte deuren (dus met een oneven aantal deuren) de draad moet beginnen of eindigen. Aangezien er zo meer dan 2 kamers zijn, is het probleem onoplosbaar.

Zie De juiste grafentheoretische term

maandag 1 september 2003

©2001-2024 WisFaq