## riddles on Egyptian fractions and Bernoulli factories

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

$p=\frac{3-\sqrt{3(4\sqrt{9}-6)}}{6}$

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⁻¹⁵.

### 3 Responses to “riddles on Egyptian fractions and Bernoulli factories”

1. Luis Mendo Tomás Says:

Actually, the following code is better, as it only uses integer numbers, so there are no floating.point issues: https://tio.run/##y00syfn/36rE0DDCr1wtKjfCo1JRv9jD1TZS8/9/IxMA.

2. Luis Mendo Tomás Says:

For the first riddle, the solution with 1/24 as smallest fraction is optimal. I tested by brute force that there are no solutions with all denominators less than 24. I used this code (but it’s a little cryptic). Empty output means there is no solution: https://tio.run/##y00syfn/38rQMMLPsFJRv9jINlLz/38jEwA

3. nagasuri bala venkateswarlu Says:

Very good riddles.

This site uses Akismet to reduce spam. Learn how your comment data is processed.