Track / Stage 4 / 236 of 340 #976 of 2444

Problem 976

AMC 12 late, AIME early

Combinatorics Difficulty 4.9 Prove it Brazilian Mathematical Olympiad · Brazil

A positive integer is dapper if at least one of its multiples begins with $2008$ . For example, $7$ is dapper because $200858$ is a multiple of $7$ and begins with $2008$ . Observe that $200858 = 28694 \times 7$ .
Prove that every positive integer is dapper.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

Let $n$ be any positive integer. Choose $k$ to be an integer greater than the number of digits of $n$ . So the interval $[2008 \cdot 10^k, 2009 \cdot 10^k[$ , which contains $10^k > n$ integer consecutive numbers, has a multiple of $n$ . So every positive integer $n$ is dapper.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.