ronde tafel
Opgave - CanMO 1994 vraag 3
25 personen zitten aan een ronde tafel. Ieder uur is er een stemming, en ieder persoon moet ja of nee antwoorden. Iedereen gedraagt zich als volgt: op de $n^e$ stemming, als zijn antwoord hetzelfde is het antwoord van op zijn minst één van de twee personen waar hij tussen zit, dan zal hij hetzelfde antwoorden op de $n+1^e$ stemming als op de $n^e$ stemming. Maar als zijn antwoord verschillend is van dat van zijn beide buren, dan verandert hij van antwoord bij de volgende beurt. Bewijs dat, ongeacht de antwoorden van de eerste stemming, vanaf een bepaald ogenblik niemand zijn stem meer zal veranderen.
- login om te reageren
Oplossing
Aangezien $25$ een oneven getal is, is het onmogelijk dat bij de eerste stemming iedere "ja" tussen twee "nee's" zit of omgekeerd. Bijgevolg zitten er twee personen met hetzelfde antwoord naast elkaar. Deze personen zullen hun antwoorden niet meer veranderen. Schuif nu telkens een persoon naar rechts op. Zit hij tussen twee meningen die anders zijn dan die van hem, verandert hij, maar de volgende stemmingen verandert hij niet meer van mening. Zit hij naast minstens één persoon die dezelfde mening heeft, dan veranderen die twee personen nooit. Zo kan je door telkens een persoon naar rechts op te schuiven en deze stappen te herhalen het blok van personen die niet veranderen steeds met een persoon uitbreiden totdat je terug bij de eerste persoon uitkomt zodat niemand meer verandert.