To play the games, we need some dices, and these dices are very unusual. Maybe with eight or twelve sides.
hh plays with N friends today(including himself). They'll choose one person to be the judge. But the problem is: there is only a M-sided dice. How to pick a judge with the dice, so that everyone has equal probability of being chosen (the probability should always be 1/N)?
hh has an idea here:
1)Get x
Decide rolling the dice x times. x is the smallest integer to make Mx larger than or equal to N.
2)Players choose sequences
Each player chooses a sequence with x elements (1~M).
For example, a 6-sides dice and x equal to 3, hh will gets sequence [5 4 6]. Players' sequences should be different from each other.(such as [6 4 5] is different from [5 4 6])
3)Pick the judge
Roll the dice for x times, we can get a result sequence, if someone has the same sequence as the result, he will be the judge; otherwise, repeat 1)-3), until the judge is chosen.
It's a bigger project, hh wants know the expected number of times we will need to throw dice to determine the judge.