Maths Olympiad Prep

Library / MMO Round 4 /9 of 17

MMO Round 4

Number theory Difficulty 5.7 AIME, harder Prove it Mongolia

Let n≥3n \ge 3 be a given integer, and S≥1S \ge 1 be a multiple of 10n−310^n - 3. Suppose that the decimal expansion of SS has mm digits and 2n−1>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=am…a1‾A = \overline{a_m \dots a_1} such that am…a1‾\overline{a_m \dots a_1} has at most 2 different digits and d∣Ad \mid A, where dd denotes 10n−310^n - 3. Consider S=an…a1‾+3×am…an+1‾S = \overline{a_n \dots a_1} + 3 \times \overline{a_m \dots a_{n+1}} which exists since m>nm > n. It follows from d∣Ad \mid A that d∣Sd \mid S. Moreover, the assumption that 2n−2≥m2n-2 \ge m yields S≤10n−1+3×(10n−2−1)<2dS \le 10^n - 1 + 3 \times (10^{n-2} - 1) < 2d and so we must have
an…a1‾+3×am…an+1‾=10n−3.(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+1≡7(mod10)a_1 + 3a_{n+1} \equiv 7 \pmod{10} and consequently, a1≠an+1a_1 \neq a_{n+1}. Observe that
an…a1‾=d−3×am…an+1‾>d−3×(10n−2−1)>9×10n−1, \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,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.