# How would I solve $\frac{(n - 10)(n - 9)(n - 8)\times\ldots\times(n - 2)(n - 1)n}{11!} = 12376$ for some $n$ without brute forcing it?

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.

• Why not? Brute forcing is very effective, when you can count the number of values that you need to test with your fingers, as is the case here. If you can factor 12376, you will get a very good starting point, but that is a coincidence. Also, if your book has a largish part of Pascal's triangle printed out... Sep 27, 2011 at 6:14

$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$.

• That was how I thought to approach it.It's still kind of tedious trial and error,but it gives you a logical starting point that shouldn't take a ridiculous amount of computation to solve. Sep 27, 2011 at 6:43
• So n must be at least 17. From Yuval Filmus' answer, we have that n must be under 22. As you note, n cannot be 19. So, it must be 17 or 18. 12376 is not divisible by 3, so the power of 3 in the numerator on the left must be the same as the power of 3 in 11!, which is 4. It's then easy to check that n=17 works, and n=18 has too many 3's. (You can also rule out 18 by considering powers of 7. You need two 7's in the numerator, and n=18 only gives one).
– tzs
Sep 27, 2011 at 6:51

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\:.$

• +1 for its simplicity. But, why the strage notation for multiplication? Sep 27, 2011 at 16:06
• @DJC It omits 6 implicit left-paren's at the start. It's an equational analog of similar Horner form notation. It permits efficient display of computation of cumulative products. Sep 27, 2011 at 16:48
• Neat. I knew there was a reason. Sep 27, 2011 at 17:04

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.

• Combinatorics makes me feel like an idiot.I feel like an even bigger idiot for not thinking of approximation to set bounds and take it from there.Well done,sir! Sep 27, 2011 at 6:39

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!

• wallah, sometimes spelled voila Sep 27, 2011 at 19:31
• @GEdgar: Thanks, it's probably not a good habit to answer questions with "the word ignorant people use when they really meant to say voilà" :) Sep 27, 2011 at 19:56
• It is interesting to look up the definition of "wallah" some time. Sep 28, 2011 at 0:29

$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.