Maths Olympiad Prep

Library / /5 of 5

Number theory Difficulty 7.2 National olympiad, round 2 Prove it Brazil

Call a super-integer an infinite sequence of decimal digits: dnd3d2d1\ldots d_n \ldots d_3 d_2 d_1. Given two super-integers cnc3c2c1\ldots c_n \ldots c_3 c_2 c_1 and dnd3d2d1\ldots d_n \ldots d_3 d_2 d_1, their product pnp3p2p1\ldots p_n \ldots p_3 p_2 p_1 is formed by taking pnp3p2p1p_n \ldots p_3 p_2 p_1 to be the last nn digits of the product cnc3c2c1c_n \ldots c_3 c_2 c_1 and dnd3d2d1d_n \ldots d_3 d_2 d_1. Can we find two non-zero super-integers with zero product? A zero super-integer has all its digits zero.

Solution

The answer is yes. In fact, there exist two sequences x=anx = \ldots a_n \ldots and y=bny = \ldots b_n \ldots such that, for every k1k \ge 1, 2k2^k divides aka2a1a_k \ldots a_2 a_1 and 5k5^k divides bkb2b1b_k \ldots b_2 b_1; then 10k10^k divides aka2a1×bkb2b1a_k \ldots a_2 a_1 \times b_k \ldots b_2 b_1 and xy=0xy = 0.

Consider first xx. We proceed by induction. For k=1k=1 choose a1=2a_1=2. Suppose ama2a1a_m \ldots a_2 a_1 is a multiple of 2m2^m and let cmc_m be ama2a1a_m \ldots a_2 a_1 divided by 2m2^m. Then am+1ama2a1=10mam+1+ama2a1=2m(5mam+1+cm)a_{m+1} a_m \ldots a_2 a_1 = 10^m \cdot a_{m+1} + a_m \ldots a_2 a_1 = 2^m (5^m \cdot a_{m+1} + c_m) and we may choose am+1=0a_{m+1}=0 or 11 according to the parity of cmc_m, so 5mam+1+cm5^m \cdot a_{m+1} + c_m is even and, consequently, am+1ama2a1a_{m+1} a_m \ldots a_2 a_1 is a multiple of 2m+12^{m+1}. This completes the induction.

The induction for yy is not that different. Indeed, choose b1=5b_1=5 and suppose bmb2b1=5mdmb_m \ldots b_2 b_1 = 5^m \cdot d_m. Then bm+1bmb2b1=10mbm+1+bmb2b1=5m(2mbm+1+dm)b_{m+1} b_m \ldots b_2 b_1 = 10^m \cdot b_{m+1} + b_m \ldots b_2 b_1 = 5^m (2^m \cdot b_{m+1} + d_m) and it's always possible to choose bm+1{0,1,2,3,4}b_{m+1} \in \{0, 1, 2, 3, 4\} such that 2mbm+1dm(mod5)2^m \cdot b_{m+1} \equiv -d_m \pmod{5}, since 2m2^m admits inverse modulo 55.

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.