HCSSiM Workshop day 2
A continuation of this, where I take notes on my workshop at HCSSiM.
The watermelon cutting problem revisited
We prove that the maximum number of pieces of watermelon you can cut with slices, assuming a watermelon of dimension
, denoted by
is given by:
First we proved it with a combinatorial argument, then with induction. I decided the first one is better because you figure out the answer as you go, whereas the induction route requires that you already know the formula. They both require you to use the recursion relation we talked about yesterday, and the first one involved writing a 2-d chart and showing how to unpack the value of using the recurrence relation, into paths going up to the top row consisting of all ones, and then the question becomes, “how many ways can you get to the top row?” and of course the answer is something like
, where you go up
times and left
times.
All pigs are yellow
Next we proved, using induction, that all pigs are the same color, and then we exhibited a yellow pig so a corollary was that all pigs are yellow. The base case is that a single pig is the same color as itself, and then assuming we have n pigs of the same color, we get to the statement that n+1 pigs are all the same color by first putting one pig in the barn, and then some other pig in the barn, and the leftover pigs are the same color as each of those so they’re all the same color.
This argument, of course, doesn’t work when you’re moving from “1 pig” to “2 pigs” and exhibits how careful you have to be with working through enough base cases so that your inductive step actually applies.
Strong Induction
We then went to using the Principle of Strong Induction (after showing that there’s no Principle of Induction over the real numbers). We proved that all numbers can be written as the sum of powers of 2, that the Fibonacci numbers grow exponentially, that every positive integer at least 2 is divisible by a prime, and that every planar polygon can be diagonalized using strong induction.
Notation
Incidentally, instead of “Strong Induction” the students voted to call it “Thor Induction”, and instead of the standard end-of-proof symbol, which is a box with an “x” inside, we voted to use the symbol “(see next page)”. They had lots of fun with that one. As a corollary, they decided that if they wanted someone to actually see the next page, they’d use the “Q.E.D.” symbol.
Cross product of Sets
Finally, we talked about the notation which denotes the cross product of sets, and made a bunch of examples, mostly of the form
specifically when
and
which we then drew as the plane and the lattice points. We ended by showing an injection from
into the lattice points, which incidentally showed that
and
have the same cardinality, which we didn’t really define but we will.
In problem 11 did you intend the definition of partial ordering to be that way? I think ti’s impossible for a relation to be “antisymmetric” and reflexive at the same time.
LikeLike
Shoot yes I should have defined “anti-symmetric” to say if
and
then
. Thanks for pointing this out!
LikeLike