Home > math education > HCSSiM Workshop day 3

## HCSSiM Workshop day 3

July 5, 2012

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.

Next we went back to the idea of maps $f: X \times X \rightarrow X$ and got the kids to come up with a whole bunch of examples for $X = \mathbb{Z},$ such as $f(a, b) = \lceil \frac{a}{2 \dot b +1} \rceil$. We eventually got them to come up with stupider examples like $(a, b) \mapsto a$ and $(a, b) \mapsto a+b.$ Then we switched it up to the finite set $[n] = \{1, 2, 3, \dots, n\}$ and got them to generalize addition. Since $n$ really started to look like an identity element under this operation, we decided to define notation for the set $\{0, 1, 2, \dots, n-1\},$ which is like $[n]$ 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 $n$ holes and $k$ pigs which need to get put into holes, at least one of the $n$ holes to contain at least $\lceil k/n \rceil$ 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 $\sqrt{2}/2$ 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 $a$ and $b$ is (denoted $gcd(a, b)$) 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 $a$ and $b$ by their greatest common divisor, you end up with numbers that are relatively prime. We even showed there are representations of $a$ and $b$ 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 $gcd(a, b) = gcd(a - bq, b)$ when you write $a = bq + r$ for $0 \leq r

Once we had the Edwinian Algorithm, we realized we could go backwards and express $gcd(a, b)$ as a linear combination of $a$ and $b$, and we used that to prove a very important property of primes, namely that if $p$ is a prime and $p | ab$ then either $p|a$ or $p|b$ or both. This allowed us to show that the prime factorizations we’d found before for $a$ and $b$ 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 $gcd(a,b)$ is faster, through the Edwinian Algorithm or via prime factorizations.

Categories: math education