Solució al tercer repte

És impossible passar per totes les portes. És una qüestió de parells i senars (imparells).

Si comencem des d’una habitació amb un nombre de portes parell, haurem d’entrar en ella al creuar l’última porta, és a dir, si comencem per una habitació amb un nombre de portes senar, començarem i acabarem en ella. Ara bé, com també hi ha habitacions amb nombre de portes senar, entrarem des de fora i arribarà un moment que quan tornem a entrar ja no podrem eixir, cosa que entra en contradicció amb el fet que hem d’acabar en l’habitació de sortida.

Si pel contrari eixim des d’una habitació amb un nombre senar de portes, no acabarem en ella, de fet acabarem en una altra habitació. Ara bé, com tenim més de dos habitacions amb nombre senar de portes (la 2, la 4, la 5 i el pati que també és una habitació amb 9 portes) resulta que al entrar des de fora en una d’elles, arribarà un moment que quan tornem a entrar ja no podrem eixir, i de nou tenim una contradicció.

En conseqüència, no podem passar per totes les portes amb les condicions que ens imposen.

És recomanable mirar els conceptes bàsics de la teoria de grafs (en particular els grafs eulerians i hamiltonians) per entendre bé aquest problema. De fet el graf equivalent a la imatge de les portes és el següent:

Graf de les habitacions

Graf de les habitacions

Com es pot observar, l’habitació 1 i l’habitació 3 tenen un nombre parell de portes (camins) i les habitacions 2, 4, 5 i el pati tenen un nombre senar de portes. En conseqüència no podem passar per totes les portes amb les condicions indicades, ja que només es podria si tinguérem un parell d’habitacions amb un nombre senar de portes o si totes les habitacions tingueren un nombre parell de portes.

Deixa un comentari

Fill in your details below or click an icon to log in:

WordPress.com Logo

Esteu comentant fent servir el compte WordPress.com. Log Out / Canvia )

Twitter picture

Esteu comentant fent servir el compte Twitter. Log Out / Canvia )

Facebook photo

Esteu comentant fent servir el compte Facebook. Log Out / Canvia )

Google+ photo

Esteu comentant fent servir el compte Google+. Log Out / Canvia )

Connecting to %s