25th ASU 1991 Problem 4 A lottery ticket has 50 cells into which one must put a permutation of 1, 2, 3, ... , 50. Any ticket with at least one cell matching the winning permutation wins a prize. How many tickets are needed to be sure of winning a prize?
26 Solution Take the tickets: 1 2 3 ... 25 26 27 ... 50 2 3 4 ... 26 1 27 ... 50 3 4 5 ... 1 2 27 ... 50 ... 26 1 2 ... 24 25 27 ... 50 Each of the numbers 1, 2, ... , 26 occurs in each of the places 1, 2, ... , 26, but the winning ticket cannot have all these numbers in the last 24 places. So there must be at least one match. So 26 tickets suffice. Now given any 25 tickets we show that they could all fail to match the winning permutation. In other words, we construct a permutation which fails to match any of the 25 tickets in any cell. We place the numbers 1, 2, 3, ... , 50 in turn. We start by placing 1. Clearly at most 25 places are ruled out, so we can place the 1. Now suppose we have placed 1, 2, ... , a. There must be at least 25 places where a+1 is not ruled out. If any of them are still unoccupied, then we are done. If not, they must be occupied by numbers x 1 , x 2 , ... , x 25 already placed. Take any empty place. 26 numbers cannot be ruled out for it, and we know that a+1 is ruled out, so at least one of the x i is not ruled out. So we can move that x i to it and then place a+1 where the x i came from. 25th ASU 1991 © John Scholes jscholes@kalva.demon.co.uk 13 March 2004 Last corrected/updated 13 Mar 04