kleuring

Deze driehoek kan gevormd worden als een vakje in zowel dezelfde rij als kolom een ander vakje heeft.

We zoeken dus voor de kleinste $n$ waarvoor dit het geval is.

Als $n=1998$ dan kan je de eerste rij en kolom helemaal vullen. Als je nu het vakje helemaal linksboven blank laat heb je 1998 vakjes gekleurd die geen dergelijke driehoek vormen.

Als $n=1999$ wordt het moeilijker.
Kleur de vakjes in en tel nu per kolom alle gekleurde vakjes behalve het eerste, we noemen dit aantal $b$. Dit zijn er minstens 999. Er zijn namelijk 1999 vakjes gekleurd, en er kunnen er maximaal 1000 de eerste zijn in een kolom aangezien er maar 1000 kolommen zijn.

Aangezien er dus 999 vakjes zijn die met minsten 1 ander vakje in dezelfde kolom staan, zijn er ook 999 rijen waar gaan 2e vakje gekleurd mag zijn. Het probleem is dat we die vakjes die eerst staan in elke kolom nog kwijt moeten.
=>Als $b=999$ dan zijn dit er 1000. Dit zou willen zeggen dat we 1000 vakjes in een enkele rij moeten plaatsen. Dan staat er in die rij in elke kolom een gekleurd vakje. En dan zal dat met die 999 vakjes die niet in de rij staan zo'n driehoek vormen.

=> Als $b\ge1000$ dan zijn er 1000 rijen waar geen 2e vakje gekleurd mag worden. Er is dan geen plaats voor de vakjes die eerst in de kolommen zouden zijn.

Kortom de kleinste $n$ waarvoor dit geldt is $n=1999$.