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 "1970 IMO Problems/Problem 2"

m (Take out a link to a page which does not exist.)
 
(One intermediate revision by the same user not shown)
Line 27: Line 27:
 
<cmath> \frac{A_{n-1}}{A_n} = 1 - \frac{x_n a^n}{A_n} < 1 - \frac{x_n b^n}{B_n} = \frac{B_{n-1}}{B_n} . </cmath>
 
<cmath> \frac{A_{n-1}}{A_n} = 1 - \frac{x_n a^n}{A_n} < 1 - \frac{x_n b^n}{B_n} = \frac{B_{n-1}}{B_n} . </cmath>
 
On the other hand, if <math>a=b</math>, then evidently <math>A_{n-1}/A_n = B_{n-1}/B_n</math>, and if <math>a < b</math>, then by what we have just shown, <math>A_{n-1}/A_n > B_{n-1}/B_n</math>.  Hence <math>A_{n-1}/A_n < B_{n-1}/B_n</math> if and only if <math>a>b</math>, as desired.  <math>\blacksquare</math>
 
On the other hand, if <math>a=b</math>, then evidently <math>A_{n-1}/A_n = B_{n-1}/B_n</math>, and if <math>a < b</math>, then by what we have just shown, <math>A_{n-1}/A_n > B_{n-1}/B_n</math>.  Hence <math>A_{n-1}/A_n < B_{n-1}/B_n</math> if and only if <math>a>b</math>, as desired.  <math>\blacksquare</math>
 +
 +
 +
==Remarks (added by pf02, November 2024)==
 +
 +
1. A comment about the problem: it is disappointing.  It is surprisingly
 +
easy compared to other problems given at an International Mathematical
 +
Olympiad, and frankly, uninteresting.
 +
 +
2. It is not stated with the usual rigor typical at this competition.  The
 +
problem is really the following two statements:
 +
 +
S1: Let <math>a, b, n > 0</math> and <math>x_n, x_{n-1}, \cdots, x_0</math> be integers,
 +
<math>x_k < a, b</math> for all <math>k</math>, <math>x_n > 0</math>, and <math>x_{n-1}, \cdots, x_0</math> not all <math>0</math>.
 +
Define <math>A_n, A_{n-1}, B_n, B_{n-1}</math> as described in the problem.  If
 +
 +
<math>\frac{A_{n-1}}{A_{n}} < \frac{B_{n-1}}{B_{n}}\ \ \ \ \ \ \ \ (1)</math>
 +
 +
then <math>a > b</math>.
 +
 +
S2: If <math>a > b</math>, then (1) is true for any <math>x_n, x_{n-1}, \cdots, x_0</math>.
 +
 +
3. I will give a variation of the solution in which the computations
 +
and argumentation are slightly simpler and more direct.
 +
 +
 +
==Solution 2==
 +
 +
Rewrite inequality (1), and give a few steps in which we state
 +
equivalent inequalities:
 +
 +
<math>\frac{x_{n-1} a^{n-1} + \cdots + x_1 a + x_0}{x_n a^n + x_{n-1} a^{n-1} + \cdots + x_1 a + x_0} <
 +
\frac{x_{n-1} b^{n-1} + \cdots + x_1 b + x_0}{x_n b^n + x_{n-1} b^{n-1} + \cdots + x_1 b + x_0}</math>
 +
 +
<math>\frac{x_{n-1} a^{n-1} + \cdots + x_1 a + x_0}{x_n a^n} <
 +
\frac{x_{n-1} b^{n-1} + \cdots + x_1 b + x_0}{x_n b^n}</math>
 +
 +
<math>\frac{x_{n-1} a^{n-1} + \cdots + x_1 a + x_0}{a^n} <
 +
\frac{x_{n-1} b^{n-1} + \cdots + x_1 b + x_0}{b^n}</math>
 +
 +
<math>x_{n-1} \frac{1}{a} + \cdots + x_1 \frac{1}{a^{n-1}} + x_0 \frac{1}{a^n} <
 +
x_{n-1} \frac{1}{b} + \cdots + x_1 \frac{1}{b^{n-1}} + x_0 \frac{1}{b^n}\ \ \ \ \ \ \ \ (2)</math>
 +
 +
Now it is clear that if <math>a > b</math> then (2) is true for any
 +
<math>x_n, x_{n-1}, \cdots, x_0</math>.  This proves statement S2 from the Remarks.
 +
 +
(Note that the problem said <math>x_n, x_{n-1} > 0</math>.  This is not necessary.
 +
All we need is that <math>x_n > 0</math> and at least one of <math>x_{n-1}, \cdots, x_1, x_0</math>
 +
is <math>\neq 0</math>.)
 +
 +
We prove statement S1 from the Remarks by contradiction.  We want to show
 +
that if (1) is true for some <math>x_n, \cdots, x_1, x_0</math>, then <math>a > b</math>.
 +
 +
Assume <math>a \le b</math>.  If we had <math>a = b</math> then (1) would be an equality, not an
 +
inequality.
 +
 +
