In a certain country, the "daily numbers" lottery works like this: you buy a $1 ticket with your choice of 3-digit number. The winning 3-digit number is announced. If you match exactly, you win $1000.

However, the draw isn't random. Instead, the winning number is always the *least popular* number chosen by ticket-buyers -- that is, the number that is on the fewest tickets.

There's one catch: if there is a "tie" for least popular number, every number in the tie counts as a winning number. For instance, if there are 1,359 tickets with number "000", 1,359 tickets with number "844", and every other number is on more than 1,359 tickets, that's a two-way tie for least popular, so there are two winning numbers. Holders of either number win the full $1000.

That means, in theory, that *every* ticket could win. For instance, if all 1,000 numbers are bought exactly 3,453 times, it's a 1000-way tie, and every ticket buyer wins $1000. (Presumably, the lottery authority has a large cash reserve to cover this possibility.)

Assume that every ticket buyer chooses his or her number randomly. Is the chance of winning less than 1 in 1000, more than 1 in 1000, or exactly 1 in 1000?

------

Solution (I hope):

Obviously, it doesn't matter in what order the tickets are bought Every ticket still has the same chance. Therefore, consider just the last, Nth, ticket.

Who is "winning" (least popular) after the (N-1)th ticket is processed? Either it's a single number, or it's tie of multiple numbers.

If it's a single number, the Nth ticket wins if and only if it's that exact number. The chance of that is 1/1000.

If it's a tie, the Nth ticket cannot possibly win: if it matches one of the tied numbers, that number is no longer tied for least popular.

So, sometimes the probability is exactly 0, and sometimes it's exactly 1/1000. So, overall, it has to be less than 1/1000.