DOC PREVIEW
MIT 6 042J - Problem Set 2

This preview shows page 1 out of 3 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 3 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 3 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Problem 1Problem 2(a)(b)Problem 3Problem 4(a)(b)Massachusetts Institute of Technology 6.042J/18.062J, Fall ’05: Mathematics for Computer Science September 21 Prof. Albert R. Meyer and Prof. Ronitt Rubinfeld revised September 20, 2005, 1388 minutes Problem Set 2 Due: September 26 Reading: Course notes on induction. Problem 1. Use induction to prove that the following inequality holds for all integers n≥ 1. 1 3 5 · · · (2n + 1) 1· ·2 4 6 · · · (2n + 2) ≥ 2n + 2 · ·Problem 2. This term in 6.042, we’re constantly trying to divide a class of n students into groups of either 4 or 5 students. (a) Let’s try to use strong induction prove that a class with n ≥ 8 students can be divided into groups of 4 or 5. Proof. The proof is by strong induction. Let P (n) be the proposition that a recitation with n students can be divided into teams of 4 or 5. First, we prove that P (n) is true for n = 8, 9, or 10 by showing how to break classes of these sizes into groups of 4 or 5 students: 8 = 4 + 4 9 = 4 + 5 10 = 5 + 5 Next, we must show that P (8), . . . , P (n) imply P (n + 1) for all n ≥ 10. Thus, we assume that P (8), . . . , P (n) are all true and show how to divide up a class of n + 1 students into groups of 4 or 5. We first form one group of 4 students. Then we can divide the remaining n − 3 students into groups of 4 or 5 by the assumption P (n − 3). This proves P (n + 1), and so the claim holds by induction. Copyright © 2005, Prof. Albert R. Meyer and Prof. Ronitt Rubinfeld.2 Problem Set 2 This proof contains a critical logical error. (In fact, the claim is false!) Identify the first sentence in the proof that does not follow and explain what went wrong. (b) Provide a correct strong induction proof that a class with n ≥ 12 students can be divided into groups of 4 or 5. Problem 3. The game of Mini-nim is defined as follows: Some positive number of sticks are placed on the ground. Two players take turns removing one, two, or three sticks. The player to remove the last one loses. Use strong induction to show that: The second player has a winning strategy if the number of sticks, equals 4k + 1 for some k ∈ N; otherwise, the first player has a winning strategy. Problem 4. Consider the following equivalent way of viewing the subset take-away game from the in-class problem on Friday, Week 2: for a fixed, finite set, A, let S initially be all the proper subsets of A. Players alternately choose a set B ∈ S and remove B and all sets that contain B from S; they then continue playing on the updated S. The player that chooses the last set in S wins. (a) Use the well-ordering property to show that, in any game, one of the players must have a winning strategy. Hint: Consider games whose initial set, S, is an arbitrary collec-tion of subsets of, A, not necessarily all the proper subsets of A. Reach a contradiction by considering a minimum size game with no winning strategy for either player. What is a useful measure of size of a game? (b) If the whole set A is a possible move in a game, explain why the 1st player must have a winning strategy.Massachusetts Institute of Technology Solutions cover sheet 6.042J/18.062J, Fall ’05: Mathematics for Computer Science September 21 Prof. Albert R. Meyer and Prof. Ronitt Rubinfeld Student’s Solutions to Problem Set 2 Your name: Due date: September 26 Submission date: Circle your TA: David Jelani Sayan Hanson Collaboration statement: Circle one of the two choices and provide all pertinent info. 1. I worked alone and only with course materials. 2. I collaborated on this assignment with: got help from:1 and referred to:2 DO NOT WRITE BELOW THIS LINE Problem Score 1 2 3 4 Total Copyright © 2005, Prof. Albert R. Meyer and Prof. Ronitt Rubinfeld. 1People other than course staff. 2Give citations to texts and material other than the Fall ’02 course


View Full Document

MIT 6 042J - Problem Set 2

Documents in this Course
Counting

Counting

55 pages

Graphs

Graphs

19 pages

Proofs

Proofs

14 pages

Proofs

Proofs

18 pages

Proofs

Proofs

18 pages

Quiz 1

Quiz 1

9 pages

Quiz 2

Quiz 2

11 pages

Load more
Download Problem Set 2
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Problem Set 2 and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Problem Set 2 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?