Massachusetts Institute of Technology Handout 5 6.042J/18.062J: Mathematics for Computer Science September 10, 1998 Professors Nancy Lynch and Srini Devadas

Problems for Recitation 1

1. The Gale game is played on a finite set, A, of size two or more, e.g., A might be the set of integers from 1 to n ≥ 2. Two players alternate moves. A move is a choice of a nonempty proper subset (that is, a nonempty subset of A other than A itself), subject to the constraint that no subset may be chosen which contains a previously chosen subset. The player who first gets stuck without an allowed move loses.

For example, when A = {1, 2, 3, 4}, the moves might be:

\begin{matrix}player : & 1 & 2 & 1 & 2 & 1 & 2 & 1 & 2 \\ move : & \{1, 2\} & \{3, 4\} & \{1, 3\} & \{2, 4\} & \{1\} & \{2\} & \{3\} & \{4\} \end{matrix}

At this point, the first player has no valid move and therefore loses.

Gale’s Conjecture is that the second player can always win. Note that this does not mean that the second player will win every game. He can lose if he plays stupidly, but there always is a way for the second to win no matter what moves the first player makes. (This is like the situation in tic-tac-toe, where the first player can lose by playing stupidly, but has a simple strategy which guarantees that he will never lose.)

(a) Prove Gale’s Conjecture for the games with n = 2 and 3.

(b) Must every Gale game end with a winner (remember, chess games don’t)? What is the length of the longest, and shortest, possible games on {1, …, n}? Explain.

(c) Try to prove Gale’s Conjecture for n = 4. Hint: you will be overwhelmed with cases if you don’t identify ”symmetric” cases. For example, if player 1’s first move is {1, 2, 3}, and you work out how player 2 will win, then you can adapt your strategy to work against any first move consisting of a set of size three, by permuting the roles of 1, 2, 3, and 4.

2. You are given 12 identical looking balls, and told that one of them is of different weight from the other 11, but you don’t know in advance whether it is heavier or lighter. Can you find the ball that is of different weight using only 3 weighings?