Maths Olympiad Prep

Library / /9 of 17

Number theory Difficulty 5.7 AIME, harder Prove it Mongolia

Let n3n \ge 3 be a given integer, and S1S \ge 1 be a multiple of 10n310^n - 3. Suppose that the decimal expansion of SS has mm digits and 2n1>m>n2n - 1 > m > n. Show that SS has at least 3 different digits.
(Bayarmagnai Gombodorj)

Solution

Assume to the contrary that there exists an integer A=ama1A = \overline{a_m \dots a_1} such that ama1\overline{a_m \dots a_1} has at most 2 different digits and dAd \mid A, where dd denotes 10n310^n - 3. Consider S=ana1+3×aman+1S = \overline{a_n \dots a_1} + 3 \times \overline{a_m \dots a_{n+1}} which exists since m>nm > n. It follows from dAd \mid A that dSd \mid S. Moreover, the assumption that 2n2m2n-2 \ge m yields S10n1+3×(10n21)<2dS \le 10^n - 1 + 3 \times (10^{n-2} - 1) < 2d and so we must have
ana1+3×aman+1=10n3.(0.1) \overline{a_n \dots a_1} + 3 \times \overline{a_m \dots a_{n+1}} = 10^n - 3. \quad (0.1)
Hence a1+3an+17(mod10)a_1 + 3a_{n+1} \equiv 7 \pmod{10} and consequently, a1an+1a_1 \neq a_{n+1}. Observe that
ana1=d3×aman+1>d3×(10n21)>9×10n1, \overline{a_n \dots a_1} = d - 3 \times \overline{a_m \dots a_{n+1}} > d - 3 \times (10^{n-2} - 1) > 9 \times 10^{n-1},
which implies an=9a_n = 9. Thus 9{a1,an+1}9 \in \{a_1, a_{n+1}\} by the assumption on AA. If an+1=9a_{n+1} = 9 then a1=0a_1 = 0 and so AA is divisible by 9, contradicting to (0.1). If a1=9a_1 = 9 then an+1=6a_{n+1} = 6, giving a similar contradiction.

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.