Roosterpunten Kleuren.
Het is zelfs binnen een deel  van 8 bij 2 al zo!
Teken 9 verticale lijnen en drie horizontale.

Dat geeft verticaal 9 setjes van drie punten.
Een setje van drie punten kan op 23 = 8 verschillende manieren gekleurd worden.
Dus er moet een dubbel setje tussenzitten (pigeon hole)


In dat dubbele setje komt één kleur minstens twee keer voor (pigeon hole)
Neem die kleur en je hebt een rechthoek met vier dezelfde hoekpunten.

Het Vervolg.

Leg 17 munten op een vierkant bord van 6 bij 6.
Dan bestaat er een rechthoek (met zijden evenwijdig aan de rand van het bord)
met op alle hoekpunten een munt.

Het lijkt bijna het zelfde probleem als hiervoor, maar deze is een stuk moeilijker. Dat komt omdat we nu erbij zeggen welk van de twee kleuren de rechthoek moet hebben.
Schrijf onder elke kolom welke koppels rijen allebei een munt hebben. Dat geeft de 16 getallen onder het eerste bord. Zodra er een getal dubbel in staat, betekent dat, dat die twee kolommen in dezelfde twee rijen munten hebben liggen, en is er dus een rechthoek te maken. Dat is rechts gebeurd.

In totaal zijn er met 6 rijen  1/2 • 6 • 5 = 15 koppels te maken.
Het gaat er dus om of er meer dan 15 koppels in totaal te maken zijn met de munten.
Nou is het aantal koppels zo klein mogelijk als de munten qua aantal zo gelijkmatig mogelijk over de kolommen zijn verdeeld.

(Stel dat een kolom m munten heeft en een andere n < m munten. Verplaats dan een munt van de eerste naar de tweede. Dat geeft m - 1 koppels minder en n koppels extra, netto een verlies van m - n - 1 koppels en dat is groter of gelijk aan nul)

In dit geval  2-3-3-3-3-3 verdeling en dat gaf  1 + 3 + 3 + 3 + 3 + 3 = 16 koppels.

Omdat er maar 15 verschillende koppels zijn te maken is er altijd minstens één dubbele, dus altijd een rechthoek.

Variant 3

Kies uit een verzameling met 11 elementen 10 deelverzamelingen met elk 4 elementen
Dan zijn er zeker twee van die deelverzamelingen die 2 elementen gelijk hebben.

Vertaal de vraag gewoon naar:
Op een bord van 10 kolommen en 11 rijen liggen 40 munten, in elke kolom precies 4 (dat is zo gelijkmatig mogelijk).
Totaal aantal koppels rijen is  1/2 • 11 • 10 = 55 
Koppels met munten zijn er  6 • 10 = 60