Maths Olympiad Prep

Library / Brazilian Math Olympiad /47 of 66

Brazilian Math Olympiad

Algebra Difficulty 6.5 National Olympiad Prove it Brazil

For each positive integer NN with 2k2k digits, let odd(N)\text{odd}(N) be the kk-digit number obtained by writing the digits of odd order of NN and even(N)\text{even}(N) be the kk-digit number obtained by writing the digits of even order of NN. For example, odd(249035)=405\text{odd}(249035) = 405 and even(249035)=293\text{even}(249035) = 293. Prove that there is no positive integer NN with 2k2k digits such that N=odd(N)⋅even(N)N = \text{odd}(N) \cdot \text{even}(N).

Solution

We will prove by induction that odd(N)⋅even(N)<N\text{odd}(N) \cdot \text{even}(N) < N for all positive integers NN with 2k2k digits.

If N=10a+bN = 10a + b, a,b∈{0,1,2,…,9}a, b \in \{0, 1, 2, \dots, 9\}, a≠0a \neq 0, N=10a+b>a⋅b+b≥a⋅b=even(N)⋅odd(N)N = 10a + b > a \cdot b + b \ge a \cdot b = \text{even}(N) \cdot \text{odd}(N).

Now suppose that NN has 2k>22k > 2 digits and that the claim is true for all numbers with 2k−22k-2 digits. Let cc and dd be the two leftmost digits of NN, so that N=c⋅102k−1+d⋅102k−2+N0N = c \cdot 10^{2k-1} + d \cdot 10^{2k-2} + N_0, N0N_0 with 2k−22k-2 digits. Then odd(N)=d⋅10k−1+odd(N0)\text{odd}(N) = d \cdot 10^{k-1} + \text{odd}(N_0) and even(N)=c⋅10k−1+even(N0)\text{even}(N) = c \cdot 10^{k-1} + \text{even}(N_0). So we need to prove that
c⋅102k−1+d⋅102k−2+N0>(c⋅10k−1+even(N0))⋅(d⋅10k−1+odd(N0))  ⟺  c⋅102k−1+d⋅102k−2+N0>cd⋅102k−2+d⋅10k−1⋅even(N0)+c⋅10k−1⋅odd(N0)+odd(N0)⋅even(N0) \begin{align*} c \cdot 10^{2k-1} + d \cdot 10^{2k-2} + N_0 &> (c \cdot 10^{k-1} + \text{even}(N_0)) \cdot (d \cdot 10^{k-1} + \text{odd}(N_0)) \\ \iff c \cdot 10^{2k-1} + d \cdot 10^{2k-2} + N_0 &> cd \cdot 10^{2k-2} + d \cdot 10^{k-1} \cdot \text{even}(N_0) + c \cdot 10^{k-1} \cdot \text{odd}(N_0) + \text{odd}(N_0) \cdot \text{even}(N_0) \end{align*}
But this is true, since both odd(N0)\text{odd}(N_0) and even(N0)\text{even}(N_0) are less than 10k−110^{k-1} and thus
c⋅102k−1≥c(d+1)⋅102k−2>cd⋅102k−2+c⋅10k−1⋅odd(N0)d⋅102k−2>d⋅10k−1⋅even(N0)N0>odd(N0)⋅even(N0) \begin{align*} c \cdot 10^{2k-1} &\ge c(d+1) \cdot 10^{2k-2} > cd \cdot 10^{2k-2} + c \cdot 10^{k-1} \cdot \text{odd}(N_0) \\ d \cdot 10^{2k-2} &> d \cdot 10^{k-1} \cdot \text{even}(N_0) \\ N_0 &> \text{odd}(N_0) \cdot \text{even}(N_0) \end{align*}

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.