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

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.


    Related material
    Read more...

  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. |Contact| |Front page| |Contents| |Up|

    Copyright © 1996-2018 Alexander Bogomolny

72193032