I couldn't solve it analytically for the life of me. So I wrote a small simulator, computed the answer to within 7 decimal places or so and then tried to figure out why that was the right answer. Then the lightbulb went on and I realized what the real answer should be and it worked.
As I wrote above, I am not very good at math, but to be able to use the computer to make your math understanding better than what it was before you started solving a problem was a huge up for me.
Can you solve that problem analytically? The straightforward answer is to set up a recurrence relation for p(k,n) and use dynamic programming, but even then it's far too laborious to compute p(20000,1000000) without a computer.
Now I can, but initially I had no idea. But the simulation can be coded up in 15 minutes or so and you'll have your first 3 decimal places in a few minutes after that. To get to 9 decimal places takes a while longer.
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.
There 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/ for a worked example.
Interesting 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?
https://projecteuler.net/problem=307
I couldn't solve it analytically for the life of me. So I wrote a small simulator, computed the answer to within 7 decimal places or so and then tried to figure out why that was the right answer. Then the lightbulb went on and I realized what the real answer should be and it worked.
As I wrote above, I am not very good at math, but to be able to use the computer to make your math understanding better than what it was before you started solving a problem was a huge up for me.