This article is from the Puzzles FAQ, by Chris Cole email@example.com and Matthew Daly firstname.lastname@example.org with numerous contributions by others.
There n tickets in the lottery, k winners and m allowing you to pick another
ticket. The problem is to determine the probability of winning the lottery
when you start by picking 1 (one) ticket.
A lottery has N balls in all, and you as a player can choose m numbers
on each card, and the lottery authorities then choose n balls, define
L(N,n,m,k) as the minimum number of cards you must purchase to ensure that
at least one of your cards will have at least k numbers in common with the
balls chosen in the lottery.
This relates to the problem of rolling a random number
from 1 to 17 given a 20 sided die. You simply mark the numbers 18,
19, and 20 as "roll again".
The probability of winning is, of course, k/(n-m) as for every k cases
in which you get x "draw again"'s before winning, you get n-m-k similar
cases where you get x "draw again"'s before losing. The example using
dice makes it obvious, however.
L(N,k,n,k) >= Ceiling((N-choose-k)/(n-choose-k)* (n-1-choose-k-1)/(N-1-choose-k-1)*L(N-1,k-1,n-1,k-1)) = Ceiling(N/n*L(N-1,k-1,n-1,k-1))