EECS 203: Discrete Mathematics
Fall 2024
Homework 6
Legal Assumptions
• When you are asked to prove something “by induction,” you may use either weak or strong induction. Do not use structural induction (which is a topic that we will cover a few days before this homework is due).
Definition Reminders
• An integer x is divisible by an integer m, written m| x, if there exists an integer k with x = mk.
• The degree of a node v in a graph, written deg(v), is the number of edges that contain v.
• A graph is connected if there exists a path between any two nodes.
• A clique is a graph in which every pair of vertices has an edge between them.
• The cardinality of a set S, written |S|, is the number of elements in S. Recall that sets do not have a concept of repeat elements, so for example, |{1, 1, 2, 3}| = 3.
Mechanical Problems
1. High Five! [9 points]
Prove by induction that for all positive integers n, 5n − 1 is divisible by 4. Do not assume the laws of modular arithmetic in your proof; instead, use the definition of divisibility.
2. Higher Five! [9 points]
Prove by induction that 3n + 4n ≤ 5n for all integers n ≥ 2.
3. The Fix Is In [14 points]
Let A be a set where |A| is finite and odd. Let f : A → A be a function with the property that for all a ∈ A, we have f(f(a)) = a. Prove by induction that there exists a ∈ A with f(a) = a. Be sure to explicitly state the predicate used in your induction.
4. It’s A Trap(ezoid) [14 points]
For an integer n ≥ 0, let Tn be an equilateral triangle that has been partitioned into 4n smaller congruent equilateral triangles, as in the following pictures. Prove by induction that for all integers n ≥ 0, there exists a way to cover all but one of the triangles in the partition using non-overlapping trapezoid tiles, congruent to three consecutive triangles from the partition.
The one uncovered triangle can be any triangle you choose. Be sure to explicitly state which triangle you will leave uncovered, and state the predicate used in your induction.
Bad Proofs
For each of the following propositions, we have given an incorrect “proof” that attempts to show that it is true. Identify the specific logical error made in each proof by citing a sentence, equation, step, or missing part of the argument, and briefly explain why it is wrong.
5. Missed Connection [8 points]
Proposition. Every graph with at least 2 nodes, and in which all nodes have degree ≥ 1, must be connected.
Proof. Let P(n) be the predicate “Every graph with exactly n nodes, all of which have degree ≥ 1, is connected.” We will prove ∀n ≥ 2 P(n) by induction:
Base Case: Suppose n = 2. There is only one 2-node graph in which all nodes have degree ≥ 1, which is the graph that has an edge connecting its two nodes. This graph is connected, and so P(2) holds.
Inductive Step: Let n ≥ 3 be any integer and assume the inductive hypothesis P(n − 1). Let G be a graph with exactly n − 1 nodes that all have degree ≥ 1. By the inductive hypothesis, G must be connected.
Now add any one new node v to G and one or more edges from v to other nodes in the graph. Call the new graph G′ . Note that G′ has exactly n nodes, and they all have degree ≥ 1. Additionally, since G is connected and there is an edge from v to a node in G, there is a path from v to all other nodes. So G′ is connected, and so P(n) holds.
6. Hometown Hoax 2 [8 points]
Proposition. All EECS 203 students are from the same hometown.
Proof. Let P(n) be the predicate “any set of n EECS 203 students are from the same hometown.” We will prove ∀n ≥ 1 P(n) by induction:
Base Case. For n = 1, the proposition states that any one EECS 203 student has the same hometown as themself, which is true.
Inductive Step. Let n ≥ 2 be any integer and assume P(n − 1), which states that any set of n−1 EECS 203 students all have the same hometown. To prove P(n), let S = {s1,..., sn } be any set of n EECS 203 students. Consider the subsets
Sa = {s1 , s2..., sn-1 } and Sb = {s2 , s3,..., sn } .
Since Sa has n - 1 students, by the inductive hypothesis, all students in Sa have the same hometown as each other. Since Sb has n - 1 students, also by the inductive hypothesis, all students in Sb have the same hometown as each other. Since (for example) s2 is in both Sa and Sb , that means all students in Sa have the same hometown as s2 , and all students in Sb have the same hometown as s2 . Therefore all students in Sa ∪ Sb = S have the same hometown as s2 , and so they have the same hometown as each other, proving P(n).
Discovery Problems
7. Preeti’s Pegboard Polygon Pattern Puzzle [20 points]
Preeti has a large board with pegs arranged in a repeating pattern of equilateral triangles. Preeti puts some rubber bands on the pegboard, forming triangles. After experimenting, she realizes the following rule: if the triangle has no pegs on its interior or its boundary (besides its three corner points), then the area of the triangle is always exactly 1.
Given this rule, derive a formula for the area of any polygon formed by placing a rubber band on the pegboard. Your formula may depend only on:
• x, the number of pegs on the interior of the polygon (not including its boundary), and
• y, the number of pegs on the boundary of the polygon (including its corner points).
Then prove correctness of your formula by induction. Be sure to explicitly state the predicate used in your induction.
You may assume that the sides of the polygon do not cross each other. You may also use the following geometric fact without proof: for any polygon with ≥ 4 pegs on its boundary, there exist 2 pegs on the boundary for which the line segment between them lies entirely in the interior of the polygon.
8. Clucks in a Clique [18 points]
A fact from biology is that, in any barnyard, for any pair of chickens, one is dominant over the other. The dominant chicken will occasionally peck the other one, and the other chicken will not dare to peck back. However, dominance is not necessarily transitive: it is possible that chicken A pecks chicken B, who pecks chicken C, who pecks chicken A.
(a) Despite non-transitivity, chicken psychologists have long observed that, among any group of n chickens, it is possible to line them up in a pecking order, meaning that every chicken pecks the one to its right. Express this as a proposition about graphs by filling in the blank, and briefly explain why your proposition is equivalent to the statement about pecking orders.
“Let G = (V, E) be a directed graph, which is a n-node clique with every edge directed in one of the two possible ways. Then .”
(b) This mystery of Chicken Psychology was finally solved in 1935, when it was proved that the existence of a pecking order is a mathematical certainty rather than anything special happening in chicken brains. Show this by proving your proposition about graphs for all n ≥ 1, using induction.
Grading of Groupwork 5
Using the solutions and Grading Guidelines, grade your Groupwork 5 Problems:
• Use the table below to grade your past groupwork submission and calculate scores.
• While grading, mark up your past submission. Include this with the table when you submit your grading.
• Write whether your submission achieved each rubric item. If it didn’t achieve one, say why not.
• For extra credit, write positive comment(s) about your work.
• You don’t have to redo problems correctly, but it is recommended!
• See “All About Groupwork” on Canvas for more detailed guidance, and what to do if you change groups.
|
|
(i)
|
(ii)
|
(iii)
|
(iv)
|
(v)
|
(vi)
|
(vii)
|
(viii)
|
(ix)
|
(x)
|
(xi)
|
Total:
|
|
Problem 1
|
|
|
|
|
|
|
|
|
|
|
|
/10
|
|
Problem 2
|
|
|
|
|
|
|
|
|
|
|
|
/20
|
|
Total:
|
|
|
|
|
|
|
|
|
|
|
|
/30
|
Groupwork 6 Problems
1. Pirate Election [15 points]
A group of 100 pirates has discovered buried treasure of 100 gold coins. Their Pirates’ Code dictates that they split the loot using the following method:
• The most senior pirate proposes a way to divide the coins. Coins are indivisible; that is, each pirate must receive an integer number of coins in the proposal (possibly zero).
• All pirates (including the proposer) vote on whether to accept or reject the proposal.
• If at least half of the pirates vote to accept, then the proposal passes. The gold is distributed as proposed, and the election is over.
• If strictly more than half of the pirates vote to reject, then the proposal fails, and the pirate who proposed it is forced to walk the plank. The process then repeats, with the most senior pirate remaining making the next proposal.
A pirate will vote for a proposal if they prefer it to the outcome that would occur instead of the proposal failed. They have the following priorities dictating their preferences:
(i) (Survival) A pirate will prefer any outcome where they do not walk the plank to any outcome where they do walk the plank.
(ii) (Greed) Between two outcomes where they do not walk the plank, a pirate will prefer an outcome in which they get more gold.
(iii) (Bloodthirst) Between two outcomes where they do not walk the plank and get the same amount of gold, a pirate will prefer the outcome in which more other pirates walk the plank.
All pirates are perfectly logical and aware of all these rules. How many pirates walk the plank, and what proposal will ultimately pass?
2. Continuous Induction [10 points]
For a predicate P(r) where r is a non-negative real number, we denote
P< (r) = “For all 0 ≤ s < r, we have P(s).”
P≤ (r) = “For all 0 ≤ s ≤ r, we have P(s).”
Suppose we want to prove ∀r P(r) over the domain R≥0 . The following two propositions look similar to each other, but only one of them actually implies that ∀r P(r):
|
A correct and an incorrect principle of continuous induction:
(i) P(0) and for all r ≥ 0, there exists ε > 0 such that P< (r) → P< (r + ε).
(ii) P(0) and for all r ≥ 0, there exists ε > 0 such that P≤ (r) → P≤ (r + ε).
|
(a) Show that the specific choice P(r) = [r < 203] makes one of the above two propositions true, and the other one false.
(b) Based on this, which one do you think is the correct principle of continuous induction? Briefly explain your answer (but you do not need to prove it).