para's
Opgave - BrMO 2 2011 dag 1 vraag 4
Zij $G$ de verzameling van roosterpunten $(x,y)$ waarvoor $1 \le x,y \le 2011$.
Bepaal het grootst mogelijke aantal roosterpunten uit $G$ die je in een verzameling $S$ kan steken zodat er geen echt parallellogram ( $4$ collineaire punten vormen geen echt parallellogram) kan worden gevormd met punten uit $S$.
- login om te reageren
Oplossing
Neem een $2011$ X $2011$ matrix.
Nu kunnen $2$ punten in één kolom slechts op $2010$ afstanden van elkaar liggen ($1 \rightarrow 2010$).
Nu mag een bepaalde afstand slecht in één kolom voorkomen, omdat we anders een parallellogram kunnen vormen tussen die vier punten.
Dus er mogen niet meer dan $2010$ verschillende afstanden zijn. (A)
Noem $x_i$ het aantal punten in kolom $i$.
Er zijn dan minstens $x_i-1$ afstanden te vormen met punten uit kolom $i$.
Er moet dus gelden dan $\sum_{i=1}^{i=2011} x_i-1 \le 2010$ wegens (A),
wat overeenkomt met $\sum_{i=1}^{i=2011} x_i \le 4021$ .
Een voorbeeld van die maximale bezetting is een matrix waarbij de 1ste kolom en 1ste rij volledig met punten bezet zijn.
Neem een $2011$ X $2011$ matrix. Nu kunnen de punten in één kolom slechts op $n-1$ afstanden van elkaar liggen ($0\rightarrow 2010$). Nu mag een bepaalde afstand slecht in één kolom voorkomen, omdat we anders een parallellogram kunnen vormen tussen die vier punten.
Door de punten in $1$ kolom allen te verschuiven over dezelfde afstand, verandert er niks aan de onderlinge afstanden en dus ook niet aan het feit of er een parallellogram te vormen is.
We mogen dus veronderstellen dat het meest linkse punt van iedere kolom in de eerste rij zit.
Merk op dat er $2011$ kolommen zijn, zodat er zeker één kolom is waar maximaal 1 punt in zit, opdat er anders minstens $2010$ afstanden zijn. (B) Als er in elke kolom (behalve die ene waar slechts $1$ punt in zit) nu twee punten zitten, zijn er in het totaal $4021$ punten. Dit is het maximum, wat we bewijzen:
Want stel dat men een werkende configuratie $C$ heeft met minstens $4022$ punten, neem een eventuele deelverzameling $D$ van exact $4022$ punten.
Door het onderste punt van $D$ te verplaatsen uit een kolom $c_i$ met meer dan $2$ punten naar een kolom $c_j$ met maximaal $1$ punt, is er minstens $1$ afstand minder in kolom $c_i$.
Bevat $c_j$ geen punten, komt er geen afstand bij in die kolom.
Bevat $c_j$ $1$ punt: Wanneer we dat punt in kolom $c_j$ in dezelfde rij laten zitten als toen het in $c_i$ zat, komt in die rij de oorspronkelijk langste afstand bij.
In beide gevallen zal de verzameling van afstanden die gevormd zijn, geen nieuw element verkrijgen (enkel verdwijnen)
Met deze operatie kunnen we nu configuratie $D$ omvormen tot een configuratie met $2011$ kolommen met elk $2$ punten met hoogstens dezelfde afstanden, maar wegens (B) is niet mogelijk, contradictie.
Dit bewijst dat er maximaal $4021$ punten in $S$ zitten.
Een voorbeeld van die maximale bezetting is een matrix waarbij de 1ste kolom en 1ste rij volledig met punten bezet zijn.