## Description

This article is from the Puzzles FAQ,
by Chris Cole chris@questrel.questrel.com and Matthew Daly
mwdaly@pobox.com with numerous contributions by others.

# 414 probability/lottery.p

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.

probability/lottery.s

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))

The correct way to see this is as follows: Suppose you have an

(N,k,n,k) system of cards. Look at all of the cards that contain the

number 1. They cover all ball sets that contain 1, and therefore these

cards become an (N-1,k-1,n-1,k-1) covering upon deletion of the number

1. Therefore the number 1 must appear at least L(N-1,k-1,n-1,k-1).

The same is true of all of the other numbers. There are N of them but

n appear on each card. Thus we obtain the bound.

Continue to: