Math Challenge: Suppose the following lottery is conducted a large number of times?

Question

Suppose the following lottery is conducted a large number of times. There are n people (you can assume n is fairly large or you could let it be 100 or 1000 if you like) and each writes a positive integer on a piece of paper. The winner is the one who writes the smallest unique positive integer. For example, if 4 people write a 1 and 2 people write a 2 and only one person writes a 3, ther person who wrote a 3 is the winner.

So my question is, if this game is played a large number of times, which is the average of all the winning numbers.

In case you were curious, I have been prefacing some of my recent math questions with "Math Challenge:" in order to (a) signify that this is not my homework and (b) possibly add a bit of excitement =) However, unlike the previous ones, I have no idea what the answer to this is, or if there even is one, but I would be very interested in people's thoughts.

By the way, I once played this game with about 30 people and the number 2 won!

Answer 1

Let's start off with a simplified case.
4 people and they are allowed to choose numbers from 1 to 10. If there is no upper bound for the allowable choices, that greatly complicates the problem. Also it is difficult to account for strategy, so we have to assume that they pick these numbers purely at random.

The number n wins if the other 3 people choose numbers higher than n, or if more than one person chooses the same number lower than n.

P(someone chooses a number higher than n) = (10-n)/10
P(someone chooses a number lower t han n) = (n-1)/10

P(3 people choose higher than n) = [(10-n)/10]^3

P(2 people choose a specific no. lower than n AND 1 person chooses higher than n) = 3*(n-1)*(1/10)^2*(10-n)/10
where there are 3 ways of choosing the 2 people and n-1 ways of choosing the number less than n.

P(3 people choosing a specific no. lower than n)
= (n-1)*(1/10)^3

P(n wins) = ∑ of above
= [(10-n)/10]^3 + 3*(n-1)*(1/10)^2*(10-n)/10 + (n-1)*(1/10)^3

The expected value of n
= ∑ n*P(n)
= 7.2
For this simplified scenario, 7 is the expected winning number.

We can now generalize this result for the case where there are P persons who can choose from 1 to N.
P(n wins) = [(N-n)^(P-1) + (P-1)*(n-1)*(N-n) + (n-1)] / N^(P-1)
E(n) = ∑ n*P(n)
In the case of N = 100, P = 30; E(n) = 10.7
Remember that this analysis cannot account for strategy.

NOTE: There is also the possibility that no number wins, which I have not considered but is not difficult to do.

Answer 2

there are 4 things to this question:
1. There are infinite number of positive integers available.
2. even if we have the ENTIRE POPULATION OF THE EARTH participating, there is a probability that everyone comes up with a unique integer.
3. Now since we are intent on winning the lottery :) we need to find out by actual sampling and other emperical means, what integers actually will have a larger possiblilty of recurrence. This is because most people if asked to choose a positive number will usually choose a managable number like 2 or 3 or 1000 or maybe even a mil.
4. Lets try a gogol and see if we can win :)

The problem is solvable if we have a upper cap on the positive integers to be used, say 1-10 or 1-100. Also the population has to be fairly large to have accurate predective effect.

If you wish to win the lottery using predictive probability it is possible....:)

Answer 3

using the one example that you have given us,, I have come up with 10.7 or 10.5 but this still seems incorrect by your example of 30 people,, where as 30 would = 2 n so n =15 so using this as a simple curve 100 people =6.6 or round of to 7
1000 people =66.6 round off to 67
10,000 people =666.6 round of to 667
this is using the example you provided as of already having to play and being the only true numbers we have to work with .
believe it or not this is a viable equations with the hard numbers you gave me,,,