Toriel is planning to create a game with prize. In this game, there are N players and N boxes each containing a piece of paper with a player's name written on it. Each player has a unique name and each box contains a different name. There are at most 1000 players playing.

Then, each player takes 1 box at random such that every player gets a different box. The more players get a box containing their name, the bigger the prize is. To prepare the prize, Toriel needs your help to calculate the expected number of player to get their own name

It's a spoj problem here http://www.spoj.com/problems/BLLUCK/

i think expected number of players who would get their own name is one

As exp=1*(1/n)+1*(n-1/n)(1/n-1)+1(n-1/n)(n-2/n-1)(1/n-2) .......... which makes it one

above form is because of following argument consider second player : probability of second player getting it's own name is p(first player not selecting second player's (name) card)*p(getting it's own card from remaining cards) and this is extended to every player

The problem is it's not convincing enough ... Is this the correct expected value ? if not what is expected value and how to arrive at it...

thanks in advance


Looks convincing enough to me! The idea is certainly correct ... maybe it just needs a little more rigor in the formulas. OK, so the expected number of boxes $i$ ending up at player $i$ is:

$E = \sum^n_{i=1} 1*P(i)$

where $P(i)$ is the chance of player $i$ picking box $i$, which is the chance of all previous players not picking box $i$, and player $i$ picking box $i$ after that. As you correctly point out, player 1 not picking box $i$ has a chance of $\frac{n-1}{n}$, and after player 1 has picked something other than box $i$, the chance of player 2 picking box $i$ out of the remaining $n-1$ boxes is $\frac{n-2}{n-1}$, etc. , and after player $i-1$ has not picked box $i$ (assuming all players before did not pick box $i$ either) with a chance of $\frac{n-(i-1)}{n-(i-1)+1}$, the chance of player $i$ picking box $i$ is $\frac{1}{n-(i-1)}$. So:

$P(i) = \frac{n-1}{n} * \frac{n-2}{n-1} * ...*\frac{n-(i-1)}{n-(i-1) + 1}*\frac{1}{n-(i-1)} = \frac{1}{n}$


$E = \sum^n_{i=1} 1*P(i) = \sum^n_{i=1} \frac{1}{n} = n * \frac{1}{n} = 1$

| cite | improve this answer | |
  • $\begingroup$ thanks for the very elegant explanation $\endgroup$ – viru Nov 30 '16 at 4:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.