\documentclass[12pt]{article}
 \usepackage[top=2cm, bottom=2cm, left=2cm, right=2cm]{geometry} 
\usepackage{graphicx}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{lgarron}
\usepackage{color}
\usepackage{ stmaryrd }
\usepackage{hyperref}

\DeclareSymbolFont{extraup}{U}{zavm}{m}{n}
\DeclareMathSymbol{\heart}{\mathalpha}{extraup}{86}
\DeclareMathSymbol{\diamond}{\mathalpha}{extraup}{87}
\DeclareMathSymbol{\spade}{\mathalpha}{extraup}{81}
\DeclareMathSymbol{\club}{\mathalpha}{extraup}{84}


\usepackage{fancyhdr}
\pagestyle{fancy}

\def\und#1#2{{\underset{#1}{\underbrace{#2}}}}
\def\date#1{\gdef\@date{#1}}

\hypersetup{pdfborderstyle={/S/U/W 1},pdfborder=0 0 1} 

\def\homeworkname{{Lucas Garron}}
\def\homeworkcoursenum{{Math 102}}
\def\homeworkcoursename{{$\club\diamond\heart\spade$ Mathematics \& Magic}}
\def\homeworknum{{April 05, 2012}}

\title{{\homeworkcoursenum} ({\homeworkcoursename}) Course Notes\\{\homeworknum}}
\author{\homeworkname}
\fancyhead[CO]{{\homeworkname} -- {\homeworkcoursenum} ({\homeworkcoursename}) -- {\homeworknum}\\}


