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?