HCSSiM Workshop day 8
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 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
for some integer
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 . Note this just means there’s nothing above it. But now the inductive hypothesis holds, and we cover the remaining set with chains
and moreover we define
to be the largest element in
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 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 There are two cases, either
is incomparable to any of the
‘s or it is comparable to at least one of them.
In the first case, we have an anti-chain of size namely the
‘s plus
, and we can form a
st chain consisting of just
itself.
In the second case, is comparable to some
Since
is maximal, and since
is maximal in its chain
with respect to being in a maximal antichain, we can form a new chain which is just the same thing as
for
and below, and goes straight up to
from
Note we may be missing some stuff that used to be above
in
But that doesn’t matter, because if we remove this new chain, we see that the maximal anti-chains leftover is only of size
so by Strong Induction we can cover it with
chains, and then bring back this chain to get an overall covering with
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 relatively prime to
as a function of
called
and wrote out a table up to 17. We observed that
and that, from the Chinese Remainder Theorem, we also could infer that for
we have
Writing out a prime factorization for
we realized we’d have a formula for
if we just knew
for any prime
and any positive
We wrote out a picture and decided
We ended by proving Euler’s formula by induction on the number of distinct prime factors:
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