\newenvironment{mylist}[1]%
  {\begin{list}{}{\settowidth{\labelwidth}{\textbf{#1}}
   \setlength{\leftmargin}{\labelwidth}
   \addtolength{\leftmargin}{\labelsep}
   \renewcommand{\makelabel}[1]{\textbf{\hfill##1}}}}%
  {\end{list}}
  
  
\begin{document} 

\maketitle

These notes are available at \href{http://stanford.garron.us/class/math102/}{http://stanford.garron.us/class/math102/}

\section{Meta}

\begin{itemize}
\item Course notes from the first day are on \href{https://coursework.stanford.edu/portal/site/Sp12-MATH-102-01/}{Coursework}, under Syllabus.
\item Today is the last day for auditions.
\end{itemize}

\section{Group Theory}

\subsection{Definition of a Group}

A group is
\begin{itemize}
\item a set $G$,
\item and a notion of multiplication, $G \times G \to G$, so $(g_1, g_2) \to g_1 * g_2$
\end{itemize}

The following have to hold:

\begin{enumerate}
\item The product has to be associative.
\[(g_1 * g_2) * g_3 = g_1 * (g_2 * g_3)\]
\item THere must be an identity, which we'll write as $id = 1$, such tha
\[1*g = g*1 = g\]
\item Every element has an inverse in $G$. The inverse of $g$ is written $g^{-1}$, so that
\[g^{-1} * g = g * g^{-1} = 1\]
\item [Closure]
\end{enumerate}

\subsection{Example: Cyclic Groups}

\[C_n = \{0, 1, 2, ..., n-1\}\]

Multiplication is defined by
\[i*j = i+j \m n\]
(e.g. $n=5$, $4+4 \equiv 3 \m 5$)

\subsubsection{Example of a cyclic group: Cutting a Deck}
$n$ cards form $C_n$ under the operations of cutting cards $i$ from top to bottom.

$id = i$, $i^{-1} = -i$

\section{Permutation Groups}

\[S_n = \{\text{All arrangements of a deck of $n$ cards labeled }1, 2, 3, ..., n\}\]

Notation: $\pi(i)$ is the label of the card at position $i$.

\subsection{Example of a permutation}

\[\pi = 3~2~1~4~5\]

Card $3$ on top, card $2$ below, etc.

\subsection{Long Notation}

We can also write this as

\[\left(\begin{array}{ccccc}
1 & 2 & 3 & ... & n \\
\pi(1) & \pi(2) & \pi(3) & ... & \pi(n)
\end{array}\right)\]

For example, switching the top two cards is the following permutation:

\[x = \left(\begin{array}{ccccc}
1 & 2 & 3 & ... & n \\
2 & 1 & 3 & ... & n
\end{array}\right)\]

Cutting the top to bottom:

\[y = \left(\begin{array}{ccccc}
1 & 2 & 3 & ... & n \\
2 & 3 & 4 & ... & 1 \\
\end{array}\right)\]

The product $\pi * \sigma$ is defined as doing $\sigma$, and then doing $\pi$. Think of the permutation like a function: $\pi * \sigma = \pi(\sigma)$ or $a * b * c * d = a(b(c(d)))$

Using $x$ and $y$ as defined above, we have

\[x * y = \left(\begin{array}{ccccc}
1 & 2 & 3 & ... & n \\
3 & 2 & 4 & ... & 1 \\
\end{array}\right)\]

But $x$ and $y$ don't commute, so the order of multiplication matters:
\[y * x = \left(\begin{array}{ccccc}
1 & 2 & 3 & ... & n \\
1 & 3 & 4 & ... & 2 \\
\end{array}\right)\]

\subsection{Inverse of a Permutation}

If

\[\pi = \left(\begin{array}{ccccc}
1 & 2 & 3 & ... & n \\
\pi(1) & \pi(2) & \pi(3) & ... & \pi(n)
\end{array}\right),\]

then the inverse $\pi ^{-1}$ can be computed like this:

\begin{enumerate}
\item Find $1$ in row $2$; whatever is above is $\pi^{-1}(1)$.
\item Find $2$ in row $2$; whatever is above is $\pi^{-1}(2)$.
\item ...
\end{enumerate}

Alternatively, you could think of it this way:

\begin{enumerate}
\item Switch the two rows.
\item Sort the top row.
\end{enumerate}


Thus,
\[
\left(\begin{array}{ccccc}
1 & 2 & 3 & 4 & 5 \\
2 & 3 & 4 & 5 & 1 \\
\end{array}\right)^{-1}
=
\left(\begin{array}{ccccc}
1 & 2 & 3 & 4 & 5 \\
5 & 1 & 2 & 3 & 4 \\
\end{array}\right)
\]

\subsection{Perfect Riffle Shuffles}

If you split a deck of $8$ cards perfectly in half and riffle shuffle them (alternate between dealing from halves to form a pile), the following happens:

\[\left(\begin{array}{cccccccc}
1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\
1 & 5 & 2 & 6 & 3 & 7 & 4 & 8 \\
\end{array}\right)\]

\subsection{Element Order}
The \emph{order} of any group element $g$ is the smallest $k$ such that
\[\und{k}{g*g*g*...*g} = 1\]

\subsubsection{Example: Cut $1$ card}
If $G = S_n$ and $\sigma = (\text{move a card from top to bottom})$, then the order of $\sigma$ is $n$.

\subsubsection{Order of a Riffle Shuffle}
Problem: Find the order of a perfect shuffle of $2n$ cards, e.g. how many perfect riffle shuffles do you need to do to a deck of cards until you get back to the original order?

Note: Although this is easy to compute for any $n$, there is no general known solution for finding the order.

\subsection{Cycle Notation}

Given $\pi$:

\begin{enumerate}
\item Write down a cycle

\begin{enumerate}
\item Write down the smallest number not used (e.g. $1$ for the cirst cycle); call it $x$
\item Write down $\pi(x)$.
\item Write down $\pi(\pi(x))$.
\item Stop when (right before) you get back to $x$.
\end{enumerate}
\item If there are any numbers left, write down another cycle.
\end{enumerate}

\subsubsection{Cycle Notation Example}

For example, take
\[\left(\begin{array}{cccccccccc}
1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\
3 & 7 & 2 & 5 & 1 & 8 & 4 & 10 & 9 & 6
\end{array}\right)\]

In cycle notation, this is
\[(1~3~2~7~4~5)(6~8~10)\]
(Note that we left out $9$).

From cycle notation, we see that a cycle recycles to its original position with an order that is its length.

Say we have $(123)(5746)$. The first part takes $3$ repetitions to recycle, but the second part takes $4$ repetitions. They both recycle together after $12$ repetitions.

{\proposition
In general, if $\sigma$ has cycles of length $l_1, l_2, ..., l_n$, the order of $\sigma$ is $lcm(l_, l_2, ..., l_n)$.
}

\subsubsection{What shuffle takes the longest?}

What permutation (of $S_n$) takes the longest number of repetitions to recycle?

We want distinct (relatively) prime parts that add up to $n$ but have the greatest product.

Example: For $52$ cards, this is $180180$.

\subsection{Antimagic Squares}

\subsubsection{A Magic Square}

Here's a $3x3$ magic square. This is a square grid with number such that every row, column, and diagonal adds up to the same number ($15$ in this case).

\[\begin{array}{|c|c|c|}
\hline
4 & 3 & 8 \\
\hline
9 & 5 & 1 \\
\hline
2 & 7 & 6 \\
\hline
\end{array}\]

A mnemonic for reconstructing this: Put $4, 5, 6$ on the diagonal, then fill in the rest. 

\subsubsection{An Antimagic Square}

Instead of adding up to the same sum, we want all the directions to add up to \emph{different} sums:

\[\begin{array}{|c|c|c|}
\hline
1 & 2 & 3 \\
\hline
8 & 9 & 4 \\
\hline
7 & 6 & 5 \\
\hline
\end{array}\]

(It's a spiral!)

\subsubsection{An Antimagic Square Trick}
Lay out the cards in an anti magic square. Give someone in the audience a prediction, and give the directions to someone else.

\begin{itemize}
\item Put your finger on any card.
\item Look at the number of that card, and hop with your finger that often (each hop is to an adjacent card, horizontally or vertically).
\item Remove the ace.
\item Hop $4$ times, remove the $5$.
\item Hop $3$ times, remove the $2$.
\item Hop $3$ times, remove the $3$.
\item Hop $5$ times, remove the $4$.
\item Hop $4$ times, remove the $6$.
\item Hop $1$ times, remove the $7$.
\item Hop $3$ times, remove the $8$.
\item You card was the $9$ (e.g. $9\diamond$ if that was the $9$ on the table).
\end{itemize}

\subsubsection{History}
Persi came up with this trick when he was young, and showed it to Martin Gardner; it's been used to great effect (e.g. commercialized as ``Voice from Another Planet'') over the years.


\section{Parity}

\subsection{A Trick}

Lay out 5 cards: $1~2~3~4~5$

\begin{itemize}
\item Put your finger on any card, remove the ace.
\item Move $2$ more steps, remove the $5$.
\item Move $3$ more steps, remove the $2$ and the $4$.
\item Your finger is on the $3$.
\end{itemize}

\subsubsection{Analysis}
After the first move, you're on one of the even cards (ace is safe to remove). Then, if you move any even number of steps, you have to be back on an even-numbered card (5 is safe to remove). Then, if you move any odd number of steps, you have to end up on the $3$.

There are two ideas at play:

\begin{itemize}
\item If you're on an even position, then
\begin{enumerate}
\item an even number of hops will keep you at an even position.
\item an odd number of hops will switch you to an odd position
\end{enumerate}
(and complementarily for starting at an odd position).
\item If the original layout is $1~2~3~4~5$, we can force the parity to an even position ``naturally''.
\end{itemize}



% Idea: Do this with a necklace? (Candy Necklace?)

\subsection{Martin Gardner's ``$13$th Turn''}

\begin{enumerate}
\item Place a die on the table, look at a corner, and add up the dots touching it.
\item Look away, and ask a volunteer to to tip the die of over an edge 12 time, and then choose to do it a $13$th time or not (their choice).
\item Ask them to tip it $4$ more times.
\item Look at the die and announce whether they did the $13$th turn earlier.
\end{enumerate}

The trick: The parity of the dots around a corner changes every roll.

\subsection{Informally Definition of Parity}
``Subgroups of order $2$''.




\end{document}

