Bewijs R_3,3=6

Opgave - reeks 1 2012 dag 1 vraag 3

Bewijs dat in een groep van $6$ personen er $3$ personen te vinden zijn die elkaar niet kennen of elkaar wel kennen.

Oplossing

De party-theorem :)

Stel de personen voor als punten in het vlak en verbindt ze met een rode lijn als ze elkaar kennen en met een blauwe lijn als ze elkaar niet kennen. We moeten nu bewijzen dat we altijd een rode of blauwe driehoek kunnen vinden.

Neem nu persoon A. Deze persoon zal zeker met dezelfde kleur, stel WLOG rood, verbonden zijn met drie andere personen, zeg B, C en D, wegens het duivenhokprincipe. Stel nu WLOG dat B en C rood verbonden zijn. Dan kunnen we een rode driehoek ABC vinden en is het gevraagde bewezen. Doe dit analoog voor BD en CD. De enige mogelijkheid die overblijft is dat B, C en D onderling blauw verbonden zijn, maar nu kunnen we een blauwe driehoek vinden zodat het gevraagde bewezen is.
Uiteraard gaat het geval waarbij rood en blauw omgewisseld worden analoog.

$QED$