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

Notes for Recitation 1 (9/11/98)

1 Predicate logic

Consider the statement, “Every cloud has a silver lining”. To say this more formally, let the variable x range over a universe of discourse which is the set of all clouds and let SL(x) stand for the proposition “x has a silver lining.” Then we can write:

∀x : SL(x)

Here the symbol ∀ means “for every” or “for all”. Another way to say the same thing is to let the universe of discourse be all objects and let C be the set of clouds. Now we write:

∀x ∈ C : SL(x)

which is shorthand for

∀x : x ∈ C ⟹ SL(x).

Other examples: Let D be the set of children. Then “Every child is a boy or a girl,” can be restated as

∀x ∈ D : Boy(x) ∨ Girl(x).

The symbol ∃ means “there exists” or “there is at least one”. So, e.g., “There is always an easy way out” can be expressed:

∃x : Easy(x) ∧ Way-out(x).

These symbols, ∃ and ∀, are called quantifiers. They can be used together (and also repeatedly), e.g., “There is a tallest man” can be written as

∃x∀y : Man(x) ∧ [Man(y) ⟹ Taller(x, y).]

“Every tennis tournament has a winner” is

∀x ∈ tournaments∃y ∈ player : y wins x.

Notice that the order of the quantifiers can change the meaning of the statement. For example the above statement with quantifiers reversed is

∃y ∈ player∀x ∈ tournaments : y wins x. which means that the same person wins every tournament whereas all the earlier version meant was that each tournament has a winner, not necessarily the same person.

For proposition P, we represent “not P ” as ¬P or \overline{P}. What happens to quantifiers when they are negated? To express the fact that no element x satisfies proposition P, we write ¬∃x : P. This is the same as saying that every element does not satisfy P, written ∀x : ¬P. Similarly, ¬∀x : P is equivalent to ∃x : ¬P.

What is the negation of the statement “Every dog has its day”? We can express the negation as ¬∀x ∈ dogs : Has-a-day(x). Then using the rule above, this is the same as

∃x ∈ dogs : ¬Has-a-day(x).

In other words, there is a dog that does not have its day.

DeMorgan’s Law says that

¬(P ∧ Q) is equivalent to (\overline{P} ∨ \overline{Q}).

Using DeMorgan’s Law and the rules for negating quantifiers, we now know that

¬∀x, y∃z∀w∃v : (P ∧ \overline{Q}) ∨ ¬(P ∧ R ∧ S)

is equivalent to

∃x, y∀z∃w∀v : (\overline{P} ∨ Q) ∧ (P ∧ R ∧ S).

2 Proofs about sets

In this section we carefully prove the following identity. Below A, B, C are finite sets.

Lemma 2.1 A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C).

This is known as the distributive law of set intersection and will be useful later in the course.

Proof. Let X = A ∩ (B ∪ C) and Y = (A ∩ B) ∪ (A ∩ C). Then we will show that

1. X ⊆ Y and

2. Y ⊆ X.

This will show that X and Y must be the same set.

1. X ⊆ Y. Let x be any element of X. Then x ∈ A and x ∈ (B ∪ C). That is x is in A and also in B or in C. Let us examine these cases separately:

(a) x is in B. Then x is in A ∩ B.

(b) x is in C. Then x is in A ∩ C.

Therefore x is in A ∩ B or in A ∩ C. That is x is always an element in their union, x ∈ (A ∩ B) ∪ (A ∩ C).

2. Y ⊆ X. Let x ∈ Y, i.e., x ∈ (A ∩ B) ∪ (A ∩ C). There are two cases:

(a) x is in A ∩ B. Then x ∈ A and x ∈ B.

(b) x is in A ∩ C. Then x ∈ A and x ∈ C.

Therefore x is in A, and x is in B ∪ C That is x is in A ∩ (B ∪ C).

x ∈ X.

3 Proof by contradiction

Lemma 3.1 Let the coefficients of the polynomial a_{0}+a_{1}x+a_{2}x^{2}+…+x^{n} be integers. Then any root of the polynomial is either integral or irrational.

Proof. Let x be a root of the polynomial, that is,

a_{0} + a_{1}x + a_{2}x^{2} + … + x^{n} = 0.

There are three cases in which to classify x: it is either integral, irrational, or the ratio of two integers with no common divisors where the denominator is greater than one. We want to eliminate the last case. Assume that x = s/t for integers s and t which have no common divisors and such that t > 1. Substituting s/t for x and multiplying both sides of the above equation by t^{n} yields:

a_{0}t^{n} + a_{1}st^{n−1} + a_{2}s^{2}t^{n−2} + … + st^{n−1} + s^{n} = 0.
a_{0}t^{n} + a_{1}st^{n−1} + a_{2}s^{2}t^{n−2} + … + s^{n−1}t = −s^{n}.

Let p be a prime divisor of t. Then p divides the lefthand side of the above equation, and therefore also the righthand side, viz., −s^{n}.

Claim: If p divides −s^{n}, then p divides s.

Write s as a product of exponentiated primes p_{1}^{k_{1}}p_{2}^{k_{2}} ⋯ p_{t}^{k_{l}}.

s^{n} = p_{1}^{nk_{1}}p_{2}^{nk_{2}} ⋯ p_{t}^{nk_{l}}.

If p divides s^{n}, then p has to be equal to p_{j} for some j between 1 and l.

