Lottery on Mars
On Mars, the aliens have a lottery, where the winning numbers are six distinct numbers chosen out of the first 3 6 positive integers.
Aliens can fill in lottery tickets by selecting six distinct positive integers out of the first 3 6 positive integers.
X3zt5 is an anarchist alien. His goal is to have a lottery ticket that doesn't contain any of the winning numbers. What is the minimum number of lottery tickets he should fill in, to guarantee that his goal is met?
The answer is 9.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
Can you provide an example of 9 tickets? I'm still having trouble with this one.
Log in to reply
Not as yet. There is enough information provided to tease out the example.
Big hint:
The next step is to consider the tickets that are entirely made up from the 18 numbers that appear in a single ticket. If there are
n
of them, then out of the other
9
−
n
, after removing any 2 pairs of 2 tickets with a common element, we need
5
−
n
tickets which do not intersect.
Note that by definition, it suggests a lot of pairs of tickets out of these
5
−
n
tickets will intersect, so how do we remove 2 pairs of tickets to get non-intersecting tickets?
In particular, what should
n
be?
Log in to reply
I got it now, thanks! One solution could be (1, 2, 3, 4, 5, 6), (1, 2, 3, 7, 8, 9), (4, 5, 6, 7, 8, 9), (10, 11, 12, 13, 14, 15), (10, 11, 12, 16, 17, 18), (13, 14, 15, 16, 17, 18), (19, 20, 21, 22, 23, 24), (25, 26, 27, 28, 29, 30), and (31, 32, 33, 34, 35, 36).
Log in to reply
@David Vreken – That's the one I came up with. I don't think there are any others (that are non-isomorphic). That partly explains why I'm interested in trying to generalize this problem further.
You can see how this is created by "slowly teasing out the information from what is given". Often (but not always), for such construction problems, the implied conditions will provide some guidance for what to do.
Does this approach give you an upper bound for any size? For a lottery consisting of n distinct numbers chosen out of a set of n 2 , I can get an upper bound of 3 n if n is even. For n = 6 this is not very good, compared to the actual answer!
Log in to reply
Unexpectedly, this solution does generalize to create the example. For even n ≥ 2 , we have an upper bound of n + 3 sets.
The idea is to pick n − 3 sets of mutually exclusive n elements, and use the remaining 3 n elements to do two of the "pairing of n/2 elements" (here's where " n is even" comes in). Then, to eliminate all of these sets, we need n − 3 + 4 = n + 1 numbers, but only have n numbers to cancel out with. Hence, one of these sets will survive.
I'm not certain if n + 3 is indeed the minimum. For n = 2 , 4 , 6 , this is indeed the minimum. Maybe an approach similar to the "given any 8 tickets, find 6 winning numbers that invalidates all 8 tickets" will work.
I've not thought long about the odd case, but I believe a similar "pairing of n/2 elements" will yield an upper bound of n + k . I'm guessing that k ≤ 5 .
It looks like the solution for any even ticket size n ≥ 4 with ticket space n 2 is n + 3 . Split up the n 2 numbers into n − 1 chunks: [ 1 . . . 2 3 n ] , [ 2 3 n + 1 . . . 3 n ] , [ 3 n + 1 . . . 4 n ] , [ 4 n + 1 . . . 5 n ] , . . . The first two chunks have 2 3 n elements each, and the other n − 3 have n .
Choose three tickets covering each of the two larger chunks as in David Vrecken's solution below, and then make each of the other chunks its own ticket. It would take two tickets to eliminate the three tickets covering a larger chunk. It would then take 2 ∗ 2 + ( n − 3 ) = n + 1 to eliminate every ticket. The answer, then, has to be at least n + 3 . Calvin Lin's argument for showing why 8 can't solve the problem for n = 6 also works to show why n + 2 can't solve the problem in general, so, for even n at least 4, the answer is n + 3 .
[This is not a complete solution. I loved thinking about this problem and would like to ask how we can easily generalize it to other values. This approach doesn't seem easily extendable, so I'm wondering if there's a certain deeper theory. As an example, if the lottery picked 2 winning numbers of out 4, then we will need all 6 tickets to meet the goal! What happens if the lottery picked 3 winning numbers out of 9?]
First, given any 8 tickets, we want to find 6 winning numbers that invalidates all 8 tickets.
Case 1: There is (at least) 1 number in (at least) 3 tickets. Pick that number. Pick any number from each of the remaining (at most) 5 tickets. We're done.
Case 2: No number appears in at least 3 tickets. Then, we have (at least) 12 numbers that appear in exactly 2 tickets. We can pick 1 number to eliminate 2 tickets, and then pick 1 number to eliminate another 2 tickets for a total of 4 (Why?). Pick any number form the remaining 4 tickets. We're done.
Next, we have to find 9 tickets where no 6 winning numbers invalidates all 9 tickets. The idea here is to continually find "implied conditions" and to restrict what the example must look like, so that we're not working in the space of ( 9 ( 6 3 6 ) ) possibilities. Note: This is also made slightly easier by "knowing" that the answer is 9. But otherwise, this process could also give us some insight as to why the answer is not 9.
Let's try and proceed as before, to get information about what the tickets have to look like. (Do not read on if you really want to figure this out yourself)
Step 1 - Restrict the number of tickets an integer appears in
Case 1a: There is 1 number in (at least) 4 tickets. Pick that number. Pick any number from each of the remaining (at most) 5 tickets. We're done.
Case 1b: There is 1 number in (exactly) 3 tickets. Pick that number. Then, pick 1 number that invalidates 2 tickets (Why?). Pick that. Pick any number from each of the remaining 4 tickets. We're done.
Hence, we can conclude that no number appears in (at least) 3 tickets. (Do not read on if you really want to figure this out yourself)
Step 2 - Finding an extremely restrictive condition
Case 2: Each number appears at most twice. Then, we must have (at least) 18 numbers that appear in exactly 2 tickets. We can pick 1 number to eliminate 2 tickets, and then pick 1 number to eliminate another 2 tickets for a total of 4. We have 5 tickets remaining. If any of these 5 have a common number, pick that, and then any number from each of the remaining 3 tickets and we're done.
Hence, we can conclude that after removing any 2 pairs of 2 tickets with a common element, we must have 5 tickets which do not intersect. This condition is extremely restrictive and should give you enough information to construct the example. (Do not read on if you really want to figure this out yourself)
Step 3 - Understanding the condition to create the example
Consider the tickets that are entirely made up from the 18 numbers that appear in a single ticket. If there are n of them, then out of the other 9 − n , after removing any 2 pairs of 2 tickets with a common element, we need 5 − n tickets which do not intersect.
Note that by definition, it suggests a lot of pairs of tickets out of these 5 − n tickets will intersect, so how do we remove 2 pairs of tickets to get non-intersecting tickets?