HCSSiM Workshop day 8
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.
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: