(A conversation between Bill (the writer of this post) and Olivia (14-year old daughter of a friend.) All of the math involved is here.
Bill: Do you know what 10! is?
Olivia: Yes, when I turned 10 I yelled out ``I AM 10!''
Bill: I mean it in a different way. In math 10! is 10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2.
Olivia: Okay. So what?
Bill: Do you think that (10)!/5!5! is an integer?
Olivia: No but I'll try it. (She does) Well pierce my ears and call be drafty, it is!
Bill: Do you think that (100)!/50!50! is an integer?
Olivia: Fool me once shame on you, Fool me twice... uh, uh, We don't get fooled again was a great song by the Who!
Bill: Who? Never mind, I'll save a whose-on-first-type blog for another day.
Olivia: What?
Bill: He's on second, but never mind that. It turns out that (1) (100!)/50!50! is an integer, and (2) I can prove it without actually calculating it. (Bill then goes through combinatorics and shows that n!/k!(n-k)! solves a problem in combinatorics that must have an integer solution.)
Olivia: You call that a proof! That's INSANE You can't just solve a problem that must have an integer solution and turn that into a proof that the answer is an integer. Its unnatural. It is counter to the laws of God and Man!
Inspired by Olivia I came up with a LESS elegant proof that (2n)!/n!n! is always an integer. Inspired by that I also came up with a LESS elegant proof that the Catalan numbers are integers. See the link above for all proofs.
But realize- WE think it is OBVIOUS that (2n)!/n!n! is an integer (and for that matter n!/k!(n-k)! and the Catalan numbers) and we are right about that--- but there was a time when we would have reacted like Olivia.
I've seen 5th graders who were sure there must be a fraction whose square is 2 since (1) I wouldn't have asked them if there wasn't, and (2) the concept of a problem not having a solution was alien to them. In an earlier grade the concept of having a problem whose answer was negative or a fraction was alien to them.
When teaching students and daughters of friends we should be aware that what we we call obvious comes from years of exposure that they have not had.
When Olivia turns 15 will she say `I AM 15!' More accurate would be `I am 15!.'
Sorry if I am being thick, but why is x >= y a proof? I am referring to the number theoretic proof.
ReplyDeleteI showed the following.
DeleteLet p be any prime.
Let x be the highest power such that p^x divides (2n)!
Let y be the highest power such that p^y divides n!n!
Then x ≥ y.
So why does this suffice? Factor both (2n)! and n!n! into priimes.
If p^y divides n!n! then p^y divides (2n)!. Hence all of the factors
in the denom will be cancelled.
I don't understand this sentence in Section 6:
ReplyDelete"DO NOT WANT TO USE THAT 2^n DIVIDES n! SINCE IF WE USE
THAT TRICK WE MINE AS WELL HAVE USED THE PROOF IN THE LAST SECTION."
2^n does not divide n! for any value I tried (although it might be true for sufficiently large n), but I sense I'm missing something.
BTW, I like the proof in section 5. It's certainly not combinatorial, and should satisfy even your young interlocutor.
Here is what I was thinking and lets see what happened.
DeleteThe largest x such that p^x divides n! is
floor(n/p) + floor(n/p^2) + ...
so for p=2 its
floor(n/2) + floor(n/2^2) + ...
AH- I then INCORRECTLY thought that was \ge n/2 + n/2^2 +... = n
So- what is a good estimate for it? I can easily get roughly n/2.
bill g.