[pzhon]

[ QUOTE ]

Variation 2

The manager of a movie theatre announces that a free ticket will be given to the first person in line whose random number is the same as someone else who has already purchased a ticket. You can get in line at any time. The random numbers are uniformly distributed integers ranging from 1 to N. Which position in line should you take? (The answer is a formula which depends on N.)

[/ QUOTE ]
Actually, I think this might have been asked in this forum before.

Let P(k) be the probability that the first duplicate is the kth person in line.

P(k) = (N-1)(N-2)...(N-(k-2)) (k-1) / N^(k-1)

We'd like to know when P(k+1) is smaller than P(k). When this happens, we want to be the kth person in line.

P(k+1)/P(k) = (N-(k-1))k / (N (k-1))

After a little algebra, we see that this is 1 when k(k-1)=N, or when k = 1/2 + sqrt(N+1/4).

When 1/2 + sqrt(N+1/4) is an integer, it is equally good to stand in this place or the next. These are the optimal places. For example, when N=2, it is equally good to stand in place 0.5+sqrt(2.25)=2 and 3.

When 1/2 + sqrt(N+1/4) is not an integer, the optimal place is given by rounding 1/2 + sqrt(N+1/4) up to the next integer. For example, when N=365, you want position ceiling(0.5+sqrt(365.25)) = ceiling (19.61) = 20.