# The probability that a person succeeds to pick the longest stick from a randomly ordered n sticks of distinct lengths following the optimal strategy?

To begin with, consider two persons(Px and Py) are playing a game. Px is the organiser of the game who has n sticks of distinct lengths and displaying them one by one to Py in a random order, with each order being equally likely. Given the fact that the lengths of sticks are not known to Py in advance. On each step, Py takes a single stick from Px. After that, he/she either picks the stick and finishes the game or discards the stick and moves on to the next stick. Note that Py can compare relative lengths of all already seen sticks.

• Note that: The answer is considered correct if the absolute or relative error does not exceed 10e-7

• Constraints: 1 <= N <= 10e5

Sample Inputs and Outputs:(n -> probability)

• 1 -> 1
• 2 -> 0.5
• 3 -> 0.5
• 10 -> 0.398690476190

Notes: In the first test, Py chooses the first stick because it is the only one stick. In the second test, it does not matter if he/she chooses the first or the second stick. The probability of choosing the longest one is 0.5. In the third example, he bypasses the first stick, because if Py chooses it the probability would be 1/3. Then if the second stick is longer than the first one he/she chooses it and if it is smaller than the first one Py moves on to the third one.

My Attempt: I noticed that this is a binomial distribution problem since there are n attempts and each attempt is independent. Using the formula for the binomial distribution, I can not find the answer for n = 10, x =1, p = 1 /10, I got 0.387420489. I am struggling to find a solution is there any misconception I did? How to approach to a solution?

• This problem is known classically as the secretary problem. That article also explains the optimal approach. Jan 10, 2021 at 21:39
• What's the context where you encountered this task? Can you credit the original source?
– D.W.
Jan 11, 2021 at 18:30
• @D.W This was a question asked in a programming contest. The context of the asked qs is a close resemblance to the original one. Also, the original source is a pdf file(not a link). Jan 11, 2021 at 22:52