Cláudio Buffara and William McWorter
Tue, 25 Mar 2003

The Math Lotto

Solution

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

   C₁ = {1, 2, 3, 4, 5, 6}
   C₂ = {4, 5, 6, 7, 8, 9}
   C₃ = {1, 2, 3, 7, 8, 9}
   C₄ = {10, 11, 12, 13, 14, 15}
   C₅ = {16, 17, 18, 19, 20, 21}
   
   C₆ = {22, 23, 24, 25, 26, 27}
   C₇ = {25, 26, 27, 28, 29, 30}
   C₈ = {22, 23, 24, 28, 29, 30}
   
   C₉ = {31, 32, 33, 34, 35, 36}
   

   Form the sets:

   A = C₁ ∪ C₂ ∪ C₃ ∪ C₄ ∪ C₅
   B = C₆ ∪ C₇ ∪ C₈

   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 C₉.

   Conclusion: one of these 9 cards is a winner.

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

   sum of number of elements contained in each A_i = 8×6 = 48, and
   sum of number of A_i containing each x = d₁ + ... + d₃₆, d_i being the number of A_j containing the i^th element.

   We know each d_i is less or equal 2 from above. Hence there must be at least 12 d_i's equal to 2. Let x be one of those contained in two A_i, say A_i and A_j. Then |A_i ∪ A_j| ≤ 11; whence there is a y outside A_i ∪ A_j contained in two A_i's, say A_k and A_l, with all four of these sets distinct. Hence x, y, and one element each from the remaining four A_i's makes a 6-subset which meets all 8 of the A_i. Thus none of the A_i is a guaranteed winner.

   
   

   Related material Read more...
   	Six integers out of 10: Pigeonhole Principle
   	Pigeonhole Principle (Same sum)
   	Pigeonhole in a Matrix
   	Pigeonhole in Calendar
   	A nice puzzle modeled on the Petersen graph
   	Proizvolov's identity in a game format
   	Pigeonhole with Disjoint Intervals
   	All antichains
   	Euclid via Pigeonhole
   	Light Bulbs in a Circle (an Interactive Gizmo)

   

   |Contact| |Front page| |Contents| |Up| |Store|

   Copyright © 1996-2012 Alexander Bogomolny