# 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... –  Jyrki Lahtonen Sep 27 '11 at 6:14

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! –  Mathemagician1234 Sep 27 '11 at 6:39

$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. –  Mathemagician1234 Sep 27 '11 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 '11 at 6:51

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.

-

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? –  JavaMan Sep 27 '11 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. –  Bill Dubuque Sep 27 '11 at 16:48
Neat. I knew there was a reason. –  JavaMan Sep 27 '11 at 17:04

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

-

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 –  GEdgar Sep 27 '11 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à" :) –  Briguy37 Sep 27 '11 at 19:56
It is interesting to look up the definition of "wallah" some time. –  GEdgar Sep 28 '11 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.