1
$\begingroup$

This question is from the introduction of a handbook on combinatorics. So far, the material covered contains:

  • counting problems solved by using trees, Pascal's triangle,...
  • definition of $n$ factorial
  • definitions of combinations, variations (based on allowing repitition and if order matters).

No formulas, except for the formula for $n$ factorial have been seen.

The question then asks to find all values of $n$ such that $$10^8 < n! < 10^{12}$$ and the given answers states that this holds for $n = 12,13,14$ (only a numerical answer is given, no reasoning).

I tried solving this by taking the logarithm with base 10 from all sides, but this did not really help (seemed to brute force to me).

question: is there some 'nice' way to prove this answer?

$\endgroup$
2
$\begingroup$

For the lower bound, observe that $$10^7=\underbrace{10\cdot 10\cdot ....\cdot 10}_{7\text{ times}}>10\cdot9\cdot8\cdot7\cdot6\cdot4\cdot3=9!\implies 10^8>10\cdot9!=10!$$

Thus $n>10$. Once noticed that $12!$ works (which isn’t very hard) observe the following for the upper bound

if $a\in(10^8, 10^{12})$, then $10^4\cdot a\not\in (10^8, 10^{12})$

In particular $a\cdot 13\cdot 14\cdot 15\cdot 16\not\in (10^8, 10^{12})$ since $a\cdot 13\cdot 14\cdot 15\cdot 16>a\cdot 10^4$.

Hence, since $12!$ satisfies the inequality, $12!\cdot 13\cdot 14\cdot 15\cdot 16=16!$ doesn’t.

$\endgroup$
  • $\begingroup$ Nice answer for the lower bound. I'll try to figure out if a similar reasoning gives an upper bound! $\endgroup$ – Student Apr 7 at 13:54
  • $\begingroup$ I’ve edited the answer for the upper bound ;) $\endgroup$ – Dr. Mathva Apr 7 at 14:15
  • $\begingroup$ Thansk for the edit, but 11! Does not satisfy this inequality. $\endgroup$ – Student Apr 7 at 14:20
  • $\begingroup$ I know, but the upper and lower bound aren’t necessarily the lowest and the uppest hounds, but the best ones I managed to achieve $\endgroup$ – Dr. Mathva Apr 7 at 14:29
  • $\begingroup$ Thank you. Not sure if this is the intended answer, but I like this one very much :) $\endgroup$ – Student Apr 7 at 14:33
1
$\begingroup$

There's a nice way (called "Stirling's approximation") to get a narrower estimate, but I think that the goal here was to have you think about things. For instance, you know that $n > 8$, because at $n = 8$, the left hand side is $$ 10 \cdot 10 \cdot 10 \cdot 10 \cdot 10 \cdot 10 \cdot 10 \cdot 10 $$ while the middle is $$ 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdot 6 \cdot 7 \cdot 8 $$ Since each factor of the second is smaller than the corresponding factor of the first, you clearly need a larger $n$.

On the other hand, $21!$ has $12$ factors that are at least $10$, namely $10, 11, 12, \ldots, 21$ (as well as a bunch of smaller factors). So $21!$ is definitely bigger than $10^{12}$. At this point, you know that $n$ is between $8$ and $21$, and trying a few numbers in between narrows things down pretty fast.

But along the way, I expect the author hopes that you've learned something about estimating factorials by not-very-subtle methods. (The proof I know of Stirling's formula, for instance, involves integrals.)

$\endgroup$
  • $\begingroup$ This seems like what was intented. This answer only uses what is assumed to be known, so I don't think that things can become much better. Thank you! $\endgroup$ – Student Apr 7 at 13:53
1
$\begingroup$

By taking logs of both sides, $$8\ln{(10)}\lt\ln{(n!)}\lt12\ln{(10)}$$ Then applying Stirling's approximation we have $$8\ln{(10)}\lt n\ln{(n)}-n+\frac12\ln{(2\pi n)}\lt12\ln{(10)}$$ $$18.4...\lt n\ln{(n)}-n+\frac12\ln{(2\pi n)}\lt27.6...$$ Letting $f(x)=x\ln{(x)}-x+\frac12\ln{(2\pi x)}$ we have that $$f(11)=17.4...$$ $$f(12)=19.9...$$ $$f(13)=22.5...$$ $$f(14)=25.1...$$ $$f(15)=27.8...$$ So the values of $n$ for which this is valid are $12,13$ and $14$.

$\endgroup$
  • $\begingroup$ Thanks for your answer. I suspect that the authors of this handbook did not intented to use this approximation (book has as audience 17/18 y/o, and gives an introduction to combinatorics). I never heard of this approximation, so I still find this answer very interesting, so thanks again! $\endgroup$ – Student Apr 7 at 13:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.