In a lottery, a person must select six distinct numbers from $1, 2, 3,\dots, 36$ to put on a ticket. The lottery commitee will then draw six distinct numbers randomly from $1, 2, 3, \ldots, 36$. Any ticket with numbers not containing any of these $6$ numbers is a winning ticket. Show that there is a scheme of buying $9$ tickets guaranteeing at least one winning ticket, but $8$ tickets are not enough to guarantee a winning ticket in general.
Problem
Source:
Tags: combinatorics unsolved, combinatorics
chera
01.01.2012 07:14
Let a1,b1,c1,a2,b2,c2 be any 6 disjoint 3 element subets of {1,2,3,.....,36}. let the remaining 18 elements be partitioned into 3 disjoint subsets d,e & f of 6 elements each choose following 9 tickets a1+b1,b1+c1,c1+a1, a2+b2,b2+c2,c2+a2, d,e, and f. where A+B stands for union of sets A and B. To cover all tickets, you need to select 2 elements from a1+b1+c1, 2 elements from a2+b2+c2 and 1 element each from d,e and f. thus you need a minimum of 7 elements to cover all the 9 tickets. For the second part, suppose there are 8 tickets A,B,C,D,E,F,G and H. there are 2 cases: case1: there is an element which is common to at least 3 tickets, say(wlog) A,B and C. in this case, just choose that common element and choose 1 element each from other 5 tickets. case2: intersection of any 3 tickets is nil. in this case, by expanding the inclusion-exclusion formula for union of sets, it is seen that there are 4 tickets (wlog) A,B, C and D such that A overlaps B, and C overlaps D. just choose two overlapping elements from A+B, and C+D, and one element each from remaining 4 tickets. therefore you can choose 6 elements to cover any given 8 tickets.
Pascal96
11.07.2012 13:37
For the second part of the problem we can use a counting argument. For any lottery ticket, there are exactly n = (30 choose 6) sets of distinct numbers that have no numbers in common with the ticket. Since there are 8 tickets, there are at most 8n sets of six numbers that are disjoint from at least one of the 8 lottery tickets. Now just use the estimate 8n < (36 choose 6) to finish. (this bound is not hard to prove by hand- a little cancellation and it's done)
Crossing0ver
27.01.2019 18:34
Quote: Pascal 96 your solution is wrong,because $ 8* \binom{30}{6} > \binom{36}{6}$
guptaamitu1
04.11.2021 12:09
To prove $8$ doesn't work, first we pick a number $\alpha$ which is common to at least $\beta \ge 2$ sets (such a $\alpha$ exists as $6 \cdot 8 = 48 > 36$). If $\beta \ge 3$, then we are just done (as we just need to cover $5$ more sets and we have $5$ numbers more to choose). Otherwise, if $\beta = 2$, then among the remaing $6$ sets two sets must have some common element as $6 \cdot 6 > 36 - 1$ ($-1$ is for the $\alpha$), and then we just pick that common element too. After that, we just that to cover $\le 4$ with $4$ numbers, which is trivial. $\blacksquare$