CS 70 Discrete Mathematics for CS Spring 2004 Papadimitriou/Vazirani HW 14

Due on Wednesday, May 12 at 5pm (283 Soda)

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

2. (10 pts.) Commutativity and Identity

(a) A binary operator f(x,y) is commutative if the result does not depend on the order of the arguments. State using quantifier notation the proposition that f is not commutative. (Matrix multiplication is an example of a noncommutative operator.)

(b) An identity for a binary operator is an element that, when combined with any element x, yields x itself. For example, the identity for + is 0; the identity for × is 1. For a noncommutative operator, a left-identity is an identity when it is the first argument; a right-identity is an identity when it is the second argument. State using quantifier notation the propositions that i_{L} is a left-identity for f and that i_{R} is a right-identity for f.

(c) Prove that for any i_{L} and i_{R} satisfying your definitions, it must be the case that i_{L}= i_{R}.

(d) Does your proof imply that f has exactly one identity element? If not, what have you proved?

3. (10 pts.) Optimality

(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, Spring 2004, HW 14 1