Maths Olympiad Prep

Library / /5 of 11

Combinatorics Difficulty 6.0 AIME, harder Prove it New Zealand

Problem:
A positive integer is called sparkly if it has exactly 9 digits, and for any nn between 11 and 99 (inclusive), the nthn^{\text{th}} digit is a positive multiple of nn. How many positive integers are sparkly?

Solution

Solution:
For each n=1,2,,9n = 1, 2, \ldots, 9 there are 9/n\lfloor 9 / n \rfloor different possibilities for the nthn^{\mathrm{th}} digit. For example, there are 9/2=4\lfloor 9 / 2 \rfloor = 4 possible choices for the second digit (these being 2,4,62, 4, 6 and 88). Therefore the answer is
91×92×93×94×95×96×97×98×99 \left\lfloor \frac{9}{1} \right\rfloor \times \left\lfloor \frac{9}{2} \right\rfloor \times \left\lfloor \frac{9}{3} \right\rfloor \times \left\lfloor \frac{9}{4} \right\rfloor \times \left\lfloor \frac{9}{5} \right\rfloor \times \left\lfloor \frac{9}{6} \right\rfloor \times \left\lfloor \frac{9}{7} \right\rfloor \times \left\lfloor \frac{9}{8} \right\rfloor \times \left\lfloor \frac{9}{9} \right\rfloor
which equals 9×4×3×2×1×1×1×1×1=2169 \times 4 \times 3 \times 2 \times 1 \times 1 \times 1 \times 1 \times 1 = 216

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 reproduced verbatim; metadata (topic, difficulty) added by this project.