Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
Given this equation:
$$ \frac{(n - 10)(n - 9)(n - 8)\times\ldots\times(n - 2)(n - 1)n}{11!} = 12376 $$
How would I find $n$?
I already know the answer to this, all thanks toWolfram|Alpha, but just knowing the answer isn't good enough for me. I want to know on how I would go about figuring out the answer without having to multiply each term, then using algebra to figure out the answer.
I was hoping that there might be a more clever way of doing this.
$12376=2^3\cdot 7\cdot 13\cdot 17$, so $17$ divides $(n-10)\cdots (n-1)n$. Let's start with $n=17$ :)
Edit. Also note that no primes larger than 17 (eg. 19, 23, 29, ...) divide $(n-10)\cdots (n-1)n$.
HINT $\rm\displaystyle\ \ 12376\ =\ \binom{n}{11}\ =\ \frac{12}{1}\ \frac{13}{2}\ \frac{14}{3}\: \cdots\: \frac{n}{n-11}\ $ so moving fractions to the LHS yields
$$\displaystyle\quad 12376\bigg)\frac{1}{12} = \frac{3094}3\bigg) \frac{2}{13} = \frac{476}3\bigg)\frac{3}{14} = \frac{34}1\bigg)\frac{4}{15} = \frac{136}{15}\bigg)\frac{5}{16} = \frac{17}6\bigg)\frac{6}{17}\ =\ 1 $$
Hence we conclude $\rm\ n = 17\:.$
The equation implies $$n\cdots(n-10) = 12376 \cdot 11!. $$ Estimating the LHS, $$ (n-10)^{11} \leq 12376 \cdot 11! \leq n^{11}. $$ This gives you the value of $n$ up to $11$ values, and you can use binary search to find the correct $n$. Perhaps you could use divisibility properties, but it isn't worth the trouble here.
Using @pharmine's factorization, we have
$$\begin{eqnarray*} n(n-1)(n-2)\cdots(n-10) &=& 17\cdot 13 \cdot 7 \cdot 2^3 \cdot 11! \\ &=& 17\cdot 13 \cdot 7 \cdot 2^3 \cdot 11 \cdot 10 \cdot 9 \cdot 8 \cdot 7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2 \end{eqnarray*}$$
Now, $17$ divides the LHS, so LHS consists of eleven consecutive integers including a multiple of $17$; given the size of the product, that multiple is likely "$17$" itself. The prime $19$ isn't a factor, so the consecutive integers are either "$18$" through "$8$" (that is, $n=18$), or "$17$" through "$7$" ($n=17$). In either case, the list of integers contains "$17$" through "$8$"; constructing these uses up the RHS factors:
$$(17)\cdot 13 \cdot 7 \cdot 2^3 \cdot 11 \cdot 10 \cdot 9 \cdot 8 \cdot 7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2$$ $$(17\cdot 16)\cdot 13 \cdot 7 \cdot 2^3 \cdot 11 \cdot 10 \cdot 9 \cdot 7\cdot 6\cdot 5\cdot 4\cdot 3$$ $$(17\cdot 16 \cdot 15)\cdot 13 \cdot 7 \cdot 2^3 \cdot 11 \cdot 10 \cdot 9 \cdot 7\cdot 6\cdot 4$$ $$\cdots$$ $$(17\cdot 16 \cdot 15 \cdot 14\cdot 13\cdot 12\cdot 11\cdot 10\cdot 9\cdot 8) \cdot 7$$
... and we conclude that $n=17$.
The lefthand side of the equation is ${n \choose 11}$, where ${n \choose k}$ (read "$n$ choose $k$") is a binomial coefficient (see also here). Since this grows fairly quickly in $n$, you can just start plugging in values.
First, it is clear that n is greater than 11 for a solution in this case (11 would yield 1 and negative n's would yield negative results). Now, let's try to get an approximation of n by assuming it is an integer (this won't work if n was less than 11):
$$ \frac{(n - 10)(n - 9)(n - 8)\times\ldots\times(n - 2)(n - 1)n}{11!} = \frac{n!}{11!\times(n-11)!} = 12376 $$
At this point, we have a relatively quick way to check integer solutions, and thus approximate decimal solutions if needed. For most of us nothing immediately stands as to how to solve this by algebra, so we plug in few guesses to get an approximation of what our answer will be:
$$ n=12: \frac{12!}{11!\times(12-11)!} = 12 $$
$$ n=15: \frac{15!}{11!\times(15-11)!} = 1365 $$
$$ n=17: \frac{17!}{11!\times(17-11)!} = 12376 $$
And voilà, 17 is our answer! We need not go further!
$n(n-1)\cdots(n-10)/11! = 2^3 \cdot 7 \cdot 13 \cdot 17$. It's not hard to see that $11! = 2^8 3^3 5^2 7^1 11^1$; this is apparently known as de Polignac's formula although I didn't know the name. Therefore
$n(n-1) \cdots (n-10) = 2^{11} 3^3 5^2 7^2 11^1 13^1 17^1$.
In particular 17 appears in the factorization but 19 does not. So $17 \le n < 19$. By checking the exponent of $7$ we see that $n = 17$ (so we have (17)(16)\cdots (7), which includes 7 and 14) not $n = 18$.
Alternatively, there's an analytic solution. Note that $n(n-1) \cdots (n-10) < (n-5)^{11}$ but that the two sides are fairly close together. This is because $(n-a)(n-(10-a)) < (n-5)^2$. So we have $$ n(n-1) \cdots (n-10)/11! = 12376 $$ and using the inequality we get $$ (n-5)^{11}/11! > 12376 $$ where we expect the two sides to be reasonably close. Solving for $n$ gives $$ n > (12376 \times 11!)^{1/11} + 5 = 16.56.$$ Now start trying values of $n$ that are greater than 16.56; the first one is 17, the answer.
Implicit in here is the approximation $$ {n \choose k} \approx {(n-(k-1)/2)^k \over k!} $$ which comes from replacing every factor of the product $n(n-1)\cdots(n-k)$ by the middle factor.
