WisFaq!

Pakketjes, huizen en bedrijven

je hebt 3 huisjes en 3 bedrijven. alle 3 de huizen moeten paketjes kijgen van alle 3 de bedrijven maar, de lijnen mogen elkaar niet kruisen en je mag de paketjes niet doorgeven. je moet de puzlle maken in 2D en niet in 3D!

paul rooijmans
22-7-2003

Antwoord

Deze puzzel heeft in twee dimensies geen oplossing. De puzzel staat ondermeer bekend als de water-gas-elektriciteit-puzzel omdat hij dikwijls in die vorm wordt gesteld (3 huizen moeten verbonden worden met W, G en E zonder te snijden).

Grafentheoretisch: de graaf die onstaat als je 2 keer 3 punten hebt (1,2,3,a,b,c) waarbij je elke letter met elk cijfer wil verbinden (een bipartiete graaf), K(3,3) genaamd, is niet planair. Dit wil zeggen dat hij in het vlak niet kan.

Koen Mahieu met dank aan Christoph Smet

km
22-7-2003