tag:blogger.com,1999:blog-3722233.post3271600808794839193..comments2021-05-08T03:50:47.058-05:00Comments on Computational Complexity: Less elegant proofs that (2n)!/n!n! is an integerLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-3722233.post-89535266299513791832015-02-04T08:40:04.199-06:002015-02-04T08:40:04.199-06:00Here is what I was thinking and lets see what happ...Here is what I was thinking and lets see what happened.<br />The largest x such that p^x divides n! is<br />floor(n/p) + floor(n/p^2) + ...<br />so for p=2 its<br />floor(n/2) + floor(n/2^2) + ... <br />AH- I then INCORRECTLY thought that was \ge n/2 + n/2^2 +... = n<br />So- what is a good estimate for it? I can easily get roughly n/2.<br /><br />bill g.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-88664691211025744712015-02-04T06:26:10.289-06:002015-02-04T06:26:10.289-06:00I don't understand this sentence in Section 6:...I don't understand this sentence in Section 6:<br /><br />"DO NOT WANT TO USE THAT 2^n DIVIDES n! SINCE IF WE USE<br />THAT TRICK WE MINE AS WELL HAVE USED THE PROOF IN THE LAST SECTION."<br /><br />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.<br /><br />BTW, I like the proof in section 5. It's certainly not combinatorial, and should satisfy even your young interlocutor. rwebahttps://www.blogger.com/profile/03128005962472194043noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-5283234355221637192015-02-03T22:48:31.858-06:002015-02-03T22:48:31.858-06:00I showed the following.
Let p be any prime.
Let x ...I showed the following.<br />Let p be any prime.<br />Let x be the highest power such that p^x divides (2n)!<br />Let y be the highest power such that p^y divides n!n!<br />Then x ≥ y.<br /><br />So why does this suffice? Factor both (2n)! and n!n! into priimes.<br />If p^y divides n!n! then p^y divides (2n)!. Hence all of the factors<br />in the denom will be cancelled.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-48803413800871796672015-02-03T20:28:31.526-06:002015-02-03T20:28:31.526-06:00Sorry if I am being thick, but why is x >= y a ...Sorry if I am being thick, but why is x >= y a proof? I am referring to the number theoretic proof.Anonymousnoreply@blogger.com