Massachusetts Institute of Technology Handout 29 6.042J/18.062J: Mathematics for Computer Science March 31, 2000 Professors David Karger and Nancy Lynch

Mini-Quiz 8

1. Write your name:

2. (Rosen, Section 2.2, Problem 3) Suppose that an element happens to be among the first four elements in a list of 32 elements (but you don’t know that). Would linear search or binary search locate this element more rapidly? Explain why.

Tutorial 8 Problems

Problem 1 Let {0, 1}^{n} be the set of all bit strings of length n.

(a) How many functions are there with domain {0, 1}^{m} and codomain {0, 1}^{n}?

Solution.

There are 2^{m} elements in the domain. There are 2^{n} elements in the codomain. For every element in the domain, we thus have 2^{n} choices for what we can map it to. Therefore, by the Product Rule, there are (2^{n})^{2^{m}} possible functions with domain {0, 1}^{m} and codomain {0, 1}^{n}.

□

(b) A value x is called a fixed point of a function f if f(x) = x. How many functions from {0, 1}^{n} to {0, 1}^{n} have no fixed points?

Solution.

To count all the functions without fixed points, we observe that such a function could map each element of the domain to any element but itself, that is, to any one of the remaining 2^{n} − 1 elements in the codomain. There are 2^{n} elements in the domain, so, by Product Rule there are (2^{n} − 1)^{2^{n}} such functions with no fixed points.

□

(c) How many functions from {0, 1}^{n} to {0, 1}^{n} have at least one fixed point?

Solution.

There are (2^{n})^{2^{n}} functions, and (2^{n} − 1)^{2^{n}} have no fixed points. Therefore, the remaining (2^{n})^{2^{n}} − (2^{n} − 1)^{2^{n}} have at least one fixed point.

□

(d) How many functions from {0, 1}^{n} to {0, 1}^{n} have exactly one fixed point?

Solution.

Let’s fix a particular point for our fixed point. Now let’s consider where the remaining 2^{n} −1 points can be mapped. Each one can be mapped to any spot but itself—thus it can be mapped to exactly 2^{n} − 1 possible spots. So by the Product Rule, there are (2^{n} − 1)^{2^{n}−1} functions with exactly this particular fixed point and no other. Now there are 2^{n} possible choices for the particular fixed point, so by the Sum Rule, the total number of functions with exactly one fixed point is 2^{n}(2^{n} − 1)^{2^{n}−1}.

□

Problem 2

(a) In lecture we demonstrated how to “guess” the fifth card in a poker hand when a collaborator reveals the other four cards. Describe a method for guessing two hidden cards in a hand of nine cards, when your collaborator reveals the other seven cards.

Solution.

There must be ⌈9/4⌉ = 3 cards with the same suit, so our collaborator chooses to hide two of them and then use the third one as the first card to be revealed. So this first revealed card fixes the suit of the two hidden cards; it will also be used as the origin for the offset position of the first hidden card. This first hidden card will in turn be used as the origin for the offset of the other hidden card. There are six cards to code the two offset positions. These suffice to code two offsets of size from one to six. That is, our collaborator can choose one of the 3! = 6 orders in which to reveal the first three cards and thereby tell us the offset position of the first hidden card. Our collaborator can then choose the order of the final three cards to describe the offset position of the second hidden card from the first. Note that the first revealed card must be chosen so that both offsets are less ≤ 6; since the sum of the offsets between successive cars ordered in a cycle from Ace to King is 13, it is not possible for more than one offset between successive cards to exceed seven, so this is always possible.

□

(b) Show that there is no procedure for “guessing” a hidden card among four when your collaborator reveals three. Hint: Compare the number of hands to the number of revealed three-card sequences. Solution.

There are \binom{52}{4} possible four-card hands. There are P (52, 3) three-card sequences that can ever be revealed. Since

\frac{\binom{52}{4}}{P (52, 3)} = \frac{52 · 51 · 50 · 49/4!}{52 · 51 · 50} = 49/24 > 1,

there must, by pigeonholing, be two (actually three) hands for which the collaborator reveals the same three cards. Therefore the magician cannot determine the hidden card, since these hands must have different hidden cards.

□

Problem 3 Consider a sequence of distinct real numbers a_{1}, a_{2}, …, a_{mn+1}. Prove that there exists an increasing subsequence

a_{i_{1}} < a_{i_{2}} < ⋯ < a_{i_{m+1}} with i_{1} < i_{2} < ⋯ < i_{m+1}

or a decreasing subsequence

a_{j_{1}} > a_{j_{2}} > ⋯ > a_{j_{n+1}} with j_{1} < j_{2} < ⋯ < j_{n+1}

or both.

Solution.

Say there is no increasing subsequence of length greater than m. Then, f is a map from the numbers a_{i} to {1, …, m}. By generalized pigeonhole, there is some s such that f(a_{i}) = s for at least \frac{mn}{m} + 1 = n + 1 numbers a_{i}. Let a_{j_{1}}, a_{j_{2}}, …, a_{j_{n+1}} (with j_{1} < j_{2} < ⋯ < j_{n+1}) be this sequence.

For this sequence, a_{j_{k}} > a_{j_{k+1}} for all 1 ≤ k ≤ n; otherwise, f(a_{j_{k}}) ≥ s + 1, which contradicts our assumption.

So, if t_{i} ≥ m + 1 for some i, then we have such an increasing subsequence; otherwise, a_{j_{1}}, a_{j_{2}}, …, a_{j_{n+1}} is a decreasing subsequence of the correct length.

□