Massachusetts Institute of Technology Handout ?? 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}?

(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?

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

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

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.

(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.

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.