Exam (elaborations)
CS 70 Fall 2016 Discrete Mathematics and Probability Theory Seshia and Walrand
- Course
- Institution
CS 70 Fall 2016 Discrete Mathematics and Probability Theory Seshia and Walrand
[Show more]
Seller
Follow
solutions
Reviews received
Content preview
CS 70 Discrete Mathematics and Probability TheoryFall 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
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller solutions. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $7.49. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
75323 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy study notes for 14 years now