Skip to main content
OlympiadHQ

Browse · MathNet

Print

Argentine National Olympiad 2015

Argentina 2015 counting and probability

Problem

Call a natural number acceptable if it has at most 9 distinct prime divisors. There is given a pile of stones. A legal move is to remove stones from the pile where is an acceptable number. Players and take turns in making legal moves; goes first. The one who removes the last stone wins. Decide which player has a winning strategy.
Solution
Let be the product of the first 10 primes . Observe that is the smallest unacceptable number. Apparently divides , and acceptable numbers are not divisible by . Let remove stones on his first move. Because is divisible by but is not, the number of stones remaining is not divisible by ; in particular . So the remainder of satisfies . It follows that is acceptable as is the least unacceptable number. In addition is nonzero, so can make a legal move by taking stones. There remain stones, a quantity divisible by .

Then, just like above, any move of yields a number of stones that is not divisible by , and nonzero in particular. Its remainder is such that , so is able to remove stones and reach a position again where the number of stones is a multiple of . Clearly can apply such moves at each step.

The number of stones decreases at each move, so the game ends with a win of one of the two players. 's moves always leave a quantity not divisible by , unlike 's moves. Hence cannot take the last stone, meaning that 's strategy guarantees him a win.
Final answer
B

Techniques

Games / greedy algorithmsInvariants / monovariantsPrime numbers