Counting Il Each vertex on the left has degree 5.4=120, since there are five ways to select the card kept secret and there are 4! permutations of the remaining 4 cards. In terms of the marriage metaphor, every girl like 120 boys Each vertex on the right has degree 48, since there are 48 possibilities for the fifth card. Thus, every boy is liked by 48 gir Now let S be an arbitrary set of vertices on the left, which were regarding as girls. There are 120 S edges incident to vertices in this set. Since each boy is liked by at most 48 girls, this set of girls likes at least 120[S/48>SI different boys. Thus, the marriage condition is satisfied, a matching exists by Halls Theorem, and the trick can be done without magic! 4.2 The real secret You might not find the preceding answer very satisfying. After all, as a practical matter, the assistant and the magician can not memorize a matching containin 2,598,960 edges! The remaining challenge is to choose a matching that can be readily the fly. We'll describe one approach. As an running example, suppose that the audience Q命J◇ The assistant picks out two cards of the same suit. In the example the assistant ht ch The Assistant locates the values of these two cards on the cycle shown belor A 2 3 10 For any two distinct values on this cycle one is always between 1 and 6 hops clock wise from the other. For example, the 3V is 6 hops clockwise from the 10V The more counterclockwise of these two cards is revealed first, and the other be comes the secret card. Thus, in our example the 109 would be revealed and the 39 would be the secret card. Therefore The suit of the secret card is the same as the suit of the first card revealed� � Counting III 11 • Each vertex on the left has degree 5 4! = 120 · , since there are five ways to select the card kept secret and there are 4! permutations of the remaining 4 cards. In terms of the marriage metaphor, every girl like 120 boys. • Each vertex on the right has degree 48, since there are 48 possibilities for the fifth card. Thus, every boy is liked by 48 girls. Now let S be an arbitrary set of vertices on the left, which we’re regarding as girls. There are 120 |S| edges incident to vertices in this set. Since each boy is liked by at most 48 girls, this set of girls likes at least 120 |S /| 48 ≥ | | S different boys. Thus, the marriage condition is satisfied, a matching exists by Hall’s Theorem, and the trick can be done without magic! 4.2 The Real Secret You might not find the preceding answer very satisfying. After all, as a practical matter, the Assistant and the Magician can not memorize a matching containing 52 = 2, 598, 960 5 edges! The remaining challenge is to choose a matching that can be readily computed on the fly. We’ll describe one approach. As an running example, suppose that the audience selects: 10♥ 9♦ 3♥ Q♠ J♦ • The Assistant picks out two cards of the same suit. In the example, the assistant might choose the 3♥ and 10♥. • The Assistant locates the values of these two cards on the cycle shown below: A K 2 Q 3 J 4 10 5 9 6 8 7 For any two distinct values on this cycle, one is always between 1 and 6 hops clock￾wise from the other. For example, the 3♥ is 6 hops clockwise from the 10♥. • The more counterclockwise of these two cards is revealed first, and the other be￾comes the secret card. Thus, in our example, the 10♥ would be revealed, and the 3♥ would be the secret card. Therefore: – The suit of the secret card is the same as the suit of the first card revealed