riddles on Egyptian fractions and Bernoulli factories
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.
Two fairy different riddles on the weekend Riddler. The first one is (in fine) about Egyptian fractions: I understand the first one as
Find the Egyptian fraction decomposition of 2 into 11 distinct unit fractions that maximises the smallest fraction.
And which I cannot solve despite perusing this amazing webpage on Egyptian fractions and making some attempts at brute force random exploration. Using Fibonacci’s greedy algorithm. I managed to find such decompositions
2 = 1 +1/2 +1/6 +1/12 +1/16 +1/20 +1/24 +1/30 +1/42 +1/48 +1/56
after seeing in this short note
2 = 1 +1/3 +1/5 +1/7 +1/9 +1/42 +1/15 +1/18 +1/30 +1/45 +1/90
And then Robin came with the following:
2 = 1 +1/4 +1/5 +1/8 +1/10 +1/12 +1/15 +1/20 +1/21 +1/24 +1/28
which may prove to be the winner! But there is even better:
2 = 1 +1/5 +1/6 +1/8 +1/9 +1/10 +1/12 +1/15 +1/18 +1/20 +1/24
The second riddle is a more straightforward Bernoulli factory problem:
Given a coin with a free-to-choose probability p of head, design an experiment with a fixed number k of draws that returns three outcomes with equal probabilities.
For which I tried a brute-force search of all possible 3-partitions of the 2-to-the-k events for a range of values of p from .01 to .5 and for k equal to 3,4,… But never getting an exact balance between the three groups. Reading later the solution on the Riddler, I saw that there was an exact solution for 4 draws when
Augmenting the precision of my solver (by multiplying all terms by 100), I indeed found a difference of
> solver((3-sqrt(3*(4*sqrt(6)-9)))/6,ba=1e5)[1]
[1] 8.940697e-08
which means an error of 9 x 100⁻⁴ x 10⁻⁸, ie roughly 10⁻¹⁵.
R-bloggers.com offers daily e-mail updates about R news and tutorials about learning R and many other topics. Click here if you're looking to post or find an R/data-science job.
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.