A continuation of this, where I take notes on my workshop at HCSSiM.
Equivalence Relations and Partial Orderings
After going over many proofs of the geometry problem from last night’s problem set, I corrected the mistake in the “antisymmetric” property and we went through plenty of examples of equivalence relations and partial orderings. We ended with linear orderings, the real numbers, and the less than or equal relation.
Adding modulo n
Next we went back to the idea of maps 
and got the kids to come up with a whole bunch of examples for 
such as 
. We eventually got them to come up with stupider examples like 
and 
Then we switched it up to the finite set ![[n] = \{1, 2, 3, \dots, n\}](https://s0.wp.com/latex.php?latex=%5Bn%5D+%3D+%5C%7B1%2C+2%2C+3%2C+%5Cdots%2C+n%5C%7D&bg=ffffff&fg=555555&s=0&c=20201002)
and got them to generalize addition. Since 
really started to look like an identity element under this operation, we decided to define notation for the set 
which is like ![[n]](https://s0.wp.com/latex.php?latex=%5Bn%5D&bg=ffffff&fg=555555&s=0&c=20201002)
but on its side.
Pigs-in-hole Principle
We introduced the pigeonhole principle (but since our camp mascot is a yellow, pig, we call it pigs-in-hole). We actually defined the slightly more general idea that, if you have holes and 
pigs which need to get put into holes, at least one of the holes to contain at least 
pigs. With that we proved that at least 2 people in New York City have the same number of hairs on their head, that five points in a 1 by 1 square are withing distance 
of each other, that in a group of $n$ people at least two people will have had the same number of handshakes, and others.
Greatest Common Divisor
We asked the kids what the greatest common divisor of 
and 
is (denoted 
) and how to compute it. We spent a long time chasing down rabbit holes and proving other things that didn’t help us find the greatest common divisor but were true. For example, we showed that if you divide and by their greatest common divisor, you end up with numbers that are relatively prime. We even showed there are representations of and as products of primes, but since we couldn’t yet prove those were unique representations, we could use that to come up with a way to find the “common primes.”
Eventually we thought of a trick to reduce the problem, namely the division algorithm. Actually Edwin thought of the trick, and it eventually became the Edwinian Algorithm (not like it’s usually called, namely the Euclidean Algorithm). Edwin observed that 
when you write 
for 
Once we had the Edwinian Algorithm, we realized we could go backwards and express as a linear combination of and , and we used that to prove a very important property of primes, namely that if 
is a prime and 
then either 
or 
or both. This allowed us to show that the prime factorizations we’d found before for and were in fact unique up to relabeling, which we left for homework.
So it turns out I’m not going to be able to make the homeworks public, but we had an awesome problem set with lots of pigeon hole problems and Edwinian Algorithm problems. We asked them to decide which approach to calculating 
is faster, through the Edwinian Algorithm or via prime factorizations.
mathbabe 