\documentclass[12pt]{article}

\usepackage{latexsym}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{tikz}

\newtheorem*{goal}{Goal}

\newcommand{\CC}{\mathbb{C}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\dd}{\displaystyle}
\newcommand{\scs}{\scriptstyle}

\setlength{\evensidemargin}{1in}
\addtolength{\evensidemargin}{-1in}
\setlength{\oddsidemargin}{1.5in}
\addtolength{\oddsidemargin}{-1.5in}
\setlength{\topmargin}{1in}
\addtolength{\topmargin}{-1.5in}

\setlength{\textwidth}{16cm}
\setlength{\textheight}{23cm}


\pagestyle{empty}


\begin{document}



\section*{Math 3140: Homework 3}




\begin{enumerate}
\item[A.] 5.4, 5.10
\item[B.]  For $D_n$, let the vertices of the regular $n$-gon be labeled by $0,1, \ldots, n-1$ in a counter-clockwise direction.  Let $t$ be symmetry that sends the vertex $0$ to $1$ and the vertex $2$ to $n-1$.  Let $s$ be the symmetry that sends $0$ to $0$ and sends $1$ to $n-1$.  Show that 
$$D_n=\langle s,t\rangle.$$
\item[C.] Find examples of the following (justify your answer), or explain why they don't exist:
\begin{enumerate}
\item[(1)] A nonabelian cyclic group.
\item[(2)] A group generated by two elements.
\item[(3)] A group generated by three elements, but not by two element.
\end{enumerate}
\item[D.] Show that $(\QQ,+)$ is not cyclic.  In fact, show that $(\QQ,+)$ does not even have a finite number of generators.  Hint: What does the subgroup $\langle p/q\rangle$ look like for $p,q\in \ZZ_{\neq 0}$?
\item[E.] A \emph{perfect shuffle} is a shuffle where you split the deck into two equal stacks (the top stack and the bottom stack) and push the stacks together in such a way that the cards from the two stacks alternate.  There are two ways of doing this: either the bottom card came from the top stack (an \emph{in-shuffle}), or the bottom card came from the bottom stack (an \emph{out-shuffle}).  For example, if you have 10 cards,
\begin{equation*}
\text{In-shuffle:} \ \begin{tikzpicture}[baseline=1cm,scale=.1]
	\foreach \y in {0,...,19}
		\draw (0,\y) -- (6,\y);
\end{tikzpicture} \longmapsto
 \begin{tikzpicture}[baseline=1cm,scale=.1]
	\foreach \y in {0,...,9}
		\draw[gray] (0,\y) -- (6,\y);
	\foreach \y in {10,...,19}
		\draw (0,\y) -- (6,\y);
	\foreach \y in {10,...,19}
		\draw (10,\y.5) -- (16,\y.5);
	\draw[|-|] (7,0) -- (7,9);
	\draw[->] (8,4.5) to [out=0,in=-90] (13,9);
\end{tikzpicture}
\longmapsto
\begin{tikzpicture}[baseline=1cm,scale=.2]
	\foreach \y in {0,...,9}
		\draw (0,\y) -- (3,\y);
	\foreach \y in {0,...,9}
		\draw (2,\y.5) -- (5,\y.5);
\end{tikzpicture}\quad
\text{Out-shuffle:} \ \begin{tikzpicture}[baseline=1cm,scale=.1]
	\foreach \y in {0,...,19}
		\draw (0,\y) -- (6,\y);
\end{tikzpicture} \longmapsto
 \begin{tikzpicture}[baseline=1cm,scale=.1]
	\foreach \y in {0,...,9}
		\draw[gray] (0,\y) -- (6,\y);
	\foreach \y in {10,...,19}
		\draw (0,\y) -- (6,\y);
	\foreach \y in {9,...,18}
		\draw (10,\y.5) -- (16,\y.5);
	\draw[|-|] (7,0) -- (7,9);
	\draw[->] (8,4.5) to [out=0,in=-90] (13,9);
\end{tikzpicture}
\longmapsto
\begin{tikzpicture}[baseline=1cm,scale=.2]
	\foreach \y in {1,...,10}
		\draw (0,\y) -- (3,\y);
	\foreach \y in {0,...,9}
		\draw (2,\y.5) -- (5,\y.5);
\end{tikzpicture}
\end{equation*}
By a judicious use of in and out-shuffles one can create all kinds of card tricks (providing one is capable of a perfect shuffle), since such shuffling is in no way random.  Suppose you have a deck of 52 cards. 
\begin{enumerate}
\item[(1)] Prove that if you apply the in-shuffle enough times, you will get back with what you started.  Hint: prove that you get back where you started without actually doing it (it's a lot of shuffles).
\item[(2)] How many out-shuffles do you need to get back where you started (Justify your answer)?
\end{enumerate}
Remark: It turns out with normal shuffling (which is far from perfect) it takes approximately 7 shuffles to get close to random (which is proved in part using methods of this class).

\end{enumerate}

\end{document} 