Winnaar Breinbreker nov-dec

Breinbreker

De winnaar van de breinbreker van november-december is Yannick Neyt. Als prijs ontvangt Yannick een jaarabonnement op het tijdschrift Pythagoras en op het tijdschrijft Wiskunde & Onderwijs. Proficiat en veel leesplezier!

We kregen ook nog juiste inzendingen van Mathias Jolie en Thomas Present. Bedankt voor jullie inzending!

Oplossing van Yannick

a) Stel je hebt 1 Xzorgsiaan met het maximale aantal partners: 3. Elk van deze partners kan dus nog hoogstens twee andere partners hebben: 3*2. Dus nu kunnen er geen andere wezentjes meer zijn dan deze tien (1+3+6=10), want die zouden geen partner
zijn van het eerste wezentje en zouden er ook geen partner mee gemeen hebben. Er leven dus maximaal tien wezentjes op de planeet Xzorg.

Is tien wezentjes ook echt mogelijk? Ja, de Petersen-graaf voldoet.

Oplossing vraag a

Deze graaf is namelijk (3,0,1) compleet, wat wil zeggen dat elke top graad 3 heeft en dat elke twee niet-verbonden toppen juist 1 partner gemeen hebben. Dus 10 is echt het maximum aantal Xzorgsianen.

b) Stel we nemen 1 van de Xzorgsianen uit het triootje (A in figuur). Deze is verbonden met de 2 uit het triootje en mogelijks nog een andere partner B. Nu kunnen de twee uit het triootje nog elk maximum een partner hebben en kan B nog twee partners hebben. We hebben nu 8 Xorgsianen, meer kunnen het er niet zijn, want dan zou die geen partner zijn van de eerste Xzorgsiaan noch een partner gemeen hebben met hem. Dat 8 echt mogelijk is maakt de figuur hieronder duidelijk. Dus 8 Xzorgsianen is het maximum als er een triootje is gebeurd.

Oplossing vraag b