Home > math education > HCSSiM Workshop day 8

HCSSiM Workshop day 8

July 11, 2012

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
  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!

    Like

  1. July 12, 2012 at 6:53 am
    HCSSiM Workshop day 9 « mathbabe
Comments are closed.
%d bloggers like this: