CS 70 Discrete Mathematics and Probability Theory
Fall 2016 Seshia and Walrand HW 2
1. Sundry
Before you start your homework, write down your team. Who else did you work with on this
homework? List names and email addresses. (In case of hw party, you can also just describe
the group.) How did you work on this homework? Working in groups of 3-5 will earn credit
for your "Sundry" grade.
2. (5 points) Prove that 13 + 23 + 33 + · · · + n3 = (1 + 2 + 3 + · · · + n)2 for all integers n > 0.
Solution: We will do an induction on n:
• Proposition: P(n) = “13 + · · · + n3 = (1 + · · · + n)2 ”.
• Base case: P(1) is the proposition 13 = (1)2 , which is true, since 1 = 1.
• Inductive step: prove P(n) =⇒ P(n + 1) for all n > 0.
(a) The inductive hypothesis is 13 + · · · + n3 = (1 + · · · + n)2 , where n > 0.
(b) To prove: 13 + · · · + n3 + (n + 1)3 = (1 + · · · + n + (n + 1))2 .
(c) Taking the expression on the right hand side, we get
((1 + · · · + n) + (n + 1))2
= (1 + · · · + n)2 + 2(1 + · · · + n)(n + 1) + (n + 1)2
(since (x + y)2 = x2 + 2xy + y2 for all x, y)
= (13 + · · · + n3 ) + 2(1 + · · · + n)(n + 1) + (n + 1)2
(using the inductive hypothesis)
n(n + 1)
= (13 + · · · + n3 ) + 2 (n + 1) + (n + 1)2
2
(since 1 + · · · + n = n(n + 1)/2 for all n)
= 13 + · · · + n3 + (n + 1)3 (simplifying the right-hand side)
3. (10 points) A Tricky Game
(a) (10 points) CS 70 course staff invite you to play a game: Suppose there are n2 coins in
a n × n grid (n > 0), each with their heads side up. In each move, you can pick one of
the n rows or columns and flip over all of the coins in that row or column. However,
you are not allowed to re-arrange them in any other way. You have an unlimited number
of moves. If you happen to reach a configuration where there is exactly one coin with
its tails side up, you will get an extra credit. Are you able to win this game? Does that
apply to all n? Prove your answer.
CS 70, Fall 2016, HW 2 1
, Solution: When n = 1, the answer is trivial. Let’s then analyze the base case when
n = 2. We will prove the following lemma.
Lemma: The 2 × 2 puzzle is unwinnable.
Proof: Let P be the property that the number of coins in a configuration with heads side
up on the 2 × 2 grid is even. Note that P is true initially, and moreover it is not disturbed
by flipping of any row or column. Hence is a P is an invariant of the configuration. By
induction on the number of moves, P holds after any number of moves, and so we can
only reach configurations where P is true.
(In other words, we let Q(k) denote the proposition that P holds after any
sequence of k moves. The base case Q(0) holds trivially. Also, Q(k) =⇒
Q(k + 1) holds for all k ≥ 0, since every sequence of k + 1 moves can be de-
composed into a sequence of k moves followed by one more move, and if P
holds before this last move, it holds after the last move, too, since P is not dis-
turbed by flipping of any single row or column. Therefore by induction Q(k)
holds for all k ≥ 0.)
But now the configuration with exactly one coins tails side up is incompatible with P
and consequently is unreachable by any finite set of moves. Therefore the 2 × 2 puzzle
is unwinnable.
Now, we will use the lemma to prove the following theorem.
Theorem: The n × n puzzle is winnable if and only if n = 1.
Proof: We show that the puzzle is unwinnable when n ≥ 3. Suppose not, i.e., there is
some winning sequence of moves that leaves just a single coin with “tails” side up at
some location L. Consider any 2×2 sub-grid containing location L. Then we have found
a sequence of moves which takes this 2 × 2 sub-grid from the initial all-heads position
to a position containing 3 heads and 1 tail. But this is impossible, by the previous result.
Hence our assumption that there exists a winning sequence of moves must have been
impossible, which proves the theorem.
(b) (Optional) Now, suppose we change the rules: If the number of “tails” is between 1 and
n − 1, you win. Are you able to win this game? Does that apply to all n? Prove your
answer.
Solution: Similarly, when n = 1, the answer is trivial. We will prove the following
theorem:
Theorem: The game remains unwinnable for all n ≥ 2.
Proof: Consider any pair of rows of coins. Let P be the property that the two rows are
identically configured, and Q be the property that these two rows are exact inverses of
each other (i.e., each head in the first row corresponds to a tail in the second row, and
vice versa). Then (for every pair of rows) P ∨ Q is an invariant of the game, since it
holds initially and is not disturbed by any move.
Now there are only two cases: either there is some winning sequence of moves, or there
is not. In the former case, in the winning final configuration some rows must have t
tails, for some 1 ≤ t ≤ n − 1. This implies that every other row has either t or n − t tails
CS 70, Fall 2016, HW 2 2
Fall 2016 Seshia and Walrand HW 2
1. Sundry
Before you start your homework, write down your team. Who else did you work with on this
homework? List names and email addresses. (In case of hw party, you can also just describe
the group.) How did you work on this homework? Working in groups of 3-5 will earn credit
for your "Sundry" grade.
2. (5 points) Prove that 13 + 23 + 33 + · · · + n3 = (1 + 2 + 3 + · · · + n)2 for all integers n > 0.
Solution: We will do an induction on n:
• Proposition: P(n) = “13 + · · · + n3 = (1 + · · · + n)2 ”.
• Base case: P(1) is the proposition 13 = (1)2 , which is true, since 1 = 1.
• Inductive step: prove P(n) =⇒ P(n + 1) for all n > 0.
(a) The inductive hypothesis is 13 + · · · + n3 = (1 + · · · + n)2 , where n > 0.
(b) To prove: 13 + · · · + n3 + (n + 1)3 = (1 + · · · + n + (n + 1))2 .
(c) Taking the expression on the right hand side, we get
((1 + · · · + n) + (n + 1))2
= (1 + · · · + n)2 + 2(1 + · · · + n)(n + 1) + (n + 1)2
(since (x + y)2 = x2 + 2xy + y2 for all x, y)
= (13 + · · · + n3 ) + 2(1 + · · · + n)(n + 1) + (n + 1)2
(using the inductive hypothesis)
n(n + 1)
= (13 + · · · + n3 ) + 2 (n + 1) + (n + 1)2
2
(since 1 + · · · + n = n(n + 1)/2 for all n)
= 13 + · · · + n3 + (n + 1)3 (simplifying the right-hand side)
3. (10 points) A Tricky Game
(a) (10 points) CS 70 course staff invite you to play a game: Suppose there are n2 coins in
a n × n grid (n > 0), each with their heads side up. In each move, you can pick one of
the n rows or columns and flip over all of the coins in that row or column. However,
you are not allowed to re-arrange them in any other way. You have an unlimited number
of moves. If you happen to reach a configuration where there is exactly one coin with
its tails side up, you will get an extra credit. Are you able to win this game? Does that
apply to all n? Prove your answer.
CS 70, Fall 2016, HW 2 1
, Solution: When n = 1, the answer is trivial. Let’s then analyze the base case when
n = 2. We will prove the following lemma.
Lemma: The 2 × 2 puzzle is unwinnable.
Proof: Let P be the property that the number of coins in a configuration with heads side
up on the 2 × 2 grid is even. Note that P is true initially, and moreover it is not disturbed
by flipping of any row or column. Hence is a P is an invariant of the configuration. By
induction on the number of moves, P holds after any number of moves, and so we can
only reach configurations where P is true.
(In other words, we let Q(k) denote the proposition that P holds after any
sequence of k moves. The base case Q(0) holds trivially. Also, Q(k) =⇒
Q(k + 1) holds for all k ≥ 0, since every sequence of k + 1 moves can be de-
composed into a sequence of k moves followed by one more move, and if P
holds before this last move, it holds after the last move, too, since P is not dis-
turbed by flipping of any single row or column. Therefore by induction Q(k)
holds for all k ≥ 0.)
But now the configuration with exactly one coins tails side up is incompatible with P
and consequently is unreachable by any finite set of moves. Therefore the 2 × 2 puzzle
is unwinnable.
Now, we will use the lemma to prove the following theorem.
Theorem: The n × n puzzle is winnable if and only if n = 1.
Proof: We show that the puzzle is unwinnable when n ≥ 3. Suppose not, i.e., there is
some winning sequence of moves that leaves just a single coin with “tails” side up at
some location L. Consider any 2×2 sub-grid containing location L. Then we have found
a sequence of moves which takes this 2 × 2 sub-grid from the initial all-heads position
to a position containing 3 heads and 1 tail. But this is impossible, by the previous result.
Hence our assumption that there exists a winning sequence of moves must have been
impossible, which proves the theorem.
(b) (Optional) Now, suppose we change the rules: If the number of “tails” is between 1 and
n − 1, you win. Are you able to win this game? Does that apply to all n? Prove your
answer.
Solution: Similarly, when n = 1, the answer is trivial. We will prove the following
theorem:
Theorem: The game remains unwinnable for all n ≥ 2.
Proof: Consider any pair of rows of coins. Let P be the property that the two rows are
identically configured, and Q be the property that these two rows are exact inverses of
each other (i.e., each head in the first row corresponds to a tail in the second row, and
vice versa). Then (for every pair of rows) P ∨ Q is an invariant of the game, since it
holds initially and is not disturbed by any move.
Now there are only two cases: either there is some winning sequence of moves, or there
is not. In the former case, in the winning final configuration some rows must have t
tails, for some 1 ≤ t ≤ n − 1. This implies that every other row has either t or n − t tails
CS 70, Fall 2016, HW 2 2
