COT 5420 - Homework 0
Not to turn in.
Read Chapter 0 and solve the following background problems.
If you already have a partner (or two), you can discuss them together.
[Here's a restatement of the proof's induction step that you may
find clearer: "For k>=1 assume that the claim is true for
h=k and prove that it is true for h=k+1.
Consider any set H of k+1 horses, numbered from
1 to k+1.
Now, horses 1 through k are a set of size k,
so by the induction hypothesis they are the same color.
By the same argument, horses 2 through k+1 are the same color.
But the middle horses, 2 through k, can't change color based
on who they're grouped with; these are horses, not chameleons.
So horses 1 and k+1 must be the same color as well,
by transitivity. Thus all horses in H are the same color."]
- McDonalds sells Chicken McNuggets in packages of 6, 9, and 20.
A bit of trial and error shows that with these package sizes,
it is impossible to buy exactly 43 Chicken McNuggets.
It turns out, however, that any larger quantity can be bought.
Prove this, using induction.