WisFaq!

Twee luchtvaartmaatschappijen

Hallo ik kom niet uit deze vraag:

Tussen zes steden zijn er vliegdiensten, onderhouden door twee luchtvaartmaatschappijen.
Tussen elk tweetal steden vliegt een van de twee maatschappijen (heen en terug). Dat wil men zo doen dat er geen drietal steden is, waartussen alleen door één van de maatschappijen wordt gevlogen.

hoe kan ik nu de vliegverbindingen zo verdelen dat er maar één drietal is waartussen maar door één maatschappij wordt gevlogen?

alvast bedankt

Laura
9-6-2013

Antwoord

Teken zes punten in het vlak (de steden); het gaat het best met een regelmatige zeshoek. Probeer nu de verbindingslijnen te kleuren, elk met rood (maatschappij 1) of blauw (maatschappij 2). Bij elke poging zul je zien dat je altijd een driehoek van één kleur krijgt; je kunt inderdaad bewijzen dat er altijd een rode of blauwe driehoek optreedt. Voor de tweede vraag kun je beginnen met een rode driehoek en proberen de rest zo te kleuren dat er geen rode of blauwe driehoek bij komt.

Zie Stelling van Ramsey [http://dutiaw37.twi.tudelft.nl/~kp/stukjes-pythagoras/jg44/2005-04/]

kphart
12-6-2013