CS 70 Discrete Mathematics for CS

Fall 2004  Rao  HW 9

Due on Tuesday, December at 5:00PM (283 Soda)

1. (25 pts pts.) Countability.

(a) You are given an array of n bit strings a_{1},a_{2},...,a_{n}, each of length n. Show how to construct another bit string b of length n such that b ≠ a_{i} for all 1 ≤ i ≤ n by only looking only at n bits in the array. (Looking at the i-th bit of a_{j} counts as one.)

(b) Let X be the set of reals from 0.001 to 0.002. Show by a diagonalization argument that X is uncountable.

(c) Show that the set of perfect powers is countable. (A perfect power is an integer x which equals d^{2} where d is an integer.)

2. (25 pts pts.) Turing Machines

(a) Read Section 11.5 in Rosen. Do exercise 23 on page 782.

(b) (Extra Credit.) Do problem 24 on page 783.

3. (25 pts pts.) Chess Alice and Bob are playing a game of chess, with Alice to move first. If x_{1},...,x_{n} represents a sequence of possible moves (i.e., first Alice will make move x_{1}, then Bob will make move x_{2}, and so on), we let W (x_{1},...,x_{n}) denote the proposition that, after this sequences of moves is completed, Bob is checkmated.

(a) State using quantifier notation the proposition that Alice can force a checkmate on her second move, no matter how Bob plays.

(b) Alice has many possibilities to choose from on her first move, and wants to find one that lets her force a checkmate on her second move. State using quantifier notation the proposition that x_{1} is not such a move.

4. (25 pts pts.) Optimization

(a) Given a function o(x), we want to find x^{∗} that minimizes this function. This is an optimization problem. State the proposition that x^{∗} is the optimal solution.

(b) Suppose that we need only an approximate answer.State the proposition that x̃is within three times the optimal solution, without refering to the optimal solution x^{∗}. (I.e., you cannot use x^{∗} here.)

(c) State the proposition that x′is not within three times the optimal without refering to x^{∗}.

(d) If we need not only to minimize o(x) but also need that x satisfies some condition P(x). State the proposition that x^{∗} is the optimal solution.

CS 70, Fall 2004, HW 9 1