vijftien stoelen
Opgave - CanMO 1975 vraag 6
(i) 15 stoelen worden geplaatst rond een cirkelvormige tafel met bijhorende naamkaartjes voor de 15 gasten. De gasten merken deze kaartjes echter niet op, en het blijkt dat niemand op de juiste plaats zit. Toon aan dat de tafel zodanig gedraaid kan worden dat er tegelijkertijd twee mensen wel op de juiste plaats zitten.
(ii) Geef een voorbeeld van een schikking waarbij 1 iemand op de juiste plaats zit en elke rotatie van de tafel ervoor zorgt dat er maximum 1 op de juiste plaats zit.
- login om te reageren
Oplossing
$(i)$ $g_0,...,g_{14}$ stellen de nummers voor waar de gasten op zitten. (als iedereen juist zit hebben we dus $g_i=i$)
Beschouw alle getallen $v_i=g_i-i\mod15$, zodat $0< v_i<15$.
Er zijn 15 zo'n getallen die 14 waarden kunnen aannemen, van 1 tot 14.
Dus zijn er zeker 2 gelijk wegens het Duivenhokprincipe: $g_i-i=g_j-j$, dus $g_i-g_j=i-j$. Dat betekent dat de personen i en j op de correcte afstand van elkaar zitten, en als we de tafel draaien zitten ze op de juiste plaats.
$(ii)$ uit (i) weten we dat als door een bepaalde rotatie niemand op de juiste plaats zit, er dan een rotatie is die ervoor zorgt dat er zeker 2 op de juiste plaats zitten.
In dit geval mag dat niet, dus moet door te roteren steeds precies 1 persoon juist zitten.
Dat kun je bv. doen door $g_i=(2i+k)\mod15$. die getallen zijn verschillend want $g_i=g_j$ zou betekenen dat $2(i-j)\equiv0\pmod{15}$ wat onmogelijk is want $i\equiv j$ kan niet.
Het is ook onmogelijk dat $g_i-g_j\equiv i-j\pmod{15}$, want anders zou $i-j\equiv0$ wat niet kan.
(i)
Als iedereen op de verkeerde plaats zit, kunnen we met x als juiste plaats ($x \in [1,15]$ waarmee we iedere stoel vast nummeren) iedereen zijn huidige plaats schrijven als $x-a$ (waarbij $a \in [1,14]$ en een natuurlijk getal is ($15$ zou de juiste plaats weergeven en vanaf $16,17,18...$ krijgen we het zelfde resultat als bij $1,2,3...$) - gezien het een cirkel is, komt voor $1$ weer $15$).
Er zijn dus $14$ mogelijke verschuivingen voor alle genodigden, waardoor we $14$ gasten een verschillende verschuiving kunnen geven, maar de vijftiende gast zeker moeten indelen bij iemand anders wat betreft het aantal plaatsen hij verschoven is (allemaal in dezelfde richting natuurlijk).
Dit is het duivenhokprincipe dat zegt dat $15$ personen verdelen over $14$ draaiingen, we kunnen zeggen dat er min. $2$ mensen bij een draaiiing beide juist zullen zitten.
Als we de tafel volgens deze dubbele verschuiving draaien, komen er dus twee mensen op de juiste plaats te zitten, wat met iedere aan de voorwaarde voldoende tafelschikking het geval is.
(ii)
$$\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline x&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15\\
\hline x-a&1&15&14&13&12&11&10&9&8&7&6&5&4&3&2\\
\hline a &0&2&4&6&8&10&12&14&1&3&5&7&9&11&13\\
\hline\end{array}$$
Op deze manier komt iedere mogelijke verschuiving (inclusief $0$, wat dus iemand op de juiste plaats is) 1x voor, wat voor iedere rotatie 1 iemand op de juiste plaats geeft.