Skip to main content
OlympiadHQ

Browse · MathNet

Print

Ukrainian Mathematical Olympiad

Ukraine counting and probability

Problem

Two players play the following game. They start with a pile of pebbles and take some amounts of pebbles by turns. The player starts can take or pebbles each turn at his discretion, another player can take or each turn. The player unable to make his turn loses. Which player has a winning strategy?
Solution
Перший гравець може забезпечити собі перемогу, узявши першим ходом чотири камінці, а всіма наступними — по одному камінцю. Тоді кількість узятих загалом камінців буде парною лише після ходів першого гравця, а перемагає той гравець, після ходу якого ця величина стане рівною .

Відповідь: Перший гравець.
Final answer
First player

Techniques

Games / greedy algorithmsInvariants / monovariants