This problem came up during the Google CTF 2017. For background information about the challenge you can search for `GoogleCTF A7 ~ Gee cue elle`.

Problem description:

 - A random number `N` between `0` and `39402006196394479212279040100143613805079739270465446667948293404245721771497210611414266254884915640806627990306815` (`~3.9*10^115`) is selected
 - You have to find the correct number `N`
 - You can take a guess `X`, and get a response whether the number `X` is greater or lower than `N`
 - The twist:
  - you can only perform 13 guesses in 30s without hitting a 90s timeout - `13/30`
  - if your guess was lower, then you get an error and you can only have 2 errors in 30s without a 90s timeout - `2/30`
  - you have only `2240s` time to find the correct value

I had a short discussion with the challenge creator about the solution and he solved it like the [broken egg](http://datagenetics.com/blog/july22012/index.html) problem. His algorithm basically runs in constant time - 1920s. I think the problem is not equivalent to the egg problem, but somehow the algorithm performs here really really well.

I chose a skewed binary search. Instead of splitting the search field into 50:50, I skew to one side `2/13=0.15` 15:85. This way the probability of hitting the punishing error condition is pretty unlikely. My intuition tells me, that this should be the most efficient algorithm, but apparently it's not.

1. I thought the `0.15` skew would be the best ratio, but after analysing the time it takes with different ratios, the most efficient value seems to be around `~0.22`. My calculation is obviously wrong, but what would have been the correct calculation to find `~0.22`?

[![average time in seconds for different skews][1]][1]


  [1]: https://i.sstatic.net/do9Mu.png

2. Why does the egg problem algorithm perform better (as in faster)?
3. What is the most efficient algorithm here, and why is it not based on a skewed binary search?

Any thoughts and comments are welcome.