Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2001 IMO Shortlist Problems/N1"

(Added a solution)
m (→‎Solution)
 
Line 37: Line 37:
  
 
So <math>(n + 4)!</math> has <math>c+3b-3</math> digits, but is smaller than the smallest <math>c+3b-3</math> digit number with the first digit 4, which means that its first digit can't be 4. This contradicts with how <math>n</math> is defined, thus no such value of <math>n</math> exists.
 
So <math>(n + 4)!</math> has <math>c+3b-3</math> digits, but is smaller than the smallest <math>c+3b-3</math> digit number with the first digit 4, which means that its first digit can't be 4. This contradicts with how <math>n</math> is defined, thus no such value of <math>n</math> exists.
 +
 +
~Circling
  
 
== Resources ==
 
== Resources ==

Latest revision as of 07:14, 1 April 2022

Problem

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

Solution

Suppose that there is such a number $n$. Let $a$ be the number of digits of $(n + 8)!$, and let $b$ be the number of digits of $n + 9$. Then we have:

$8 \cdot 10^{a-1} \leqslant (n + 8)! < 9 \cdot 10^{a-1}$

and

$10^{b-1} \leqslant n + 9 < 10^b$

Combining these inequalities via multiplication we get:

$8 \cdot 10^{a+b-2} \leqslant (n+9)! < 9 \cdot 10^{a+b-1}$

From this inequality, it can be seen that $(n+9)!$ has at least $a+b-1$ and at most $a+b$ digits. However, if it has $a+b$ digits then the first digit is less than $9$, which contradicts with how $n$ is defined. Thus, $(n+9)!$ must have $a+b-1$ digits. Expressing this as an inequality, we get:

$9 \cdot 10^{a+b-2} \leqslant (n+9)! < 10^{a+b-1}$

Combining these values with the earlier bounds for $(n+8)!$ via division, we get:

$10^{b-1} < n+9 < \frac{5}4 10^{b - 1}$

Suppose that $n+1 < 10^{b-1}$. Then $10^{b-1}$ is between $n+1$ and $n+9$. Thus, one of the values $n+2,n+2,\ldots n+8$ must be $10^{b-1}$. Call that value $n+l &nbsp; (1 < l < 9)$. This means that the digits of $(n+l)!$ are just the digits of $(n+l-1)!$, followed by $b-1$ zeroes. Thus the first digit of the two numbers are equal, which contradicts with how $n$ is defined. This means that:

$10^{b-1} \leqslant n+1 < n+2 < n+3 < n+4 < n+9 < \frac{5}4 10^{b - 1}$

Let $c$ be the number of digits of $(n+1)!$. Then we have:

$10^{c-1} \leqslant (n+1)! < 2 \cdot 10^{c-1}$

Combining these with the bounds for $n+2$, $n+3$ and $n+4$ via multiplication we get:

$10^{c+3b-4} \leqslant (n+4)! < \frac{125}{32}10^{c+3b-4} < 4 \cdot 10^{c+3b-4}$

So $(n + 4)!$ has $c+3b-3$ digits, but is smaller than the smallest $c+3b-3$ digit number with the first digit 4, which means that its first digit can't be 4. This contradicts with how $n$ is defined, thus no such value of $n$ exists.

~Circling

Resources

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2001_IMO_Shortlist_Problems/N1&oldid=173130"