Difference between revisions of "1990 IMO Problems/Problem 5"
Line 1: | Line 1: | ||
− | + | ==Problem== | |
+ | Given an initial integer <math>n_{0}\textgreater1</math>, two players, <math>\mathbb{A}</math> and <math>\mathbb{B}</math>, choose integers <math>n_{1}, n_{2},n_{3}</math>, . . . alternately according to the following rules: | ||
Knowing <math>n_{2k}</math>, <math>\mathbb{A}</math> chooses any integer <math>n_{2k+1}</math> such that | Knowing <math>n_{2k}</math>, <math>\mathbb{A}</math> chooses any integer <math>n_{2k+1}</math> such that | ||
− | < | + | <cmath>n_{2k}\leq n_{2k+1}\leq n_{2k}^2</cmath>. |
Knowing <math>n_{2k+1}</math>, <math>\mathbb{B}</math> chooses any integer <math>n_{2k+2}</math> such that | Knowing <math>n_{2k+1}</math>, <math>\mathbb{B}</math> chooses any integer <math>n_{2k+2}</math> such that | ||
− | < | + | <cmath>\frac{n_{2k+1}}{n_{2k+2}}</cmath> |
is a prime raised to a positive integer power. | is a prime raised to a positive integer power. | ||
Player <math>\mathbb{A}</math> wins the game by choosing the number 1990; player <math>\mathbb{B}</math> wins by choosing | Player <math>\mathbb{A}</math> wins the game by choosing the number 1990; player <math>\mathbb{B}</math> wins by choosing | ||
the number 1. For which <math>n_{0}</math> does: | the number 1. For which <math>n_{0}</math> does: | ||
+ | |||
(a) <math>\mathbb{A}</math> have a winning strategy? | (a) <math>\mathbb{A}</math> have a winning strategy? | ||
+ | |||
(b) <math>\mathbb{B}</math> have a winning strategy? | (b) <math>\mathbb{B}</math> have a winning strategy? | ||
+ | |||
(c) Neither player have a winning strategy? | (c) Neither player have a winning strategy? | ||
+ | |||
+ | ==Solution== | ||
+ | If <math> n_0<6</math> 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 <math> 30>5^2</math>), 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 <math> n_{2k}=2</math>, A can only choose prime powers, so B wins. | ||
+ | |||
+ | If <math> n_0=6,7</math> 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 <math> n_0 \geq 8</math>, if <math> n_0</math> 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 <math> n_{2k} \geq 60</math> for some k. | ||
+ | |||
+ | If <math> 45 \leq n_{2k} \leq 1990</math> for some k, then A wins (he may pick 1990). If <math> n_{2k}>1990</math> pick the least natural value of m such that <math> 2^m 47\geq n_{2k}</math>. The best B can do is half it, taking it to <math> n_{2k+2} = 2^{m-1} 47 < n_{2k}</math>. However, B cannot make <math> n_{2k+2}</math> drop below 45 because <math> 47*32<1990 \Rightarrow 2^m \geq 64</math>. Thus we will get a descending sequence of integers until we end up with <math> 45 \leq n_{2k} \leq 1990</math>, at which point A wins. | ||
+ | |||
+ | This solution was posted and copyrighted by Ilthigore. The original thread for this problem can be found here: [https://aops.com/community/p1106506] | ||
+ | |||
+ | == See Also == {{IMO box|year=1990|num-b=4|num-a=6}} |
Latest revision as of 13:50, 30 January 2021
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 |