Magic & Math with Cards

Lecture 58 · Mathematics

Hall’s theorem explains the 124-card limit

Video in production

This lecture is still face down. Its script is written; filming and animation are under way.

Meanwhile, read the outline

What you will learn

Prove 124-card attainability using Hall’s theorem and a regular compatibility graph.

Before this lecture

In this lecture

An outline of the lecture, scene by scene, with the statements that appear on screen. It follows the draft script, so details may change in production.

  1. State existence goal and exact graph objects

    • Card labels: 124
    • Vertices per side: 225,150,024
    • Edge means visible labels belong to hand

  2. Define neighbour set and Hall bottleneck

    • N(S)=union of available messages
    • Hall condition:|N(S)|≥|S| for every S
    • Distinct neighbours, not edge multiplicity

  3. Explain why Hall condition suffices via alternating reach ability

    • Unmatched left start u
    • Augmenting path or bottleneck
    • No bottleneck→all left vertices matched

  4. Compute degree 120 on both sides

    • Hand degree=5×4!=120
    • Message degree=124−4=120
    • Both sides 120-regular

  5. Double count edges for arbitrary subset

    • 120|S| edges leave S
    • At most 120|N(S)| can enter neighbours
    • |S|≤|N(S)|

  6. Translate matching into protocol and scope optimality

    • Matching→encoder and inverse decoder
    • Maximum 124 within stated channel
    • Existence does not imply convenient lookup

  7. Specify Hall subset game and scaling tool

    • Count distinct neighbours
    • Every subset follows the same edge bound
    • Small graph for play; symbolic graph for proof

  8. Retrieve entire argument and bridge explicit code

    • Counting bound
    • Regular compatibility graph
    • Hall condition→matching→protocol

Companion interactive

Planned

Identify subset bottlenecks and explain why regularity rules them out.

The interactive for this lecture is being built and will appear here.

Notes

Written notes for this lecture will appear here.

Sources

How these sources were used
  • Norman Do, “A Mathemagical Card Trick”: Hall framework and regular-graph argument; graph labels and vertex counts corrected against exact definitions.
  • Shai Simonson and Tara S. Holm, “Using a Card Trick to Teach Discrete Mathematics”: Matching interpretation. Use Hall inequality at least, not the evident at-most typo in prose.