Problem Set 8 Thus, there are(k)(-) hands with exactly k face cards. By the Sum Rule, there are 12\/40 12)/40 7八(0 hands with 5, 6, or 7 face cards Problem 4. The lecture notes describe a magic trick in which the audience selects 5 card from a deck, the Assistant reveals 4 of these cards in some order, and the Magician deter- mines the last card Now suppose there are two decks of cards, one with blue backs and one with green backs. As before, the audience selects 5 cards. The assistant reveals 4 of these cards in ome order. The Magician is allowed to look at both sides of these cards. The Magician must determine the suit, value, and back-color of the remaining card (a) Prove that this is possible Solution. Construct a bipartite graph with a vertex on the left for every possible set of 5 cards and a vertex on the right for every possible sequence of 4 cards. 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 there is an edge between a set of 5 cards and a sequence of 4 if the Assistant can reveal that sequence of 4 provided the audience selects that set of 5 Now the magic trick is possible if there is a matching for the vertices on the left. Specifically, thethe audience picks a set of 5 cards. Then the assistant reveals the matching sequence of 4 cards. Finally, the Magician names the remaining card in the matched se We can prove the existence of the required matching using Hall,s Theorem directly (as in the notes)or with a corollary(as in lecture) Corollary. If every vertex on the left side of a bipartite graph has degree c and every vertex on the right has degree d, then there is a matching for the left vertices ifc>d>0 Here well use the corollary. In this case, each vertex on the left has degree c=5.4 2=120, since the Assistant can reveal any one of 5 cards first, 4 cards second, 3 cards third, and 2 cards last. Each vertex on the right has degree d=104-4=100, since the fifth card can be any card in the two decks other than the four in the sequence atching for the vertices on the left exists by the corollary, and the trick car (b) Extra credit: Describe a practical way to perform this trick. (We have no solution to this problem! Problem 5. Miss McGillicuddy never goes outside without a collection of pets. In partic� �� � � �� � � �� � � �� � 4 Problem Set 8 40 Thus, there are 12 hands with exactly k face cards. By the Sum Rule, there are k 7−k 12 40 12 40 12 40 + + 5 2 6 1 7 0 hands with 5, 6, or 7 face cards. Problem 4. The lecture notes describe a magic trick in which the audience selects 5 cards from a deck, the Assistant reveals 4 of these cards in some order, and the Magician deter￾mines the last card. Now suppose there are two decks of cards, one with blue backs and one with green backs. As before, the audience selects 5 cards. The Assistant reveals 4 of these cards in some order. (The Magician is allowed to look at both sides of these cards.) The Magician must determine the suit, value, and back­color of the remaining card. (a) Prove that this is possible. Solution. Construct a bipartite graph with a vertex on the left for every possible set of 5 cards and a vertex on the right for every possible sequence of 4 cards. 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, there is an edge between a set of 5 cards and a sequence of 4 if the Assistant can reveal that sequence of 4 provided the audience selects that set of 5. Now the magic trick is possible if there is a matching for the vertices on the left. Specifically, the the audience picks a set of 5 cards. Then the Assistant reveals the matching sequence of 4 cards. Finally, the Magician names the remaining card in the matched set. We can prove the existence of the required matching using Hall’s Theorem directly (as in the notes) or with a corollary (as in lecture): Corollary. If every vertex on the left side of a bipartite graph has degree c and every vertex on the right has degree d, then there is a matching for the left vertices if c ≥ d > 0. Here we’ll use the corollary. In this case, each vertex on the left has degree c = 5·4·3· 2 = 120, since the Assistant can reveal any one of 5 cards first, 4 cards second, 3 cards third, and 2 cards last. Each vertex on the right has degree d = 104 − 4 = 100, since the fifth card can be any card in the two decks other than the four in the sequence. So a matching for the vertices on the left exists by the corollary, and the trick can be done. (b) Extra credit: Describe a practical way to perform this trick. (We have no solution to this problem!) Problem 5. Miss McGillicuddy never goes outside without a collection of pets. In partic￾ular: