Smurfenspel

Opgave - VWO 2013 dag 1 vraag 2

Aan een grote ronde tafel zitten $2013$ smurfen. Ieder van hen heeft twee kaartjes. Op elk kaartje staat een getal uit $\{1,2,...,2013\}$ zodanig dat elk van de getallen uit deze verzameling precies twee keer voorkomt. Om de minuut neemt iedere smurf het kaartje met het kleinste van de twee getallen, smurft dat door aan zijn linkerbuur en ontvangt een kaartje van zijn rechterbuur. Toon aan dat er een moment komt waarop een smurf twee kaartjes met hetzelfde getal heeft.

Oplossing

Stel dus uit het ongerijmde dat de vraag fout is, nl. dat er nooit een smurf $2$ keer dezelfde kaart krijgt.

Op het begin hebben 2 smurfen elk het getal 2013. Deze zullen dit nooit doorgeven omdat ze nooit een getal $\ge 2013$ zullen krijgen. Na maximaal 2 ronden hierna zullen ook de smurfen die dan het getal $2012$ hebben dit nooit meer doorgeven (hierbij bedoelen we smurfen die niet $2013$ hebben) Deze smurfen zullen namelijk nooit een getal $\ge 2012$ krijgen.
Zo zullen er steeds meer en kleinere getallen zijn die noot meer doorgegeven zullen worden.

Dit kan worden bewezen met inductie waarbij $k$ waarden vastliggen ($2013-k+1$ tot $2013$), dus $2k$ smurfen $1$ waarde blijvend bij zich houden. Er zijn $2013-2k$ smurfen vrij die ooit de grootste kaart krijgen of hebben die niet bij de grootste $k$ waarden zit, zodat zij terug die waarde $2013-k$ zullen blijven behouden.

Dit gaat door totdat alle getallen $\ge 1008$ vast liggen, aangezien dan $k=1006$ en vervolgens maar $1$ smurf vrij is/ Er is dan een smurf die dan nog geen "vast" getal heeft. Als de 1007'en voldoende doorgegeven worden zal deze smurf uiteindelijk een 1007 krijgen. Deze geeft hij nooit meer af. Alle anderen smurfen geven de andere 1007 door totdat... deze bij de smurf met 1007 komt en een dubbel vormt. Contradictie met onze veronderstelling uit het ongerijmde.
De vraag was dus juist en hierbij ook bewezen.