HCSSiM Workshop day 8

Home > math education > HCSSiM Workshop day 8

HCSSiM Workshop day 8

July 11, 2012 Cathy O'Neil, mathbabe

A continuation of this, where I take notes on my workshop at HCSSiM.

We first saw presentations from the students from last night’s problem set. One was a four line proof that the last two digits of $17^{2012}$ are 61. The other was a beautiful proof that the only real numbers that have more than one decimal representation are rationals of the form $a/10^k$ for some integer $k.$

Dillworth’s Theorem Revisited

After going over examples of chains and antichains, and making sure we knew that there must be at least as many chains as there are elements in an anti-chains if we want the chains to cover our set, we set up a proof by induction on the number of elements in our set. The base case is easy (one element, one chain, one element in a maximal anti-chain) and then to reduce to a smaller case we remove any maximal element $m$ . Note this just means there’s nothing above it. But now the inductive hypothesis holds, and we cover the remaining set with chains $C_1, C_2, \dots, C_k$ and moreover we define $a_i \in C_i$ to be the largest element in $C_i$ such that it is contained in some maximal anti-chain.

We then stated two lemmas. The first is that any maximal anti-chain must have a unique element in each chain $C_i$, and the second is that, after defining the elements $a_i$ as above, they form a maximal anti-chain. We treat these lemmas as black boxes for the proof (the first we did yesterday, the second is on problem set tonight).

Now we put back the removed point $m.$ There are two cases, either $m$ is incomparable to any of the $a_i$ ‘s or it is comparable to at least one of them.

In the first case, we have an anti-chain of size $k+1,$ namely the $a_i$ ‘s plus $m$ , and we can form a $(k+1)$ st chain consisting of just $m$ itself.

In the second case, $m$ is comparable to some $a_i.$ Since $m$ is maximal, and since $a_i$ is maximal in its chain $C_i$ with respect to being in a maximal antichain, we can form a new chain which is just the same thing as $C_i$ for $a_i$ and below, and goes straight up to $m$ from $a_i.$ Note we may be missing some stuff that used to be above $a_i$ in $C_i.$ But that doesn’t matter, because if we remove this new chain, we see that the maximal anti-chains leftover is only of size $k-1,$ so by Strong Induction we can cover it with $k-1$ chains, and then bring back this chain to get an overall covering with $k$ chains.

Dihedral Groups

After reviewing the formal definition of a Karafiol (group), we used rotations and flips of a folder and then of a regular 5-gon to come up with a non-commutative group. We defined a subgroup and explored the different subgroups of the dihedral group as well as other examples we’d seen coming from modular arithmetic.

Euler’s Totient function

We introduced the number of positive integers less than $n$ relatively prime to $n$ as a function of $n$ called $\phi(n)$ and wrote out a table up to 17. We observed that $\phi(p) = p-1$ and that, from the Chinese Remainder Theorem, we also could infer that for $gcd(m, n) = 1$ we have $\phi(mn) = \phi(m) \phi(n).$ Writing out a prime factorization for $n = \prod_i p_i^{a_i}$ we realized we’d have a formula for $\phi(n)$ if we just knew $\phi(p^a)$ for any prime $p$ and any positive $a.$ We wrote out a picture and decided $\phi(p^a) = p^a - p^{a-1}.$

We ended by proving Euler’s formula by induction on the number of distinct prime factors:

$\sum_{d | n} \phi(d) = n.$

Categories: math education

Comments (1)

Joshua Zucker

July 14, 2012 at 12:39 pm

What do you think of the induction proof you mention for the totient sum, compared with the “just write out all the fractions k/n and simplify them” proof?

Also thanks for sharing your outline of all these lovely days of mathematics. Definitely brings back the summer camp memories (for me, the Ross program most of all) and reminds me of why I’m staying so involved in math circles. This year I’m going to do a number theory series at the San Jose math circle, and I’m definitely stealing some of your ideas here!

LikeLike