If <math>a < b</math> then by S1, it would follow that
 +
<math>\frac{A_{n-1}}{A_{n}} > \frac{B_{n-1}}{B_{n}}</math> for all values of
 +
<math>x_n, \cdots, x_1, x_0</math> which contradicts the hypothesis.  Either way, we
 +
get a contradiction, which proves S1.
 +
 +
[Solution by pf02, November 2024]
  
  

Latest revision as of 18:28, 26 November 2024

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$.

Solution

Suppose $a>b$. Then for all integers $0 \le k \le n$, $x_n x_k a^n b^k \ge x_n x_k b^n a^k$, with equality only when $k=n$ or $x_k = 0$. (In particular, we have strict inequality for $k=n-1$.) In summation, this becomes \[x_n a^n \sum_{k=0}^n x_k b^k > x_n b^n \sum_{k=0}^n x_k a^k,\] or \[x_n a^n \cdot B_n > x_n b^n \cdot A_n,\] which is equivalent to \[\frac{x_n a^n}{A_n} > \frac{x_n b^n}{B_n} .\] This implies \[\frac{A_{n-1}}{A_n} = 1 - \frac{x_n a^n}{A_n} < 1 - \frac{x_n b^n}{B_n} = \frac{B_{n-1}}{B_n} .\] On the other hand, if $a=b$, then evidently $A_{n-1}/A_n = B_{n-1}/B_n$, and if $a < b$, then by what we have just shown, $A_{n-1}/A_n > B_{n-1}/B_n$. Hence $A_{n-1}/A_n < B_{n-1}/B_n$ if and only if $a>b$, as desired. $\blacksquare$


Remarks (added by pf02, November 2024)

1. A comment about the problem: it is disappointing. It is surprisingly easy compared to other problems given at an International Mathematical Olympiad, and frankly, uninteresting.

2. It is not stated with the usual rigor typical at this competition. The problem is really the following two statements:

S1: Let $a, b, n > 0$ and $x_n, x_{n-1}, \cdots, x_0$ be integers, $x_k < a, b$ for all $k$, $x_n > 0$, and $x_{n-1}, \cdots, x_0$ not all $0$. Define $A_n, A_{n-1}, B_n, B_{n-1}$ as described in the problem. If

$\frac{A_{n-1}}{A_{n}} < \frac{B_{n-1}}{B_{n}}\ \ \ \ \ \ \ \ (1)$

then $a > b$.

S2: If $a > b$, then (1) is true for any $x_n, x_{n-1}, \cdots, x_0$.

3. I will give a variation of the solution in which the computations and argumentation are slightly simpler and more direct.


Solution 2

Rewrite inequality (1), and give a few steps in which we state equivalent inequalities:

$\frac{x_{n-1} a^{n-1} + \cdots + x_1 a + x_0}{x_n a^n + x_{n-1} a^{n-1} + \cdots + x_1 a + x_0} < \frac{x_{n-1} b^{n-1} + \cdots + x_1 b + x_0}{x_n b^n + x_{n-1} b^{n-1} + \cdots + x_1 b + x_0}$

$\frac{x_{n-1} a^{n-1} + \cdots + x_1 a + x_0}{x_n a^n} < \frac{x_{n-1} b^{n-1} + \cdots + x_1 b + x_0}{x_n b^n}$

$\frac{x_{n-1} a^{n-1} + \cdots + x_1 a + x_0}{a^n} < \frac{x_{n-1} b^{n-1} + \cdots + x_1 b + x_0}{b^n}$

$x_{n-1} \frac{1}{a} + \cdots + x_1 \frac{1}{a^{n-1}} + x_0 \frac{1}{a^n} < x_{n-1} \frac{1}{b} + \cdots + x_1 \frac{1}{b^{n-1}} + x_0 \frac{1}{b^n}\ \ \ \ \ \ \ \ (2)$

Now it is clear that if $a > b$ then (2) is true for any $x_n, x_{n-1}, \cdots, x_0$. This proves statement S2 from the Remarks.

(Note that the problem said $x_n, x_{n-1} > 0$. This is not necessary. All we need is that $x_n > 0$ and at least one of $x_{n-1}, \cdots, x_1, x_0$ is $\neq 0$.)

We prove statement S1 from the Remarks by contradiction. We want to show that if (1) is true for some $x_n, \cdots, x_1, x_0$, then $a > b$.

Assume $a \le b$. If we had $a = b$ then (1) would be an equality, not an inequality.

If $a < b$ then by S1, it would follow that $\frac{A_{n-1}}{A_{n}} > \frac{B_{n-1}}{B_{n}}$ for all values of $x_n, \cdots, x_1, x_0$ which contradicts the hypothesis. Either way, we get a contradiction, which proves S1.

[Solution by pf02, November 2024]


Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

Resources

1970 IMO (Problems) • Resources
Preceded by
Problem 1 		1 • 2 • 3 • 4 • 5 • 6 Followed by
Problem 3
All IMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1970_IMO_Problems/Problem_2&oldid=235650"