\documentclass[12pt]{article}

\usepackage{amsmath,amscd,amsbsy,amssymb,latexsym,url}
\usepackage{epsfig,graphicx,subfigure}
\usepackage{enumitem,balance,mathtools}
%\usepackage[labelsep=period, justification=justified, bf, width=1.3\linewidth, format=plain]{caption}
\usepackage{wrapfig}
\usepackage{tikz} \setlength\oddsidemargin{-0.05in}
\usetikzlibrary{calc} \setlength\evensidemargin{-0.05in}
%\usepackage{natbib}
\setlength\textheight{8.7in} \setlength\topmargin{-0.1in}
\setlength\textwidth{6.3in}
\usepackage{mathrsfs, euscript}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{exercise}{Exercise}[section]
%\newtheorem{solution}{section}

\setcounter{section}{1} \numberwithin{equation}{section}
\numberwithin{figure}{section}

\newenvironment{proof}[1][Proof:]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
\newenvironment{definition}[1][Definition:]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
\newenvironment{example}[1][Example:]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
\newenvironment{remark}[1][Remark:]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
\newenvironment{solution}[1][Solution:]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}

\newcommand{\qed}{\nobreak \ifvmode \relax \else
      \ifdim\lastskip<1.5em \hskip-\lastskip
      \hskip1.5em plus0em minus0.5em \fi \nobreak
      \vrule height0.4em width0.5em depth0.25em\fi}
\newcommand{\hw}[1]{#1}%includes solutions
%\newcommand{\hw}[1]{}
\newcommand{\indt}[1]{\begin{list}{\setlength\leftmargin{0.5in}}\item{}#1\end{list}\noindent}
\def\Prob{\text{Prob}}
\def\prob{\text{Prob}}
\begin{document}
\noindent

%========================================================================
\begin{center}
\textbf{\Large{Homework 8}} \vspace{2mm}

Mathematics in Computer Science
%John E. Hopcroft
\end{center}
\vspace{1mm}

\begin{enumerate}
 \item Prove that the smallest group
 containing $I,r$, and $f$ is $G=\{I,r,r^2,\ldots ,fr^3\}.$
  %
 \item What is the group $\{I,a,b,c,\ldots \}$ with
 $ac=ca,bc=cb,aa=I,bb=I,cc=I,bab=I$. 
 %
 \item
  \begin{enumerate}
  \item  What is the set of physical symmetries of the cube?
  \item Give a brief discussion that will convince us that your
  answer to part (a) is correct.
  \end{enumerate}
  %
\item
  \begin{enumerate}
  \item What are the symmetries of the tic tac toe board game?
  \item Construct the group multiplication table for the symmetries.
  \end{enumerate}
  %
\item Consider tic tac toe boards that are completely filled in with
{\footnotesize $\bigcirc$}'s and $\times $'s.  Use Burnside's theorem to determine the number
of equivalence classes.
%
\item  Let $b_1,b_2,\ldots $ be the various board
positions of tic tac toe. Let $G$ be a group of transformations that
map board positions to equivalent board positions.
\begin{enumerate}
  \item How many board configurations are there if each position on
  the board contains an {\footnotesize$\bigcirc$}, a $\times$, or is open?
  \item Prove that the number of elements of $G$ that preserve a board
configuration $b_1$ is the same as the number of group elements that
map $b_1$ to an equivalent configuration $b_2$.
\item  How many elements are there in the equivalence class of $b_1$
if $|G|=m$ and $k$ elements of $G$ preserve $b_1$.
\end{enumerate}
%
\item Consider two operations on a $2\times 2$ square.  The
operations are: $r$ which is a rotation of $180^{\circ}$, and $f$ which is
a flip about the diagonal axes from upper left to lower right.
\begin{enumerate}
  \item What is minimum number of additional operations that needed
to be added to form a group?
  \item Write out the group table.
\end{enumerate}
\begin{center}

\begin{tikzpicture}
\foreach \x in {0,2}{\foreach \y in {0,2}{
  \draw (\x,\y) rectangle (\x+1,\y+1);
  \draw (\x,\y+0.5)--(\x+1,\y+0.5);
  \draw (\x+0.5,\y)--(\x+0.5,\y+1);
  \draw (1.1,\y+0.5) [thick,->] -- (1.9,\y+0.5);}}
  \draw (1.5,0.5) [above] node {$f$};
  \draw (1.5,2.5) [above] node {$r$};
  \foreach \z in {0,2}{
    \draw (0.25,\z+0.25) node {3};
    \draw (0.25,\z+0.75) node {1};
    \draw (0.75,\z+0.25) node {4};
    \draw (0.75,\z+0.75) node {2};}
  \draw (2.25,0.25) node {2};
  \draw (2.25,0.75) node {1};
  \draw (2.75,0.25) node {4};
  \draw (2.75,0.75) node {3};
  \draw (2.25,2.25) node {2};
  \draw (2.25,2.75) node {4};
  \draw (2.75,2.25) node {1};
  \draw (2.75,2.75) node {3};
\end{tikzpicture}
\end{center}
 \end{enumerate}

%========================================================================
\end{document}
