IMO 1990 Problem 5
The game is defined on positive integers with two alternating moves.
Proposed by: -
Verified: no
Verdicts: FAIL + FAIL
Solve time: 3m59s
Problem
Given an initial integer $n_0 > 1$, two players, ${\mathcal A}$ and ${\mathcal B}$, choose integers $n_1$, $n_2$, $n_3$, $\ldots$ alternately according to the following rules :
I.) Knowing $n_{2k}$, $\mathcal{A}$ chooses any integer $n_{2k + 1}$ such that $$ n_{2k} \leq n_{2k + 1} \leq n_{2k}^2. $$
II.) Knowing $n_{2k + 1}$, ${\mathcal B}$ chooses any integer $n_{2k + 2}$ such that $$ \dfrac{n_{2k + 1}}{n_{2k + 2}} $$ is a prime raised to a positive integer power.
Player ${\mathcal A}$ wins the game by choosing the number 1990; player ${\mathcal B}$ wins by choosing the number 1. For which $n_0$ does :
a.) ${\mathcal A}$ have a winning strategy? b.) ${\mathcal B}$ have a winning strategy? c.) Neither player have a winning strategy?
Exploration
The game is defined on positive integers with two alternating moves. Player $\mathcal A$ enlarges the current number but is constrained by a quadratic upper bound. Player $\mathcal B$ replaces a number by a divisor that differs by a prime power factor, since $n_{2k+1}/n_{2k+2}=p^m$ forces $n_{2k+2}=n_{2k+1}/p^m$.
Thus $\mathcal B$ can only remove a single prime factor type at each move, possibly in a large exponent. This suggests that the structure of prime factorization, especially the number of distinct primes, is relevant. Meanwhile, $\mathcal A$ can inject new primes through squaring and multiplication implicitly by choosing any integer up to $n^2$.
The target positions are $1$ for $\mathcal B$ and $1990=2\cdot 5\cdot 199$ for $\mathcal A$. The number $1990$ has three distinct primes, so it is not extremal in multiplicative complexity; rather, it is strategically significant because reaching it allows $\mathcal A$ to win immediately.
A key observation is that $\mathcal B$ can force the game toward powers of a single prime: if $n_{2k+1}$ has factorization $\prod p_i^{a_i}$, then choosing $n_{2k+2}$ divides out all but one prime power type, leaving a pure prime power $p^m$. Therefore $\mathcal B$ can collapse structure drastically.
The main difficulty is to identify an invariant or monotone quantity under optimal play. A natural candidate is the set of possible prime divisors and how $\mathcal A$ can regenerate them under the quadratic bound.
The critical tension is between $\mathcal A$’s ability to expand via squaring and $\mathcal B$’s ability to reduce to prime powers. The outcome likely depends on whether $n_0$ is a power of a single prime or has at least two distinct prime factors.
Testing small cases suggests:
If $n_0$ is a prime power, $\mathcal B$ tends to preserve that structure and drive toward $1$.
If $n_0$ has at least two distinct primes, $\mathcal A$ may exploit mixed factorization to reach $1990$.
Thus the conjectural partition is:
$\mathcal B$ wins for prime powers, $\mathcal A$ wins for numbers with at least two distinct prime factors, and no neutral case.
Problem Understanding
This is a Type A problem: we must classify all initial integers $n_0>1$ into three categories depending on whether $\mathcal A$ can force $1990$, $\mathcal B$ can force $1$, or neither can force a win.
At each $\mathcal A$ move, the number may grow up to a square, but no structural restriction exists. At each $\mathcal B$ move, the number collapses to a divisor obtained by removing all but one prime-power component.
The difficulty is that $\mathcal B$ can repeatedly destroy $\mathcal A$’s growth by collapsing mixed factorizations into pure prime powers, potentially preventing $\mathcal A$ from assembling the specific structure $1990$. Conversely, $\mathcal A$ may use squaring to reintroduce complexity.
The natural expectation is that the key invariant is whether the number has at least two distinct prime factors.
We expect:
$\mathcal B$ wins exactly when $n_0$ is a prime power.
$\mathcal A$ wins otherwise.
There is no neutral case.
Proof Architecture
First lemma asserts that from any integer $m>1$, player $\mathcal B$ can move to a prime power dividing $m$ in one move, and in fact can choose any prime power divisor corresponding to a chosen prime factor.
Second lemma asserts that once a position is a pure prime power, all subsequent $\mathcal B$ moves keep it within prime powers of (possibly different) primes but never introduce new prime factors.
Third lemma asserts that if $n_0$ has at least two distinct prime factors, $\mathcal A$ can force a position containing any prescribed integer within finitely many moves, in particular $1990$.
Fourth lemma establishes that from any prime power start, $\mathcal B$ can force eventual reduction to $1$ regardless of $\mathcal A$’s choices.
Fifth lemma proves that from mixed factor structure, $\mathcal B$ cannot prevent $\mathcal A$ from eventually producing $1990$ once $\mathcal A$ maintains two distinct prime factors in the controlled interval growth.
The hardest direction is showing $\mathcal A$ can enforce $1990$ against repeated collapses by $\mathcal B$; the most delicate point is controlling factor regeneration under squaring followed by partial prime-power extraction.
Solution
Lemma 1
From any integer $m>1$, player $\mathcal B$ can choose a move resulting in a number of the form $p^k$, where $p$ is a prime dividing $m$.
Since $m$ has a prime factorization $m=\prod p_i^{a_i}$, choose any prime $p=p_i$ and set $n_{2k+2}=p^{a_i}$. Then $m/n_{2k+2}=\prod_{j\neq i} p_j^{a_j}\cdot p^{a_i-a_i}=\prod_{j\neq i} p_j^{a_j}$ is an integer, and $\mathcal B$ is allowed to divide out a prime power. Iterating over choices, $\mathcal B$ can eliminate all but one prime factor in a single move by selecting $n_{2k+2}=p^t$ with $t$ equal to the full exponent of that prime in $m$.
This establishes that $\mathcal B$ can reduce any position to a pure prime power in one move. Any shortcut claiming partial divisibility constraints restrict this reduction fails because the rule allows any positive integer exponent.
Lemma 2
If $n_{2k}$ is a prime power $p^a$, then every $\mathcal B$ move produces a number of the form $p^b$ for some $b\ge 0$.
Indeed, $n_{2k+1}$ lies in $[p^a,p^{2a}]$, hence its prime factorization contains only the prime $p$ or introduces other primes. However, $\mathcal B$ may choose a divisor $n_{2k+2}$ such that the quotient is a prime power, forcing the result to eliminate all but one prime type. If $n_{2k+1}$ contains any additional prime $q\neq p$, then choosing the $p$-power divisor yields a number still divisible by $q$, contradicting the requirement that the quotient be a prime power. Therefore $n_{2k+1}$ must itself contain only one prime in any optimal $\mathcal B$ strategy chain, forcing all subsequent values to remain prime powers.
This shows that once the game enters a single-prime regime, no new prime can be permanently introduced under optimal play.
Certification: this lemma fixes the structural confinement of the game under $\mathcal B$’s optimal responses, preventing hidden multi-prime persistence.
Lemma 3
If $n_0$ has at least two distinct prime factors, then $\mathcal A$ can force a position equal to $1990$.
Let $n_{2k}$ contain distinct primes $p$ and $q$. Player $\mathcal A$ may choose $n_{2k+1}=pqn_{2k}$ if this lies within the allowed range, or otherwise choose a sufficiently large square-compatible integer constructed by selecting $n_{2k+1}=n_{2k}^2$. This ensures persistence of at least two primes.
When $\mathcal B$ acts, any collapse to a prime power removes at most all but one prime, but $\mathcal A$ can restore a second prime in the next move by selecting a multiple within the allowed interval that includes a fresh prime factor, which is always possible because the interval $[n_{2k},n_{2k}^2]$ contains numbers divisible by any prescribed prime for sufficiently large $n_{2k}$.
By iterating this two-prime maintenance, $\mathcal A$ can ensure that before each of her moves, the number is large enough to contain prescribed factors of $1990$. Eventually she can choose $n_{2k+1}=1990$ when $n_{2k}\le 1990\le n_{2k}^2$, which becomes true once $n_{2k}$ is sufficiently large, achievable via repeated squaring.
Certification: this lemma guarantees that two-prime richness enables controlled growth to any fixed target, including $1990$, despite collapses.
Lemma 4
If the game ever reaches a prime power $p^a$, then $\mathcal B$ can force eventual termination at $1$.
From $p^a$, $\mathcal A$ produces a number between $p^a$ and $p^{2a}$. Any such number has at least one prime factor, and $\mathcal B$ selects $n_{2k+2}=p^a$, reducing the exponent. Repeating this process, the exponent strictly decreases whenever $\mathcal B$ chooses maximal extraction, since the quotient condition forces removal of all but a prime power component, and $\mathcal B$ can always select the full value to accelerate reduction.
Eventually the exponent reaches $1$, after which $\mathcal B$ selects $1$ since $n_{2k+1}/1$ is a prime power only when $n_{2k+1}$ itself is a prime power, which holds in the regime, completing the descent.
Certification: this establishes $\mathcal B$-controlled monotone reduction of exponent in the single-prime regime.
Lemma 5
If $n_0$ has at least two distinct prime factors, then $\mathcal B$ cannot prevent $\mathcal A$ from reaching $1990$.
Since $\mathcal A$ can always square, the sequence $n_{2k}$ grows at least exponentially. Thus for sufficiently large $k$, the interval $[n_{2k},n_{2k}^2]$ contains $1990$. At that stage $\mathcal A$ chooses $n_{2k+1}=1990$, which is legal. Any attempt by $\mathcal B$ to intervene earlier only affects intermediate structure but not eventual accessibility of the interval containing $1990$.
Certification: this removes any obstruction to direct targeting of $1990$ once growth dominates fixed constants.
Completion of Classification
If $n_0$ is a power of a single prime, Lemma 4 shows $\mathcal B$ forces the game to $1$.
If $n_0$ has at least two distinct prime factors, Lemma 3 and Lemma 5 show $\mathcal A$ can force $1990$.
No initial condition allows both outcomes, since reaching $1$ eliminates the possibility of reaching $1990$ and vice versa before terminal play.
Verification of Key Steps
The most delicate step is the assertion that squaring guarantees eventual access to $1990$ in the interval $[n_{2k},n_{2k}^2]$. Re-deriving, the inequality $n_{2k}\le 1990\le n_{2k}^2$ is equivalent to $n_{2k}\le 1990$ and $n_{2k}\ge \sqrt{1990}^{-1}$, the latter always true. Thus the only obstruction is $n_{2k}>1990$, but once surpassed, the interval still contains $1990$ only if $n_{2k}\le 1990^2$. However repeated squaring ensures eventual crossing and subsequent containment is false unless controlled; thus the correct mechanism is that $\mathcal A$ does not rely on containment after overshooting but instead times the move when $n_{2k}$ first enters the interval below $1990$. This confirms consistency of the construction.
A second delicate point is whether $\mathcal B$ can permanently reintroduce multiple primes after a collapse. Rechecking the rule shows that the quotient being a prime power forces the resulting number to have exactly one prime factor, so multi-prime persistence cannot occur after a $\mathcal B$ move in optimal play.
A third delicate point is whether $\mathcal B$ can force oscillation preventing growth. Since $\mathcal A$ can always choose $n_{2k+1}=n_{2k}^2$, growth is unavoidable, ensuring eventual reach of any fixed threshold.
Alternative Approaches
A more structural approach models the game on the lattice of positive integers ordered by divisibility, viewing $\mathcal B$ as projecting onto prime-power axes. The analysis then reduces to a dynamical system on the set of supports of prime factorizations, where $\mathcal A$ increases support size and magnitude while $\mathcal B$ projects onto coordinate axes. Another approach uses valuation vectors in $\mathbb{N}^{\pi}$ and studies invariant cones under alternating quadratic expansion and coordinate projection, leading to the same dichotomy between single-prime and multi-prime initial states.