Q & A: A little puzzle
I had a dream last night involving — (?) well I am not really sure, except that it left me wondering if there is a simple proof (if indeed it is true) that there must be a common factor of
m choose i = m!/(i! (m-i)!)
m choose j = m!/(j! (m-j)!)
for all counting numbers i,j,m with 1 < i,j < m Another way to state this same thing is: any pair of entries, on any row of Pascal's triangle (except for the 1's on the edges) will have a common factor. With facts of this sort, often there is a clever way to cast things in terms of counting something a couple of different ways which makes things clear.
The Math Factor in iTunes
RSS feed
Comments RSS
mathbun.com
jlundell said,
January 1, 2008 at 12:20 pm
It’s trivially true if m is prime, is it not? I don’t quite see how that helps the general case, though.
Eric said,
January 2, 2008 at 10:48 am
The question gets particularly interesting at m=12, where each pair of entries has a common factor, but the row as a whole has no common factor:
12 choose 1 = 12 = 2*2*3
12 choose 3 = 220 = 2*2*5*11
12 choose 4 = 495 = 3*3*5*11
strauss said,
January 2, 2008 at 11:50 am
Hi, does this already happen with m=6?
6 choose 1 = 6 = 2*3
6 choose 2 = 15 = 3*5
6 choose 3 = 20 = 2*2*5
Each pair has a common factor but the three as a whole do not.
Same with m = 10
10 choose 1 = 10
10 choose 2 = 45
10 choose 5 = 252 = 2^2* 3^2* 7
Eric said,
January 3, 2008 at 4:05 pm
Well yes, it does. For some reason the earlier entries didn’t catch my eye.
stevestyle said,
January 6, 2008 at 1:56 am
I believe I have an intuitive proof; you can judge how intuitive it is.
I will use an example with m = 6, i = 2 and j = 3.
I will use the notation mCi to mean the number of ways of choosing i objects from m objects, so mCi = m!/i!(m-i)!
Suppose we have a bag of m balls. Each ball is labelled with a number; 1, 2, 3 up to m.
First we choose i balls. There are mCi ways of doing this.
In our example we have fifteen ways:
1 1 1 1 1 2 2 2 2 3 3 3 4 4 5
2 3 4 5 6 3 4 5 6 4 5 6 5 6 6
The bag now contains the remaining m-i balls. From these we choose another j-i balls to give us j balls in total. We are choosing j-i balls from m-i balls so we have (m-i)C(j-i) choices.
We can group these choices into mCi groups of (m-i)C(j-i).
In our example we have a total of 15 groups of 4 = 60 choices:
1 1 1 1 1 1 1 1 . . . 5 5 5 5
2 2 2 2 3 3 3 3 . . . 6 6 6 6
3 4 5 6 2 4 5 6 . . . 1 2 3 4
We can get to the set 1 2 3 in three different ways. We can choose our first set to be 1 2 and then add 3, we can choose 1 3 and then add 2 or we can choose 2 3 and then add 1.
We can reorder our 60 choices as 20 groups of 3.
1 1 2 1 1 2 1 1 2 . . . 4 4 5
2 3 3 2 4 4 2 5 5 . . . 5 6 6
3 2 1 4 2 1 5 2 1 . . . 6 5 4
In general we have mCj groups of jCi.
This gives mCi x (m-i)C(j-i) = mCj x jCi. In our example 6C2 x 4C1 = 6C3 x 3C2 or 15 x 4 = 20 x 3.
In particular mCi divides mCj x jCi.
However there are more ways to choose i balls from m balls than there are to choose i balls from j balls, so mCi > jCi.
Therefore mCi and mCj have a common factor.
The common factor is a multiple of mCi/jCi. In our example this is 5, which is exactly the common multiple.
I hope all of that is clear and correct.
Chaim, is this enough for a doctorate or do I need to flesh it out a bit first?
Cheers,
Steve
strauss said,
January 6, 2008 at 11:23 am
This is correct! But I’m afraid not quite enough for a doctorate!
I asked Stan Wagon about this problem last week; he tells me that this observation was first made only in the 1970’s, by Szekeres and (the great) Erdos. (Surprisingly late) Their proof is just exactly the one you give!
(Also, you can verify that mCi * (m-i)C(j-i) = mCj * jCi directly from the definition of choose; and as you say, since mCi > jCi, we must have a common factor of mCi and mCj)
Stan also gave me a formula for working out what the gcd actually is:
Let g be the greatest common divisor of m!/j! and (m-i)!/(j-i)!
Then the greatest common divisor of mCi and mCj works out to be (m!/j!) * (1/g)
(Stan runs The Problem of the Week, an excellent source of interesting problems suitable for math undergrads on up)