frieten van 2005 uit de QED competitie

Opgave - JWO 2018 dag 1 vraag 2

Filip en Laurent gaan beide frietjes eten.
Ze delen een zak met $2018$ frieten, waarbij ze elk om beurt $1,2$ of $5$ frieten mogen verorberen.
Degene die het laatste frietje neemt, die betaalt de rekening.
Wie zal de kosten moeten betalen, als je weet dat Filip als eerste mocht beginnen eten en beide slim zijn en niet willen betalen.

Oplossing

Bij perfect spel zal Laurent de rekening moeten betalen:

In zijn eerste zet neemt Filip 1 frietje. Dan blijven er aan het begin van Laurent zijn beurt 2017 frieten over. Dit is een drievoud plus 1.

Filip kan nu zorgen dat het aantal frieten na zijn beurt steeds gelijk is aan een drievoud plus 1 , dat strikt positief is wanneer Laurent een strikt positief aantal frieten overliet.
Dit door volgende strategie toe te passen;

Telkens nadat Laurent 1 frietje heeft genomen, neemt Filip er 2.
Wanneer Laurent er 2 of 5 heeft genomen, neemt Filip er 1.
(het aantal frieten gaat dus van $3k+3$ of $3k+2$ met $k\ge 0$ naar $3k+1$ in zo'n beurt)

Zo zijn er aan het begin van Laurents beurt respectievelijk 3, 3 of 6 frieten minder dan aan het begin van zijn vorige beurt. Zo zal, aangezien a - 3 ≡ a (mod 3) en a - 6 ≡ a (mod 3), het aantal frieten aan het begin van Laurent zijn beurt steeds een drievoud plus 1 blijven.

Zo zal het uiteindelijk voorkomen dat Laurent aan het begin van zijn beurt nog exact 1 friet heeft (want het aantal frieten is strikt dalend), en hij niet anders kan dan die laatste friet op te eten en dus de rekening te betalen.