emneufeld@water.UUCP (Eric Neufeld) (11/29/85)
Another goof on my part! Two ways to derive the solution 42 as the number of tickets: 1: Use block design theory 2. Compute C(36,2)/C(6,2) But in order to take advantage of this minimum number, somehow, you must be able to figure out what to write on the tickets you buy. That is, there must be someway of writing the (36 choose 2 ) pairs on 42 tickets which each allow (6 choose 2) pairs, and making sure each pair appears on exactly one ticket. This turns out to be impossible, see Corollary 17.2, Section VII of Street and Wallis, "Combinatorial Theory: an introduction", or in any introudction to block design theory, what is known as the Bruck-Ryser-Chowla theorem. So you have to add a little redundancy to your tickets, that is upcoming.