Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "1990 IMO Problems/Problem 5"
 
Line 1: Line 1:
−
5. 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:
+
==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
−
<math>n_{2k}\leq n_{2k+1}\leq n_{2k}^2</math>.
+
<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
−
<math>\frac{n_{2k+1}}{n_{2k+2}}</math>
+
<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 12:50, 30 January 2021

Problem

Given an initial integer $n_{0}\textgreater1$, two players, $\mathbb{A}$ and $\mathbb{B}$, choose integers $n_{1}, n_{2},n_{3}$, . . . alternately according to the following rules: Knowing $n_{2k}$, $\mathbb{A}$ chooses any integer $n_{2k+1}$ such that \[n_{2k}\leq n_{2k+1}\leq n_{2k}^2\]. Knowing $n_{2k+1}$, $\mathbb{B}$ chooses any integer $n_{2k+2}$ such that \[\frac{n_{2k+1}}{n_{2k+2}}\] is a prime raised to a positive integer power. Player $\mathbb{A}$ wins the game by choosing the number 1990; player $\mathbb{B}$ wins by choosing the number 1. For which $n_{0}$ does:

(a) $\mathbb{A}$ have a winning strategy?

(b) $\mathbb{B}$ have a winning strategy?

(c) Neither player have a winning strategy?

Solution

If $n_0<6$ 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 $30>5^2$), 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 $n_{2k}=2$, A can only choose prime powers, so B wins.

If $n_0=6,7$ 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 $n_0 \geq 8$, if $n_0$ 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 $n_{2k} \geq 60$ for some k.

If $45 \leq n_{2k} \leq 1990$ for some k, then A wins (he may pick 1990). If $n_{2k}>1990$ pick the least natural value of m such that $2^m 47\geq n_{2k}$. The best B can do is half it, taking it to $n_{2k+2} = 2^{m-1} 47 < n_{2k}$. However, B cannot make $n_{2k+2}$ drop below 45 because $47*32<1990 \Rightarrow 2^m \geq 64$. Thus we will get a descending sequence of integers until we end up with $45 \leq n_{2k} \leq 1990$, 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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1990_IMO_Problems/Problem_5&oldid=144076"