Review:
Vocabulary
- Mathematical induction, strong induction, well-ordering principle.
Induction and well-ordering principle proofs
For these exercises, you might find it useful to use Google Drawings (though it is not really necessary). Here is a template with a staring picture for each question. In each breakout room, as before, have one person make a copy of this template, and share a link with edit permissions to this copy with the rest of the room via chat.
Exercise 1: Pie fights
Imagine $n\geq 2$ people standing in a field, each holding a pie. At a signal, everybody throws a pie into their nearest neighbour (assume that distances between each pair of people are all different, so in particular everybody has one nearest neighbour).
- Draw examples of such arrangments with 5 and 6 people, and determine who throws pie into whom in each example. Hint: think of drawing a graph of the relation "nearest" on the set of people, where distances are (roughly) the distances between vertices in your drawing.
- Prove using well-ordering principle that there is at least one pair of people who throw pies at each other (out of $n\geq 2$ people overall). Hint: think of enumerating distances between pairs rather than enumerating people.
- Prove by induction that if the number of people is odd, then there is always at least one person who does not get hit by a pie.
- (Bonus, if you have time after solving the next question)
Prove that if the number of people is even then for every $n$ there is a way to arrange people on the field so that everybody gets hit by a pie. Hint: assume that the field size is unlimited.
Exercise 2: Sharing chocolate
Imagine that you have a bar of chocolate which is an $s \times t$ grid of pieces ("squares"). To share it with your friends, you would like to break it up into individual squares, without ever breaking an individual square. How many steps would it take for you to do so, if at any step you can break a piece of chocolate in half horizontally or vertically? Does it depend on the order in which you break it, and if so, what is the best order?
- Try it out by cutting a 2 x 3 grid into its 6 individual squares.
Then try a 5 x 1 grid and a 3 x 3 grid. Use these expriments to figure out what might be the fastest way to do it and how many steps you need.
- Now, based on the results of your experiments, how many steps do you think you need to break an $s \times t$ grid into individual squares? Write the formula.
- Prove your answer by strong induction. Hint: since your formula does not depend on s and t separately, but rather on their product $st$, you can do induction on $n=st$.
Review
- If 3 people in a pie fight stand on the corners of a right triangle with sides 3,4,5, who will throw pie into whom? Who will survive? Now, put a 4th person at the side of length 5 a distance 0.5 from the corner of 5-side and 4-side. Who throws the pie where now? Does anyone survive? And how would it change if the 4th person were to stand on the 3-side 0.5 away from the right corner?
- How many breaks do you need to break a 10 x 2 chocolate bar into individual squares? And how many for a 6 x 5 bar?
- In all induction and strong induction proofs identify the statement $P(n)$ being proven, base case(s), induction hypothesis, induction step, and where that induction hypothesis is used in the induction step. Make sure you know the difference between strong induction and normal induction.