De winnaar van de breinbreker van april-mei 2023 is Arne Lameire met een elegante grafentheoretische oplossing. Proficiat! We feliciteren ook Bart Van Gasse, Steven Van Overberghe, Luka Sebbag, Tymen Van Himme en Marieke Louage voor hun correcte inzendingen.
De modeloplossing gaat als volgt:
We bekijken de wiskundigen als een graaf waarbij elke wiskundige een knoop is en
elke vriendschap tussen twee wiskundigen een boog is. Als een wiskundige een ticket
heeft, dan kleuren we de overeenkomstige knoop in.
Telkens als een ongekleurde knoop grenst aan minstens 2 gekleurde knopen, kleuren
we deze in. De bogen die deze knopen dan met elkaar verbinden zullen we ’gebruikte
bogen’ noemen.
Nu bekijken we het minimale aantal gebruikte bogen om de volledige graaf in te
kleuren. Hiervoor kleuren we een voor een de knopen in. In het begin zijn er 75
niet-gekleurde knopen. Als deze worden ingekleurd, moeten er dus minstens 150
gebruikte bogen zijn. Bij de laatste knoop moeten alle andere knopen al ingekleurd
zijn en kan geen enkele van de 3 bogen al gebruikt zijn, anders was deze knoop al
ingekleurd. Dus moet bij de laatste knoop alle 3 de bogen gebruikt worden. Dus
moet elke graaf die uiteindelijk volledig gekleurd wordt, minstens 151 bogen bevat-
ten. Omdat elke graaf die voldoet aan de voorwaarden uit het vraagstuk exact 150
bogen bevat, is dit dus onmogelijk.