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.