1990 IMO Problems/Problem 5
Problem
Given an initial integer , two players, and , choose integers , . . . alternately according to the following rules: Knowing , chooses any integer such that . Knowing , chooses any integer such that is a prime raised to a positive integer power. Player wins the game by choosing the number 1990; player wins by choosing the number 1. For which does:
(a) have a winning strategy?
(b) have a winning strategy?
(c) Neither player have a winning strategy?
Solution
If it is clear that B wins, because A can only choose numbers with at most 2 prime factors (30 is the smallest with three and ), which B can either make smaller (choose the lesser of the two) or the number contains one prime factor in which case B wins. Once , A can only choose prime powers, so B wins.
If it's a draw, because the only numbers that give A a chance of winning are those with three prime factors (for reasons discussed above). Less than 49, this gives 30 and 42 as the only choices which won't cause A to lose. However, if A chooses 30, B may choose 6, and we have a stalemate. If A chooses 42, B may choose 6, and we still have a stalemate.
If , if is less than 45 by choosing (perhaps starting later) 3*4*5, then 3*5*7, then 2*3*5*7, and then 3*4*5*7 A can force B to make for some k.
If for some k, then A wins (he may pick 1990). If pick the least natural value of m such that . The best B can do is half it, taking it to . However, B cannot make drop below 45 because . Thus we will get a descending sequence of integers until we end up with , at which point A wins.
This solution was posted and copyrighted by Ilthigore. The original thread for this problem can be found here: [1]
See Also
1990 IMO (Problems) • Resources | ||
Preceded by Problem 4 |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 6 |
All IMO Problems and Solutions |