PHP

Opgave - VWO 1989 dag 1 vraag 1

Bewijs dat iedere deelverzameling met $55$ elementen uit $\{1,2,\cdots,100\}$ minimum $2$ elementen heeft met verschil $9.$

Oplossing

Schrijf de getallen 1-99 in volgorde in een rooster van 9 rijen bij 11 kolommen, beginnend linksboven, dan telkens eerst naar beneden de kolom opvullend, vooraleer in de volgende kolom bovenaan verder te gaan. Het getal 100 blijft over en schrijven we rechtsboven op rij 1 in een 12de kolom.
Merk op: tussen elementen van verschillende rijen is nu geen verschil 9 mogelijk.
Voor elke rij >=2 geldt nu dat de enige manier om er 6 getallen uit te kiezen zonder één 9-verschil, erin bestaat om de getallen uit kolom 1,3,5,7,9 en 11 te nemen. Meer dan zes kan niet. Alle verschillen in de vijf gaten per rij tussen de opeenvolgende getallen zijn dan 18 (gat type A).
In rij 1 zijn er 12 getallen en daar kan de keuzen op meerder manieren, maar in elk geval ook maximaal 6 getallen. Ofwel zijn er dan 4 gaten met lengte 18 (gat type A) en 1 met lengte 27 (gat type B), ofwel zijn er 5 gaten met lengte 18 (gat type A) en één gat aan het begin of op het einde (type C).

A = (x, x+9, x+18) met x+9 nog ongebruikt
B = (x, x+9, x+18, x+27) met x+9 en x+18 nog ongebruikt
C = (91, 100, niks) met 100 nog ongebruikt
ofwel (niks, 1, 10) met 1 nog ongebruikt

In elk geval zijn alle nog niet gebruikte getallen gelegen in gaten van één van deze drie soorten, en deze gaten hebben allemaal dezelfde eigenschap: 1 tussenliggend getal toevoegen in dat gat zorgt voor tenminste één eerste 9-verschil.

We hadden nu dus al 54 getallen kunnen kiezen zonder één 9-verschil te veroorzaken.
We hebben ook alle dergelijke gevallen met 54 gecovered. Voor allemaal geldt nu hetzelfde.
Wegens het duivenhokprincipe (in zijn meest belachelijke vorm: 1 duif verdelen over n hokjes geeft minstens één hokje met een duif) geldt dat het kiezen van een 55ste getal onvermijdelijk leidt tot het opvullen van één van deze A-, B- of C-posities, en het daar dus onvermijdelijk veroorzaken van minstens een 9-verschil.

We willen zoveel mogelijk getallen kiezen die geen verschil van negen hebben met een ander element. Van ieder gebruikt element $x$ moet element $x+9$ dus ongebruikt zijn. Om te zorgen dat $x-9$ ook ongebruikt is, werken we best in patronen waarbij de ruimte tussen gebruikte en ongebruikte reeksen elementen voldoende groot is om ze van mekaar te 'isoleren' (om een verschil van $9$ te vermijden).

Dat patroon bestaat om zoveel mogelijk elementen te kunnen gebruiken uit $9$ opeenvolgende gebruikte getallen, met daarna $9$ niet gebruikte elementen.

Zo krijgen we dus in een poging tot een maximaal aantal elementen die geen verschil hebben van 9 5 keer een herhaling van het patroon '$9$ keer gebruikt, $9$ keer niet gebruikt' (want $100/18=5,...$). Hierna hebben we nog $10$ elementen over, waarvan we zonder de voorwaarden te schenden er weer $9$ kunnen gebruiken. Zo verkrijgen we dus $54$ elementen gebruikt zonder ergens een verschil van $9$ te verkrijgen.

We bewijzen nu dat het niet met $55$ kan met het duivenhokprincipe:

We verdelen de getallen in de verzameling:
$\{1,10),(11,2) \cdots,(18,9)$,$(28,19)\cdots(36,27)$,$(46,37)\cdots(54,45)$,$(64,55)\cdots(72,63)$,$(82,73)\cdots (81,90)$,$(91,100),\cdots(99,108).$

Dit zijn $6*9=54$ verzamelingen die samen alle getallen uit $\{1,2\cdots 100 \}$ bevatten. Dit betekent dat met het duivenhokprincipe er minstens $1$ koppel is waarvan beide getallen genomen werden bij de $55$ elementen.
Dat koppel heeft een verschil van $9$ waarmee de vraag bewezen is.

Misschien eens een kortere oplossing ter illustratie:
Stel de getallen $a_1,\cdots,a_{55}$.
Beschouw alle getallen $a_i-4$ en $a_i+5$, dat zijn er $2*105=110$.. Ze kunnen gaan van $-3$ tot $105$, dat zijn $109$ mogelijke waarden.
Er zijn er dus zeker twee gelijk wegens het duivenhokprincipe.
$a_i-4=a_j-4$ is onmogelijk want alle getallen zijn verschillend.
Om dezelfde reden is $a_i+5=a_j+5$ onmogelijk.
$a_i-4=a_i+5$ is ook onmogelijk.
Dus moet $a_i-4=a_j+5$, zodat $a_i-a_j=9$.