Chapter 14 Cardinality Rules610
Hint:Hall’s Theorem and degree-constrained (11.5.5) graphs.
Problem 14.40.
The Magician can determine the 5th card in a poker hand when his Assisant reveals
the other 4 cards. Describe a similar method for determining 2 hidden cards in a
hand of 9 cards when your Assisant reveals the other 7 cards.
Homework Problems
Problem 14.41. (a)Show that any odd integerxin the range 109 < x < 2 109
containing all ten digits0;1;:::;9must have consecutive even digits.Hint:What
can you conclude about the parities of the first and last digit?
(b)Show that there are 2 vertices of equal degree in any finite undirected graph
withn 2 vertices.Hint:Cases conditioned upon the existence of a degree zero
vertex.
Problem 14.42.
Show that for any set of 201 positive integers less than 300, there must be two
whose quotient is a power of three (with no remainder).
Problem 14.43. (a)LetRbe an 82 4 rectangular matrix each of whose entries
are colored red, white or blue. Explain why at least two of the 82 rows inRmust
have identical color patterns.
(b)Conclude thatRcontains four points with the same color that form the corners
of a rectangle.
(c)Now show that the conclusion from part (b) holds even whenRhas only 19
rows.
Hint:How many ways are there to pick two positions in a row of length four and
color them the same?
Problem 14.44.
Section 14.8.6 explained why it is not possible to perform a four-card variant of the
hidden-card magic trick with one card hidden. But the Magician and her Assistant