This is my approach for this problem, and I don't know why it's wrong.
1- Let X be the smallest power of 2 which is greater than or equal to N.
2- Let X = 2 ^ P.
3- Make P tosses to generate a random binary number consisting of P bits, let's call it I.
4- If I is less than N, so the king selects the Ith knight (0-indexed).
5- Otherwise, repeat again starting from step 3.
Now the final result should be:
F(N) = P + [(X - N) / X] * F(N)
F(N) - [(X - N) / X] * F(N) = P
F(N) * (1 - [(X - N) / X]) = P
F(N) = P / (1 - [(X - N) / X])
I'm sure this will select a knight with equal probability, but I'm not sure if it's the minimum expected number of tosses.
Is there anything wrong in my approach or is it my calculations?
For your solution (mine is the same) here is counter-example:
Regard n=10. We toss the coin 4 times to get one of 16 variants. If variant is higher than 10 but less than 16, we can use its result (1 of 5) to select one of 5 pairs of knights, after that we could toss the coin only once to choose one of them. Am I not right?
I do not know what to do with this example, but I hope that you (being far more professional sportsman than I) could find it out.
Maybe it is good idea to include one problem without solution in each round... Looking for best or fastest approximation for example...
→ That's called a Topcoder's Marathon match ...