5 ms·
By analytically, do you mean by hand, or just getting the exact answer by computer? Can project euler problems often be solved by hand? For example this 500th p
by jules 12y ago
By analytically, do you mean by hand, or just getting the exact answer by computer? Can project euler problems often be solved by hand? For example this 500th problem doesn't seem very hard with a computer, but doing it by hand seems like it will take a long long time.
- jacquesm 12y agoNo, it's still by computer. But some of them I can do by hand but that's only a few so far.
- hyperbovine 12y agoThere is an elegant way to solve these types of problems analytically using a technique called Poissonization. The aspect that makes computing the correct answer difficult is the dependence among counts for the various chips. Instead imagine the the number of defects is now Poisson distributed with mean lambda. A convenient property of the Poisson distribution is its "binning" property whereby the number of defects hitting each chip as now Poisson(lambda/n) and, most important, the counts are mutually independent. From here you can compute the correct answer by a power series argument. I'll spare you the details but see http://bulletin.imstat.org/2014/02/student-puzzle-corner/ http://bulletin.imstat.org/2014/02/student-puzzle-corner/ for a worked example.
- jules 12y agoInteresting idea, but I don't quite get how that lets us compute the answer. If I understand it correctly then we need to get the coefficient of l^(10^6) of (e^-(l/20000) + (l/20000)e^-(l/20000) + (l/20000)^2/2e^-(l/20000))^20000, and I do not know how to do that. In fact that is equivalent to finding the coefficient of x^(10^6) of (1+x+x^2)^20000, and it's easy too see that directly from the original problem, so I'm also not sure what Poissonization does for us here. Perhaps I'm completely misunderstanding the technique?
- jeffhussmann 12y agoYou have flipped the roles of 20000 and 10^6 in your formulation.
- jules 12y agoYes I have, thanks.