Homework Assignment 4: Topics: Induction
Assigned, Thursday October 7 Due, Tuesday October 12
*********Practice Exercises*************
1. Prove (using mathematical induction) that for any integer n >= 1, n
straight lines in the plane, all passing through a single point,
divide the plane into 2n regions.
3. Use mathematical induction to prove that for n an integer one or
greater, there are n! ways to arrangements of the numbers 1, 2, ... , n
in an array of size n.
*********** Recall *****************
Every induction proof should have the following parts:
1) Statement of the problem,
forall n, "something about n",
including stating exactly what set you are quantifying over!
(ie, forall integer n > 1)
2) Base case. Prove the statement for n = 0, 1, 2 (depends on the problem)
3) Induction Step
Assume (something about k)
Prove (something about k+1)
4) Conclusion, where you write down (1) again, BUT, silently, you are
(a) making sure that your induction step works
(maybe try out the whole induction step plugging in a number
for k)
(b) making sure that you have the right base cases (did you need to
assume anything else in your induction proof?)
***********Problems to Submit*********
1. Use mathematical induction to show that 3 divides n3 + 2n
when n is a non-negative integer.
(note that this is a solution to a slightly *different* problem.)
Base case n = 0 (the first non-negative integer).
3 | 03 + 2* 0
3 | 0 (yep).
Induction Step, prove
"3 | k3 + 2k" --> "3 | (k+1)3 + 2(k+1)"
Assume: "3 | k3 + 2k"
Prove: "3 | (k+1)3 + 2(k+1)"
(k+1)3 + 2(k+1) =
(k3 + 3k2 + 3k + 1 + 2k + 2 =
((k3 + 2k) + 3k2 + 3k + 1 + 2 =
(3j) + 3k2 + 3k + 3 =
(3j) + 3(k2 + k + 1) =
3(j + k2 + k + 1) =
3(integer)
so, 3 | (k+1)3 + 2(k+1)
so, "3 | k3 + 2k" --> "3 | (k+1)3 + 2(k+1)"
so, by induction
forall n, 3 divides n3 + 2n
2) Let's define the game NIM2 ( a different variant than the one in we
talked about in lecture. The game starts with a pile of n pennies,
each player can take exactly 1 or 2 or 3 pennies, and the last person to
take a penny *wins*.
You are player 1.
a) Write down what is your best first move, and whether or not you will win,
for the following values of n.
i) n = 1. take 1
i) n = 2. take 2
i) n = 3. take 3
i) n = 4. lose
i) n = 5. take 1
i) n = 6. take 2
i) n = 7. take 3
b) Write down a general formula for the values of n for which you can
win, even against an opponent that plays perfectly. (This should
be a formula, something like "forall n that can be written as 17k,
or 17k+1, for some integer k".
forall n that can be written as 4k + 1 or 4k + 2 or 4k + 3, you can win the game.
c) Inductively prove that you can win for the values of n described in part b.
We will now prove inductively that forall n that can be written as 4k
+ 1 or 4k + 2 or 4k + 3, player 1 can win the game. We will do this by
inducting over k.
Base case, k = 0, so n = 1 or 2 or 3.
In this case, the rules of the game allow player 1 to take n pennies. player 1 therefore wins!
Induction case:
Assume player 1 has a winning strategy for values of n = 4k + 1, 4k + 2, 4k + 3
Prove player 1 can win for values of n = 4(k+1) + 1, 4(k+1) + 2, 4(k+1) + 3
To make fewer cases, let's write the number of pennies n as
4(k+1) + j, where j is 1, 2 or 3.
If player 1 removes j pennies, it becomes player 2's turn, and there
are 4(k+1) pennies remainning. Player 2 must take 1 or 2 or 3 pennies.
if player 2 takes 1 penny, there are 4k+3 pennies remaining. By the
I.H., player 1 has a winning strategy
if player 2 takes 2 pennies, there are 4k+2 pennies remaining. By the
I.H., player 1 has a winning strategy
if player 2 takes 3 pennies, there are 4k+1 pennies remaining. By the
I.H., player 1 has a winning strategy
Therefore, for any number written as 4(k+1)+j, ... j = 1..3, we show
a winning strategy for player 1
Therefore, for any n that can be written as 4k+1,4k+2,4k+3, player 1
has a winning strategy.
3. * again, note that this is a slightly different problem *
The city of Logicus is inhabited by citizens with the following
characteristics:
1. The citizens are at a party where they can see everyone's face
except their own;
2. No citizen ever tells another anything that would embarrass that
citizen (ie, they don't talk about the poppy seeds to each other)
3. All citizens have perfect (and instantaneous) logical reasoning abilities.
Brian crashes the party and announces that at least one person has
poppy seeds in their teeth. After his proclamation, Brian immediately
leaves. The citizens (not having a mirror) decide that every 5
minutes (where all citizens look at the same clock) whoever discovers
they have poppy seeds in their teeth will excuse themselves from the
party (and we'll assume that nobody would ever dream of leaving the
party for any other reason).
In summary, we have: nobody directly knows if they have poppy seeds
in their teeth, because nobody would tell them this; however,
everyone can see who else has poppy seeds in their teeth.
Let n denote the number of people at the party who have poppy seeds in
their teeth. (Remember that the citizens only know that n >= 1 and are
not directly given any other information about its value.)
(a) When, if ever, will those with poppy seeds on their teeth leave
the party?
If there are n people at the party with poppy-seeds in their
teeth, they will leave after 5n minutes.
(b) Use a form of mathematical induction to prove that your answer is
correct.
Base Case:
Consider the case when one person has poppy seeds. He looks around,
sees no other poppy-seeded people, concludes that he must have poppy
seeds and leaves at the first 5 minute marker.
Induction Step:
Suppose that if n people have poppy seeds, they leave after 5n
minutes.
Prove that if n+1 people have poppy seeds, they leave after 5(n+1)
minutes.
Consider the case when n+1 people have poppy seeds. Each of the
people with poppy seeds see exactly n other people with seeds. If
exactly n people had poppy seeds, they would all have left on the 5n
minute mark (by the I.H.). Since they don't leave, each of the n+1
people concludes that they too must have a poppy seed, so all leave on
the 5(n+1) minute mark.