There are 100 persons standing in a line. Each of them is asked to choose a number between 1 to 100. The first person to have a matching number of someone ahead of him in the line will win. The poor first person has no chance of winning. Which person has the maximum chance to win?
the 10th person
ReplyDeleteI guess the answer is wrong. 11th person will have the maximum chance of winning. Share your approach. Check mine and see if anything is wrong.
ReplyDeleteLet q(k) be the probability that 1st k persons lose.
then,
q(k) = 100Pk/100^k
(i.e) 1st k persons need to chose k different numbers from 100 numbers and each of them can choose any of 100.
Now, let p(k+1) be the probability that k+1th person wins
p(k+1) = q(k)*k/100
(i.e) 1st k loses and k+1th person chooses one of the k numbers chosen by the 1st k persons
Now, p(k+1) = 100Pk*k/(100^(k+1))
We need to find the max
For maximum take p(k+1)-p(k) and see where it becomes negative
p(k+1)-p(k) = C*(-k^2+k+100) where C is some number depending on k
Clearly for k = 11, p(k+1)<p(k)
Therefore, 11th person is the one with maximum chance
i used the same approach. May be i did some calculation mistake
ReplyDelete