The Math Lotto

The "Math Lotto" betting card is a 6×6 table. The gambler is to mark 6 of the 36 slots in the card. The official result is published with 6 slots chosen as the "LOSING SLOTS". The gambler wins if he doesn't pick any losing slot.

1. Prove that it is possible to fill out 9 betting cards so that at least one of them is a winner. Describe the markings on the 9 cards.
2. Prove that 8 cards are not sufficient to ensure a win.

Solution

1. Assume each betting card consists of a 6-element subset of {1, 2, ..., 36}. Fill out 9 cards as follows:

C1 = {1, 2, 3, 4, 5, 6}
C2 = {4, 5, 6, 7, 8, 9}
C3 = {1, 2, 3, 7, 8, 9}
C4 = {10, 11, 12, 13, 14, 15}
C5 = {16, 17, 18, 19, 20, 21}

C6 = {22, 23, 24, 25, 26, 27}
C7 = {25, 26, 27, 28, 29, 30}
C8 = {22, 23, 24, 28, 29, 30}

C9 = {31, 32, 33, 34, 35, 36}

Form the sets:

A = C1 ∪ C2 ∪ C3 ∪ C4 ∪ C5
B = C6 ∪ C7 ∪ C8

Let T be any 6-subset of {1, 2, ..., 36}.

If T meets A in at most 3 elements or B in at most 1 element, then one of the cards in A or B is disjoint from T. If T meets A in 4 or more elements and B in 2 or more elements, then T meets A in exactly 4 and B in exactly 2 elements. Hence T is disjoint from C9.

Conclusion: one of these 9 cards is a winner.

2. Let A1, ..., A8 be any 8 6-subsets. If an element x appears in three of the Ai, then choose x and one element each from the remaining five sets, making a 6-element set meeting each Ai. Thus none of the Ai is a guaranteed winner. Otherwise, no element appears in more than two Ai. We count the ordered pairs (Ai, x), x in {1, ..., 36} in two ways:

sum of number of elements contained in each Ai = 8×6 = 48, and
sum of number of Ai containing each x = d1 + ... + d36, di being the number of Aj containing the ith element.

We know each di is less or equal 2 from above. Hence there must be at least 12 di's equal to 2. Let x be one of those contained in two Ai, say Ai and Aj. Then |Ai ∪ Aj| ≤ 11; whence there is a y outside Ai ∪ Aj contained in two Ai's, say Ak and Al, with all four of these sets distinct. Hence x, y, and one element each from the remaining four Ai's makes a 6-subset which meets all 8 of the Ai. Thus none of the Ai is a guaranteed winner. 3. Six integers out of 10: Pigeonhole Principle
4. Pigeonhole Principle (Same sum)
5. Pigeonhole in a Matrix
6. Pigeonhole in Calendar
7. A nice puzzle modeled on the Petersen graph
8. Proizvolov's identity in a game format
9. Pigeonhole with Disjoint Intervals
10. All antichains
11. Euclid via Pigeonhole
12. Light Bulbs in a Circle (an Interactive Gizmo)
13. Seven integers under 127 and their Ratios
14. 