N!

Prove product of any N consecutive positive integers is divisible by N! ( N factorial).

Disproof (reductio per absurdum):

First, we need to prove the lemma that all objects are white. (Disclaimer: I did not derive this proof myself, but studied it in school.)

We begin with the sub-lemma that all horses are the same color (proof by induction). Letting P(N) be the predicate 'N horses are the same color,' we observe that P(1) is true. To prove P(N+1) assuming the truth of all of P(1), P(2), ..., P(N) we proceed as follows: arrange the N+1 horses in a row (see the work Zermelo and Fraenkel if you are in any doubt as to how this can be done), and consider all but the leftmost horse. This subset consists of N horses, and since P(N) is true they are all of the same color. In particular, the rightmost horse is the same color as its neighbor. Now consider all but the rightmost horse. Again we have a subset of N horses, necessarily all the same color, and the leftmost horse is the same color as its neighbor. Now consider the penultimate horses, the neighbors of the leftmost and rightmost. Since P(2) is true, these two horses are the same color. Thus we have the leftmost, next-to-leftmost, next-to-rightmost, and rightmost horses all the same color, and all N+1 horses are the same color. This concludes the proof of the sub-lemma.

Returning to the main lemma, we first observe that the word 'horse' in the above proof is arbitrary; any other lexical variable could have been used without affecting the form or validity of the argument. Instead of 'horse' we could have used 'x' or 'alpha.' To begin the proof of the main lemma, we change 'horse' to 'object' and find that all objects are the same color. To show that all objects are white, it suffices to demonstrate the existence of one white object

Sourav Maji schrieb:

The binomial coefficient is always an integer.

Have fun with maths textbooks

So ?? binomial coeff = N!/R!(N-R)! is an integer doesnt imply anything

SM> Prove product of any N consecutive positive integers is divisible SM> by N! ( N factorial).

Proof by induction:

Let the product of some n consecutive integers (x (x+1) (x+2) ... (x+n-1)) is divisible by n!.

We are going to prove that the product of the 'next' set of n consecutive numbers ((x+1).(x+2)...(x+n)) also is divisible by n!.

The assumption states that any number in the range (1..n) divide at least one number in the set (x, x+1,...., x+n-1). For the next set, we replace x with x+n.

Now if x divides n, so does (x+n). If x divides any integer less than n, there will be a number in the set that divides it too, because we have n consecutive numbers. That means no factor in the range (1...n) is 'lost' by removing x and adding (x+n). So, the product ((x+1).(x+2)...(x+n)) divides n!.

So, we proved the above assertion.

Now we know that the product of the first n integers (1.2.3....n) is indeed divisible by n!, because it is n! itself. Hence by induction, the theorem is proved.

Happy puzzling!

Well, if you write it as

(M+N)!/M!N!

it does ...

But I like Eric's proof better.

SM> Prove product of any N consecutive positive integers is divisible SM> by N! ( N factorial).

Sima> Proof by induction:

In fact, there is no need to use induction.

If we consider n consecutive integers, there will be at least one integer in this set that is divisible by k for any positive integer k <= n. That means the product of these n consecutive numbers numbers is divisible by the product of integers from 1 to n, which is n!.

Happy Puzzling!

Sima Nehru schrieb:

12 is divisible by k for any positive integer k <= 4. By your reasoning, 12 is divisible by 4!.

Have fun with easy answers

Well, I don't know.

How about this scenario: Say '12' is part of this group of 'n' numbers. It is divisible by 4. It is also divisible by 6 (and for that matter by 3 and 2 as well). However, it certainly is not divisible by 4*6 (and not by 4*6*3*2, of course). So, if you 'allocate' 12 (out of the 'n' numbers) to 6, then you have to find other numbers for 4, 3 and 2. What's the guarantee that such other numbers will not already be 'taken' by other such divisors (i.e., by another one of the 'k', in your explanation). Maybe it's possible to prove that such a situation cannot arise, and that all the 'k' divisors will be satisified. But it's not intuitive.

I like the induction method, though.

N! = 1*2*3*...*(N-1)*N

In a product of N consecutive positive integers one of the numbers must be divisible by N because if we observe mods we must have all the positive integers between 0 and N-1 and since there are N consecutive integers we will have those mods aligned in a row. So, no repetitions of mods and one of which is 0. We go by same analogy for N-1, N-2, ..., 1. Therefore product of N consecutive positive integers is divisible by N!.

MM> Sima Nehru schrieb: >> >>>>> 'Sima'