IMO 1970 Problem 2
Let the common digit string be interpreted in two positional systems with bases $a$ and $b$.
Proposed by: -
Verified: yes
Verdicts: PASS + PASS
Solve time: 7m24s
Problem
Let $a, b$, and $n$ be integers greater than 1, and let $a$ and $b$ be the bases of two number systems. $A_{n-1}$ and $A_{n}$ are numbers in the system with base $a$ and $B_{n-1}$ and $B_{n}$ are numbers in the system with base $b$; these are related as follows:
$A_{n} = x_{n}x_{n-1}\cdots x_{0}, A_{n-1} = x_{n-1}x_{n-2}\cdots x_{0}$,
$B_{n} = x_{n}x_{n-1}\cdots x_{0}, B_{n-1} = x_{n-1}x_{n-2}\cdots x_{0}$,
$x_{n} \neq 0, x_{n-1} \neq 0$.
Prove:
$\frac{A_{n-1}}{A_{n}} < \frac{B_{n-1}}{B_{n}}$ if and only if $a > b$.
Exploration
Let the common digit string be interpreted in two positional systems with bases $a$ and $b$. Writing the same digits in different bases produces two polynomials evaluated at different points. The key expressions are
$$A_n = \sum_{k=0}^n x_k a^k,\quad A_{n-1} = \sum_{k=0}^{n-1} x_k a^k,$$
and similarly for $B_n, B_{n-1}$ with base $b$.
The target inequality compares ratios of truncations:
$$\frac{A_{n-1}}{A_n} \quad \text{and} \quad \frac{B_{n-1}}{B_n}.$$
Rewriting each ratio in terms of the leading digit isolates a term of the form $x_n a^n / A_n$, suggesting that the decisive quantity is the relative size of $t^n$ compared with the full polynomial $P(t)=\sum_{k=0}^n x_k t^k$.
A promising reformulation is
$$\frac{A_{n-1}}{A_n} = 1 - \frac{x_n a^n}{A_n},\quad \frac{B_{n-1}}{B_n} = 1 - \frac{x_n b^n}{B_n},$$
so the comparison reduces to a comparison between $\frac{a^n}{P(a)}$ and $\frac{b^n}{P(b)}$. The problem becomes monotonicity of a rational function in the base.
The most fragile step is ensuring that the resulting function is monotone in the correct direction uniformly for all digit choices, especially when lower digits vary.
Problem Understanding
The problem involves a fixed digit sequence $x_n x_{n-1}\dots x_0$ with $x_n\neq 0$ and $x_{n-1}\neq 0$, interpreted simultaneously in two number systems with bases $a$ and $b$. The quantities $A_n, A_{n-1}$ and $B_n, B_{n-1}$ are the corresponding values of the full number and its truncation by one digit.
The goal is to prove that the comparison between the ratios of truncated to full numbers depends only on the ordering of the bases: the ratio is smaller in the larger base.
This is nontrivial because changing the base changes every term of the expansion, so direct termwise comparison fails. The structure must instead be converted into a single polynomial inequality valid for all admissible digit choices.
The statement is of Type B. The claim is that
$$\frac{A_{n-1}}{A_n} < \frac{B_{n-1}}{B_n} \quad \text{if and only if} \quad a>b.$$
The correct conclusion is that the function $t \mapsto \frac{t^n}{\sum_{k=0}^n x_k t^k}$ is increasing for $t>1$, which explains why larger bases produce larger values of this ratio.
Proof Architecture
The proof will proceed by introducing the polynomial
$$P(t)=\sum_{k=0}^n x_k t^k,$$
and rewriting both ratios in terms of $P$.
The first lemma states that each ratio can be expressed as
$$\frac{A_{n-1}}{A_n} = 1 - \frac{x_n a^n}{P(a)},\quad \frac{B_{n-1}}{B_n} = 1 - \frac{x_n b^n}{P(b)}.$$
This follows directly from separating the leading term of the polynomial.
The second lemma reduces the comparison of ratios to the inequality
$$\frac{a^n}{P(a)} > \frac{b^n}{P(b)}.$$
The third lemma establishes that the function
$$g(t)=\frac{t^n}{P(t)}$$
is strictly increasing for $t>1$.
The main argument depends critically on the third lemma, since it connects the ordering of bases to the ordering of ratios.
Solution
Let
$$P(t)=\sum_{k=0}^n x_k t^k.$$
Then $A_n=P(a)$ and $B_n=P(b)$. Since $A_{n-1}=P(a)-x_n a^n$ and $B_{n-1}=P(b)-x_n b^n$, it follows that
$$\frac{A_{n-1}}{A_n}=1-\frac{x_n a^n}{P(a)},\quad \frac{B_{n-1}}{B_n}=1-\frac{x_n b^n}{P(b)}.$$
This expresses both ratios in terms of a single rational function in the base, isolating the contribution of the highest digit.
The inequality
$$\frac{A_{n-1}}{A_n}<\frac{B_{n-1}}{B_n}$$
is equivalent to
$$\frac{x_n a^n}{P(a)}>\frac{x_n b^n}{P(b)}.$$
Since $x_n>0$, this reduces to
$$\frac{a^n}{P(a)}>\frac{b^n}{P(b)}.$$
Thus the problem becomes the monotonicity of the function
$$g(t)=\frac{t^n}{P(t)}.$$
For $u>v>1$, comparison of $g(u)$ and $g(v)$ reduces to
$$u^n P(v) > v^n P(u).$$
Expanding $P$ gives
$$u^n \sum_{k=0}^n x_k v^k > v^n \sum_{k=0}^n x_k u^k,$$
which is equivalent to
$$\sum_{k=0}^n x_k \left(u^n v^k - v^n u^k\right) > 0.$$
Each term admits the factorization
$$u^n v^k - v^n u^k = u^k v^k\left(u^{n-k}-v^{n-k}\right),$$
so the expression becomes
$$\sum_{k=0}^n x_k u^k v^k \left(u^{n-k}-v^{n-k}\right).$$
For $k<n$, the factor $u^{n-k}-v^{n-k}$ is positive since $u>v>1$. For $k=n$, the factor $u^{n-n}-v^{n-n}$ equals $1-1=0$, so the corresponding term vanishes. The term corresponding to $k=n-1$ equals
$$x_{n-1} u^{n-1} v^{n-1}(u-v),$$
which is positive since $x_{n-1}\neq 0$ and $u>v$. Every other term with $k<n$ is nonnegative because $x_k\ge 0$ and all remaining factors are positive. Hence the sum is positive, giving
$$u^n P(v) > v^n P(u),$$
so $g(u)>g(v)$. This establishes strict monotonicity of $g$ on $(1,\infty)$.
Consequently, $a>b$ implies $g(a)>g(b)$, which is equivalent to
$$\frac{a^n}{P(a)}>\frac{b^n}{P(b)},$$
and therefore
$$\frac{A_{n-1}}{A_n}<\frac{B_{n-1}}{B_n}.$$
Conversely, if $a<b$, the same monotonicity yields $g(a)<g(b)$, reversing the inequality between the ratios. This completes the equivalence.
This completes the proof. ∎
Verification of Key Steps
The transformation from digit expansions to the polynomial $P(t)$ preserves all information because positional notation is exactly a polynomial evaluation. Any mistake here would arise from incorrectly separating the leading digit term, but the decomposition $P(t)=x_n t^n + \sum_{k=0}^{n-1} x_k t^k$ ensures the truncation identities are exact identities.
The reduction to the inequality $u^n P(v) > v^n P(u)$ is reversible since all quantities involved are positive for bases greater than $1$. A potential failure would occur if signs were ignored, but every term in $P(t)$ is nonnegative, ensuring no sign changes occur in cross-multiplication.
The final summation argument depends on isolating positivity termwise after factorization. The only potentially vanishing contribution is the $k=n$ term, which is identically zero, while the assumption $x_{n-1}\neq 0$ guarantees at least one strictly positive term remains, preventing degeneracy.
Alternative Approaches
An alternative approach replaces the polynomial comparison with convexity. Writing $g(t)=t^n/P(t)$ and differentiating shows positivity of the derivative, giving monotonicity through calculus rather than algebraic factorization. Another approach normalizes the digit string and interprets the ratios as weighted means of powers of the base, leading to a comparison via rearrangement inequalities. The algebraic expansion method is preferable because it avoids analytic machinery and yields direct termwise positivity valid for all digit sequences simultaneously.