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.
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.
Leave a Reply
You must be logged in to post a comment.