Maths Olympiad Prep

Library / Brazilian Mathematical Olympiad /118 of 120

Brazilian Mathematical Olympiad

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

Call a super-integer an infinite sequence of decimal digits: …dn…d3d2d1\ldots d_n \ldots d_3 d_2 d_1. Given two super-integers …cn…c3c2c1\ldots c_n \ldots c_3 c_2 c_1 and …dn…d3d2d1\ldots d_n \ldots d_3 d_2 d_1, their product …pn…p3p2p1\ldots p_n \ldots p_3 p_2 p_1 is formed by taking pn…p3p2p1p_n \ldots p_3 p_2 p_1 to be the last nn digits of the product cn…c3c2c1c_n \ldots c_3 c_2 c_1 and dn…d3d2d1d_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=…an…x = \ldots a_n \ldots and y=…bn…y = \ldots b_n \ldots such that, for every k≥1k \ge 1, 2k2^k divides ak…a2a1a_k \ldots a_2 a_1 and 5k5^k divides bk…b2b1b_k \ldots b_2 b_1; then 10k10^k divides ak…a2a1×bk…b2b1a_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 am…a2a1a_m \ldots a_2 a_1 is a multiple of 2m2^m and let cmc_m be am…a2a1a_m \ldots a_2 a_1 divided by 2m2^m. Then am+1am…a2a1=10m⋅am+1+am…a2a1=2m(5m⋅am+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 5m⋅am+1+cm5^m \cdot a_{m+1} + c_m is even and, consequently, am+1am…a2a1a_{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 bm…b2b1=5m⋅dmb_m \ldots b_2 b_1 = 5^m \cdot d_m. Then bm+1bm…b2b1=10m⋅bm+1+bm…b2b1=5m(2m⋅bm+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 2m⋅bm+1≡−dm(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,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.