Problem 285 of Project Euler was released yesterday; it requires some geometry and probability sense.
The problem goes like this:
Albert chooses two real numbers a and b randomly between 0 and 1, and a positive integer k.
He plays a game with the following formula:
The result k’ is rounded to the nearest integer. If k’ rounded is equal to k, then Albert gets k points. Otherwise, he gets nothing.
Find the expected value of the total score if Albert plays this game with .
For example (from the problem statement), let k=6, a=0.2, and b=0.85.
Here the expression gives the number 6.484. When rounded to the nearest integer, it becomes 6, which is equal to k. Therefore, Albert gets 6 points.
Yup – another expected value problem. But the concept of this problem is simple:
For any value of k, there are certain values of a and b where Albert will get points. Otherwise, he does not get points. Here the gray blob is the area where he does get points, and the white area is where he does not.
The red square is the sample space of the random variables a and b, since and .
The probability of Albert getting the points is the fraction of the square that’s gray.
The area of the red square is always 1. The area of the gray area varies with k. Thus the idea is to calculate the area of the gray area for each value of k from 1 to .
Now we can get to the details of the problem.
Notice that if , then (the difference between less-equal and less is irrelevant in this problem):
In a similar way, the equation of the larger circle is .
These are equations of circles. A circle has the equation where is the center and r is the radius.
Thus both the smaller and the larger circles have a center at . The radii of the circles are different: the radius of the smaller circle is and the radius of the larger circle .
Plotting the inequalities:
We can see now that this is a calculus problem! Indeed, the shaded area is the area of the larger circle inside the box – area of the smaller circle inside the box.
Initially I tried integrating the circles directly, but I ran into problems while integrating and I was unable to correctly integrate the equation. Instead, I integrated an equivalent problem:
It’s obvious that the areas do not change with this transformation.
So now for the smaller circle the equation is . Solving for b, we get:
.. And this equation for the larger circle:
The variable of integration here is a, and k is only a constant. Therefore we can replace the radius with r and get this equation to integrate:
With the help of an integration table, this can be integrated fairly easily.
There’s one additional problem – computing the integrating ‘limits’ of the two circles. Let’s call them and for small and large respectively.
Both of them can be computed using the pythagorean theorem.
The formula for (it should be obvious by now what should be):
Now we can get this really big formula for computing the area for any integer k:
Also, fortunately for me, it is impossible for the upper bound to cross the circle at the top or right, I mean, we never have something like this –
Anyways, here’s a Haskell implementation of the algorithm:
integral a r k = 0.5 * (a * sqrt (r^2 - a^2) + r^2 * atan (a/sqrt (r^2-a^2))) - a/k area k = let area_1 1 = 0 area_1 k = integral (sqrt (((k-0.5)/k)^2 - (1/k)^2)) ((k-0.5)/k) k - integral (1/k) ((k-0.5)/k) k area_2 k = integral (sqrt (((k+0.5)/k)^2 - (1/k)^2)) ((k+0.5)/k) k - integral (1/k) ((k+0.5)/k) k in area_2 k - area_1 k main = print . sum . zipWith (*) [1..] $ map area [1..10^5]
The code runs in about 3 seconds.
There seems to be an edge case where k=1 (probably an asymptote) so I have to specially make it be zero.
This problem was released 10 pm last night and I was tired, lol, but I still managed to solve it and get into the top 20.