29
$\begingroup$

I'm trying to prove that :

$$\frac{100!}{50!\cdot2^{50}}$$

is an integer .

For the moment I did the following :

$$\frac{100!}{50!\cdot2^{50}} = \frac{51 \cdot 52 \cdots 99 \cdot 100}{2^{50}}$$

But it still doesn't quite work out .

Hints anyone ?

Thanks

$\endgroup$
  • 3
    $\begingroup$ Think the numbers of multiple of 2, multiple of 4, multiple of 8, ..., etc in {51, 52, ..., 99, 100}. $\endgroup$ – Flan Jul 7 '13 at 14:40
  • 3
    $\begingroup$ Using \displaystyle in the title is depreciated. $\endgroup$ – Sangchul Lee Jul 7 '13 at 14:42
  • 1
    $\begingroup$ If you make it dependent on $n$, then this is called a double factorial. $\endgroup$ – dtldarek Jul 8 '13 at 8:22
112
$\begingroup$

$$ \frac{(2n)!}{n! 2^{n}} = \frac{\prod\limits_{k=1}^{2n} k}{\prod\limits_{k=1}^{n} (2k)} = \prod_{k=1}^{n} (2k-1) \in \Bbb{Z}. $$

$\endgroup$
30
$\begingroup$

We have $100$ people at a dance class. How many ways are there to divide them into $50$ dance pairs of $2$ people each? (Of course we will pay no attention to gender.)

Clearly there is an integer number of ways. Let us count the ways.

We solve first a different problem. This is a tango class. How many ways are there to divide $100$ people into dance pairs, one person to be called the leader and the other the follower?

Line up the people. There are $100!$ ways to do this. Now go down the line, pairing $1$ and $2$ and calling $1$ the leader, pairing $3$ and $4$ and calling $3$ the leader, and so on.

We obtain each leader-follower division in $50!$ ways, since the groups of $2$ can be permuted. So there are $\dfrac{100!}{50!}$ ways to divide the people into $50$ leader-follower pairs to dance the tango.

Now solve the original problem. To just count the number of democratic pairs, note that interchanging the leader/follower tags produces the same pair division. So each democratic pairing gives rise to $2^{50}$ leader/follower pairings. It follows that there are $\dfrac{100!}{2^{50}\cdot 50!}$ democratic pairings.

$\endgroup$
15
$\begingroup$

Combinatorial argument:

The number of ways to arrange the digits $1,1,2,2,3,3,4,4,5,5,\ldots, 50,50$ in a row is $\frac{100!}{2^{50}}$.

This is clearly a multiple of $50!$, since we can perform any of the $50!$ permutations on the set of 50 elements.

$\endgroup$
  • $\begingroup$ nice for combinatorial argument! $\endgroup$ – anegligibleperson Jul 7 '13 at 15:10
  • $\begingroup$ It's not so clear to me. How does a permutation of 50 relate to a permutation of 100? $\endgroup$ – Mark Jul 7 '13 at 18:02
  • $\begingroup$ @Mark If you jointly permute the $1$s, $2$s, and so on ... $\endgroup$ – Hagen von Eitzen Jul 8 '13 at 14:06
6
$\begingroup$

$$100!=(1\cdot 3\cdot 5\cdots 99)\cdot (2\cdot 4\cdot 6\cdots 100),$$

$$(2\cdot 4\cdot 6\cdots 100)=2^{50}(1\cdot 2\cdot 3\cdots 50)=2^{50}50!$$

$\endgroup$
5
$\begingroup$

Prove $51\cdot 52\cdots 100$ is divisible by $2^{50}$. Hint: Count how many multiples of 2, 4, 8... there are in the former expression.

$\endgroup$
3
$\begingroup$

From here and here, we have that the highest power of a prime $p$ dividing $n!$ is given by $$\sum_{k=1}^{\infty}\left\lfloor\dfrac{n}{p^k} \right\rfloor$$ Hence, the highest power of a prime $p$ dividing $\dfrac{n!}{m!}$ is given by $$\sum_{k=1}^{\infty}\left\lfloor\dfrac{n}{p^k} \right\rfloor - \sum_{k=1}^{\infty}\left\lfloor\dfrac{m}{p^k}\right\rfloor$$

I trust you can finish it off from here.

$\endgroup$
1
$\begingroup$

for the number of multiples of $2$:

$$100 = 52 + 2(n_1 - 1)$$ $$n_1 = 25$$

for the number of multiples of $4$:

$$100 = 52 + 4(n_2 - 1)$$ $$n_2 = 13$$

for the number of multiples of $8$:

$$96 = 56 + 8(n_3 - 1)$$ $$n_3 = 6$$

for the number of multiples of $16$:

$$96 = 64 + 16(n_4 - 1)$$ $$n_4 = 3$$

for the number of multiples of $32$:

$$96 = 64 + 32(n_5 - 1)$$ $$n_5 = 2$$

for the number of multiples of $64$:

$$64 = 64 + 64(n_6 - 1)$$ $$n_6 = 1$$

To get the number of $2$'s as factors, add all the $n$'s up, which yields $50$.

This should cancel the $2^{50}$ at the denominator, and thus prove that the expression is an integer.

$\endgroup$

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.