Maths Olympiad Prep

Library / New Zealand Mathematical Olympiad /5 of 11

New Zealand Mathematical Olympiad

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,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.