Maths Olympiad Prep

Library / /18 of 27

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\}, a0a \neq 0, N=10a+b>ab+bab=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 2k22k-2 digits. Let cc and dd be the two leftmost digits of NN, so that N=c102k1+d102k2+N0N = c \cdot 10^{2k-1} + d \cdot 10^{2k-2} + N_0, N0N_0 with 2k22k-2 digits. Then odd(N)=d10k1+odd(N0)\text{odd}(N) = d \cdot 10^{k-1} + \text{odd}(N_0) and even(N)=c10k1+even(N0)\text{even}(N) = c \cdot 10^{k-1} + \text{even}(N_0). So we need to prove that
c102k1+d102k2+N0>(c10k1+even(N0))(d10k1+odd(N0))    c102k1+d102k2+N0>cd102k2+d10k1even(N0)+c10k1odd(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 10k110^{k-1} and thus
c102k1c(d+1)102k2>cd102k2+c10k1odd(N0)d102k2>d10k1even(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,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.