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"

(New page: == Problem == Prove that there is no positive integer <math>n</math> such that, for <math>k = 1,2,\ldots,9</math>, the leftmost digit (in decimal notation) of <math>(n + k)!</math> equals ...)
 
m (→‎Solution)
 
(One intermediate revision by the same user not shown)
Line 3: Line 3:
  
 
== Solution ==
 
== Solution ==
−
{{solution}}
+
Suppose that there is such a number <math>n</math>. Let <math>a</math> be the number of digits of <math>(n + 8)!</math>, and let <math>b</math> be the number of digits of <math>n + 9</math>. Then we have:
 +
 
 +
<math>8 \cdot 10^{a-1} \leqslant (n + 8)! < 9 \cdot 10^{a-1}</math>
 +
 
 +
and
 +
 
 +
<math>10^{b-1} \leqslant n + 9 < 10^b</math>
 +
 
 +
Combining these inequalities via multiplication we get:
 +
 
 +
<math>8 \cdot 10^{a+b-2} \leqslant (n+9)! < 9 \cdot 10^{a+b-1}</math>
 +
 
 +
From this inequality, it can be seen that <math>(n+9)!</math> has at least <math>a+b-1</math> and at most <math>a+b</math> digits. However, if it has <math>a+b</math> digits then the first digit is less than <math>9</math>, which contradicts with how <math>n</math> is defined. Thus, <math>(n+9)!</math> must have <math>a+b-1</math> digits. Expressing this as an inequality, we get:
 +
 
 +
<math>9 \cdot 10^{a+b-2} \leqslant (n+9)! < 10^{a+b-1}</math>
 +
 
 +
Combining these values with the earlier bounds for <math>(n+8)!</math> via division, we get:
 +
 
 +
<math>10^{b-1} < n+9 < \frac{5}4 10^{b - 1}</math>
 +
 
 +
Suppose that <math>n+1 < 10^{b-1}</math>. Then <math>10^{b-1}</math> is between <math>n+1</math> and <math>n+9</math>. Thus, one of the values <math>n+2,n+2,\ldots n+8</math> must be <math>10^{b-1}</math>. Call that value <math>n+l &nbsp; (1 < l < 9)</math>. This means that the digits of <math>(n+l)!</math> are just the digits of <math>(n+l-1)!</math>, followed by <math>b-1</math> zeroes. Thus the first digit of the two numbers are equal, which contradicts with how <math>n</math> is defined.
 +
This means that:
 +
 
 +
<math>10^{b-1} \leqslant n+1 < n+2 < n+3 < n+4 < n+9 < \frac{5}4 10^{b - 1}</math>
 +
 
 +
Let <math>c</math> be the number of digits of <math>(n+1)!</math>. Then we have:
 +
 
 +
<math>10^{c-1} \leqslant (n+1)! < 2 \cdot 10^{c-1}</math>
 +
 
 +
Combining these with the bounds for <math>n+2</math>, <math>n+3</math> and <math>n+4</math> via multiplication we get:
 +
 
 +
<math>10^{c+3b-4} \leqslant (n+4)! < \frac{125}{32}10^{c+3b-4} < 4 \cdot 10^{c+3b-4}</math>
 +
 
 +
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 08: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"