Counting Ill Y=all X equences of 4 all sets of distinct cards card (8,K命,Q,29) {89,K命,Q◆,2◇,6◇} (K命,8,Q命,2◇) (K▲,89,6◇,Q命 {89,K命,Q◆,98,6◇} For example,(8%, Ka, Qa, 20, 60) is an element of X on the left. If the audience selects this set of 5 cards, then there are many different 4-card sequences on the right in set Y that the assistant could choose to reveal, including(89,K◆,Q◆,2◇),(K◆,89,Q◆,29) and(K确,8,6,Q命) Let's think about this problem in terms of graphs. Regard the elements of X and yas the vertices of a bipartite graph. Put an edge between a set of 5 cards and a sequence of 4 if every card in the sequence is also in the set. In other words, if the audience selects a set of cards, then the Assistant must reveal a sequence of cards that is adjacent in the bipartite graph. Some edges are shown in the diagram above What we need to perform the trick is a matching for the X vertices; that is, we need a subset of edges that join every vertex on the left to exactly one, distinct vertex on the right. If such a matching exists then the assistant and magician can agree one in advance Then when the audience selects a set of 5 cards the assistant reveals the correspond ng sequence of 4 cards. The Magician translates back to the correspoding set of 5 cards and names the one not already revealed For example, suppose the Assistant and Magician agree on a matching containing the two bold edges in the diagram above. If the audience selects the set 1 89, Ka, Qa, 94, 601, then the assistant reveals the corresponding sequence(Ko, 89, 60, Q). The Magician names the one card in the corresponding set not already revealed the 9 Notice that the sets must be matched with distinct sequences; if the Assistant revealed the same sequence when the audience picked the set 189, Kl, Q4, 20, 60), then the Magician would be unable to determine whether the remaining card was the 9c or 20 The only remaining question is whether a matching for the X vertices exists. This is precisely the subject of Halls Theorem. Regard the X vertices as girls, the y vertices as boys, and each edge as an indication that a girl likes a boy. Then a matching for the girls exists if and only if the marriage condition is satisfied Every subset of girls likes at least as large a set of boys Let's prove that the marriage condition holds for the magic trick graph. We'll need couple preliminary facts10 Counting III • • Y = all X = all sets of 5 cards • • • • sequences of 4 distinct cards • {8♥, K♠, Q♠, 2♦, 6♦} • • {8♥, K♠, Q♠, 9♣, 6♦}  hhhhhhhhhhhhh PPPPPP  ((((((((((((( (8♥, K♠, Q♠, 2♦) (K♠, 8♥, Q♠, 2♦) (K♠, 8♥, 6♦, Q♠) • • • • For example, {8♥, K♠, Q♠, 2♦, 6♦} is an element of X on the left. If the audience selects this set of 5 cards, then there are many different 4­card sequences on the right in set Y that the Assistant could choose to reveal, including (8♥, K♠, Q♠, 2♦), (K♠, 8♥, Q♠, 2♦), and (K♠, 8♥, 6♦, Q♠). Let’s think about this problem in terms of graphs. Regard the elements of X and Y as the vertices of a bipartite graph. Put an edge between a set of 5 cards and a sequence of 4 if every card in the sequence is also in the set. In other words, if the audience selects a set of cards, then the Assistant must reveal a sequence of cards that is adjacent in the bipartite graph. Some edges are shown in the diagram above. What we need to perform the trick is a matching for the X vertices; that is, we need a subset of edges that join every vertex on the left to exactly one, distinct vertex on the right. If such a matching exists, then the Assistant and Magician can agree one in advance. Then, when the audience selects a set of 5 cards, the Assistant reveals the corresponding sequence of 4 cards. The Magician translates back to the correspoding set of 5 cards and names the one not already revealed. For example, suppose the Assistant and Magician agree on a matching containing the two bold edges in the diagram above. If the audience selects the set {8♥, K♠, Q♠, 9♣, 6♦}, then the Assistant reveals the corresponding sequence (K♠, 8♥, 6♦, Q♠). The Magician names the one card in the corresponding set not already revealed, the 9♣. Notice that the sets must be matched with distinct sequences; if the Assistant revealed the same sequence when the audience picked the set {8♥, K♠, Q♠, 2♦, 6♦}, then the Magician would be unable to determine whether the remaining card was the 9♣ or 2♦! The only remaining question is whether a matching for the X vertices exists. This is precisely the subject of Hall’s Theorem. Regard the X vertices as girls, the Y vertices as boys, and each edge as an indication that a girl likes a boy. Then a matching for the girls exists if and only if the marriage condition is satisfied: Every subset of girls likes at least as large a set of boys. Let’s prove that the marriage condition holds for the magic trick graph. We’ll need a couple preliminary facts: