Maths Olympiad Prep

Library / /225 of 520

Number theory Difficulty 6.8 National olympiad Prove it

Prove that there is no positive integer nn such that, for k=1,2,,9k = 1,2,\ldots,9, the leftmost digit (in decimal notation) of (n+k)!(n+k)! equals kk.

Solution

1. Assume for contradiction: Suppose there exists a positive integer n n such that for k=1,2,,9 k = 1, 2, \ldots, 9 , the leftmost digit of (n+k)! (n+k)! equals k k .

2. Define the reduced copy: Let the reduced copy of a positive integer n n be a a , where n=a10b n = a \cdot 10^b for a nonnegative integer b b and a terminating decimal a a such that 1a<10 1 \le a < 10 .

3. Leading digit condition: If the leading digit of n n is k k , then the reduced copy of n n is between k k and k+1 k+1 .

4. Analyze the reduced copy of factorials:
- The reduced copy of (n+1)! (n+1)! is between 1 1 and 2 2 .
- The reduced copy of (n+2)! (n+2)! is between 2 2 and 3 3 .

5. Generalize the bounds:
- For (n+2)! (n+2)! , the reduced copy must be between 22=1 \frac{2}{2} = 1 and 31=3 \frac{3}{1} = 3 .
- For (n+3)! (n+3)! , the reduced copy must be between 33=1 \frac{3}{3} = 1 and 42=2 \frac{4}{2} = 2 .
- For (n+9)! (n+9)! , the reduced copy must be between 99=1 \frac{9}{9} = 1 and 108=1.25 \frac{10}{8} = 1.25 .

6. Establish the range: Note that the lower bound is always 1 1 and the upper bound starts at 3 3 and slowly reduces to 1.25 1.25 .

7. Claim: The reduced copy of all numbers from n+2 n+2 to n+9 n+9 must be between 1 1 and 1.25 1.25 .

8. Proof by contradiction:
- Suppose not. Since the numbers from n+2 n+2 to n+9 n+9 are consecutive, there will be a number from n+2 n+2 to n+9 n+9 with a reduced copy between 9 9 and 10 10 .
- This is impossible because that does not fit into any of the earlier ranges (which had a lower bound of 1 1 and an upper bound of at most 3 3 ).

9. Contradiction:
- Note that the reduced copy of (n+1)! (n+1)! is between 1 1 and 2 2 .
- Since the reduced copies of n+2,n+3,n+4 n+2, n+3, n+4 are all between 1 1 and 1.25 1.25 , the reduced copy of (n+4)! (n+4)! is less than 2(1.25)3=3.90625<4 2(1.25)^3 = 3.90625 < 4 .
- This is a contradiction as it must be between 4 4 and 5 5 .

Therefore, there is no positive integer n n such that for k=1,2,,9 k = 1, 2, \ldots, 9 , the leftmost digit of (n+k)! (n+k)! equals k k .

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.