# Mathematical Food for Thought

Serves a Daily Special and an All-You-Can-Eat Course in Problem Solving. Courtesy of me, Jeffrey Wang.

• ## Meta

All Those Digits. Topic: Number Theory. Level: Olympiad. December 28th, 2005

Problem: (2003 USAMO – #1) Prove that for every positive integer there exists an -digit number divisible by all of whose digits are odd.

Solution: We will prove the result by induction.

Base Case: works.

Suppose there exists a -digit positive integer with all odd digits that is divisible by . Call this integer .

Consider the following numbers:

, all of which have digits.

Let .

Then the above numbers become

.

Notice that are all different modulo (since they are in an arithmetic sequence with difference and ).

Therefore one of the numbers must be divisible by . Let that one be .

So one of the original numbers is , where is divisible by . Hence the number is divisible by and has digits, as desired. This completes the induction. QED.

——————–

Practice Problem: (1994 USAMO – #1) Let , be positive integers, no two consecutive, and let for . Prove that, for each positive integer , the interval contains at least one perfect square.

### 2 Responses to “All Those Digits. Topic: Number Theory. Level: Olympiad.”

1. QC Says:

s_n generates perfect squares if k_n = 2n – 1, which is the simplest and slowest-growing allowable sequence. Any other sequence must grow faster, and hence must contain perfect squares between each term.

Wow, that’s a USAMO question?