2005 Indonesia MO Problems/Problem 2
Problem
For an arbitrary positive integer , define as the product of the digits of (in decimal). Find all positive integers such that .
Solution
First we will prove that must have 2 digits. Afterward, we'll let and will solve for .
Lemma: must have 2 digits
First, if , then is a negative number, so must have more than 1 digit.
Next, we will show that can not have 3 digits. Since 2005 is not a perfect square, can not have any zeroes. That means the minimum value of that has digits is . The maximum value of with three digits is . For the case where , the minimum number is and the maximum value of is . Since , all three-digit values of more than 111 have , so can not be a 3-digit number.
Finally, we will use induction to show that if can not have four or more digits. If has digits, where , then the maximum value of is while the minimum value of is . For the base case, since , we would have for all four digit numbers, so no four digit number would work.
Assume that , where . Multiplying both sides by 100 and adding 2005(99) results in
With the induction step complete, we've shown that if . Since and , we have , so can not be number with four or more digits. Thus, must be a two-digit number.
From the Lemma, let . Substitution results in
Taking the equation modulo 4, we have . That means . Let , resulting in
If , then , so and . Substitution results in
The only feasible value of is , so the only positive integer such that is . When plugging the value in, the equality holds.
See Also
2005 Indonesia MO (Problems) | ||
Preceded by Problem 1 |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 | Followed by Problem 3 |
All Indonesia MO Problems and Solutions |