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}$
Thus:
$E = \sum^n_{i=1} 1*P(i) = \sum^n_{i=1} \frac{1}{n} = n * \frac{1}{n} = 1$