Therefore, p divides s.

Since we assumed s and t have no common divisors this is a contradiction.

4 Proof by cases

We have already seen proofs involving cases (e.g., the proof of the distributive law). Now we look at another problem that involves cases. The key to such proofs is to make sure that we cover all the cases.

You are given 3 identical looking balls, and told that one of them is heavier than the other two. Can you find the heavy ball using one weighing of a physical balance?

Solution. Place one ball on each pan of the balance. There are 3 possible outcomes:

1. The left pan is heavier. Then the ball in the left pan is the answer.

2. The right pan is heavier. Then the ball in the right pan is the answer.

3. The pans are equal. Then the third ball must be the heavy one!

5 Team problems

1. The Gale game^{1} 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}

1J. Daniel Christensen and Mark Tilford, “David Gale’s Subset Take-Away Game,” American Mathematical Monthly v.105 (Jan.1998)

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.

Solution: When n = 2, A = {1, 2}. The first player can only choose a singleton set consisting of one of the two elements. The second player just chooses the other one and wins.

When n = 3, the first player can have two choices: choosing a subset containing 1 element or 2 elements. Whatever the first player’s choice is, the second player simply picks the complement of the first player’s choice. For example, if the first player picks {1}, the second player will pick {2, 3}. Now, the game is then reduced to the case when n = 2, with the elements {2, 3}, since {1, 2} and {1, 3} cannot be chosen. Similarly, if the first player picks {1, 3}, the second player will pick {2}, reducing the game to n = 2 with elements {1, 3}. Therefore, Gale’s Conjecture holds for n = 2, 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.

Solution: The game will always end with a winner, because there are a finite number of legal moves in any game, and no move can be reused. Therefore the game will come to an end after a number of steps at most equal to the number of possible moves.

The set A with n elements has 2^{n} different subsets. Since choosing ∅ and A itself is not allowed in the game, there are exactly 2^{n} − 2 possible moves. So the longest possible game would have at most 2^{n} − 2 moves. It is possible to have this many moves in a game: the players could choose all the subsets of size of n − 1 first, followed by those with size of n − 2, and so on, down to subsets with size of 1. Such a sequence of moves is allowed because all the moves prior to any given move in the sequence are subsets at least as large as the given move, so none of them is contained in the given move.

The shortest possible game would last for n steps. In such a game the players always choose subsets containing one element. When all the n such sets are chosen, no more valid moves remain. It is not possible to go below n steps because the n subsets with size 1 can always be picked if they are not picked before.

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

Solution: There are three cases for the move of the first player when the game starts:

(a) The first player chooses a subset of 1 element. The second player then should choose the complement of the first player’s choice. The game then becomes the same as playing the n = 3 game on the set just chosen by the second player.

(b) The first player chooses a subset of 3 elements. The second player should choose the complement of the first player’s choice. The game then becomes the same as playing the n = 3 game on the set just chosen by the first player.

(c) The first player chooses a subset of 2 elements C_{1} = {a, b}. The second player then picks the complement of the first player’s choice, C_{2} = {c, d}. We then have the following cases:

i. If the first player choose a subset of one element contained in C_{1} or C_{2}, say, {a}, the second player can choose the subset containing only the element which remains in the same set, i.e., {b}. The game is then reduced to the case when n = 2.

ii. If the first player chooses a subset of two elements — necessarily one element from C_{1} and the other from C_{2}, say, {a, c}. The second player chooses the complement of it, {b, d}. We have two remaining possible subcases: A. If the first player chooses one of the remaining sets of size two, say {a, d}, player two should choose its complement, {b, c}. The remaining possible moves are the four sets of size 1, where the second player clearly wins after two more rounds.

B. If the first player chooses a set of 1 element in C_{1} or C_{2}, say, {a}, player two should choose the set containing only the element remaining in the set, i.e., {b}. The game is then reduced to the case when n = 2.

Therefore, player also has a winning strategy in the Gale game for n = 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?

Solution: The answer is Yes.

Step 1. Divide into groups of 4 balls. Place two of these groups on two pans.

Two possible outcomes:

(a) Equal. So the 8 balls that were weighed must be of the same weight, label them N (for “normal”) and one of the other 4 is of different weight, call them D. Step 2. Place 3 D balls on one side and 3 N balls on the other side for the second weighing. Three possible outcomes again:

i. Equal. The remaining D must be the ball of different weight. ii. DDD side is heavier. So the ball of different weight is among these

three and heavier. Now we can finish in one more weighing using the approach done in the tutorial.

iii. DDD side is lighter. Similar to previous case.

(b) Not Equal. Call the heavier side balls H and the lighter side balls L. Then there are 4 H’s , 4 L’s and 4 N’s (the 4 that we didn’t weigh are of the same weight). Step 2. Place 3 H’s and 1 L on one side and 1 H and 3 N’s on the other side for the second weighing. There are 3 possible outcomes:

i. Equal. The ball of different weight is among the remaining 3 L’s and

is lighter. We can find it in one more weighing. ii. 3 H’s , 1 L side is heavier. Then one of the three H’s must be heavier

than the rest. We can find it in one more weighing. iii. 3 H’s , 1 L side is lighter. Then either the L on this side is lighter

than the rest or the H on the other side is heavier than the rest. We can compare one of them with an N ball and find the ball of different weight!