\documentclass[11pt]{article}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{multicol}
\usepackage{latexsym}
\usepackage{verbatim}
\usepackage[pdftex]{graphicx}
\usepackage{enumerate}
\usepackage{url}
\usepackage{mathrsfs}
\usepackage{hyperref}
\hypersetup{colorlinks=true}
\setlength{\oddsidemargin}{.25in}
\setlength{\evensidemargin}{.25in}
\setlength{\textwidth}{6in}
\setlength{\topmargin}{-0.4in}
\setlength{\textheight}{8.5in}

\usepackage{tikz}
\newcommand*\circled[1]{\tikz[baseline=(char.base)]{
            \node[shape=circle,draw,inner sep=2pt] (char) {#1};}}

\DeclareRobustCommand{\stirling}{\genfrac\{\}{0pt}{}}
            
\input{preamble.tex}

\begin{document}

\homework{7: Burnside's Lemma}{Due Friday, Week 9}

In this HW set, there are \textbf{two} sections: a \textbf{non-collaboration} section and a \textbf{collaboration} section.  For the non-collaboration section, use only your notes/class notes, and don't work with others.  For the collaboration section, work as normal!  

Also, the HW is shorter this week because of the holiday (i.e. there's just one collaboration problem.)  Get some rest!

\section{Non-Collaboration Section}

Do the one problem below!
\begin{enumerate}
\item You have a large number of black beads and white beads, and you're trying to make a $n$-bead necklace.  Suppose that two necklaces $N_1, N_2$ are considered the ``same'' if one can be \textbf{rotated} or \textbf{flipped} in space so that it becomes the other (this is different from our earlier problems, where we only allowed rotations!)

For example, when $n=5$, there are eight such necklaces:
\begin{center}
\includegraphics[width=4in]{necklaces.pdf}
\end{center}

Create a closed formula for the total number of different necklaces under this notion of ``same,'' that holds for every prime number $n \geq 3$.

\end{enumerate}

\section{Collaboration Section}

Do \textbf{one} of the two problems below!
 
\begin{enumerate}
\item Tinkertoys!  Specifically: you have a box of Tinkertoys.  Your toys come in two forms:

\begin{itemize}
\item Rods: you have $2n$ rods \includegraphics[width=.5in]{tinkertoy_rod.pdf}, each of unit length.
\item Spools: you have $2n+1$ spools \includegraphics[width=.15in]{tinkertoy_spool.pdf}.  A spool is a disk with four equally-spaced holes.
\end{itemize}
These toys can be combined: i.e. you can use the spools to join rods together at $90^\circ$, $180^\circ$ or $270^\circ$ angles.
\begin{center}
\includegraphics[width=3in]{tinkertoys.pdf}
\end{center}

Using these toys, you want to make some sort of structure that you can lay flat on a $n \times n$ grid, so that it's contained entirely within that grid and connects two opposite corners of that grid.  When you do this, however, we want to regard any two structures that are the same under rotation or flipping as the ``same:'' i.e.
\begin{center}
\includegraphics[width=5in]{tinkertoys2.pdf}\\
\footnotesize From left to right: a configuration $C$, $C$ after reflection, $C$ after rotation, $C$ after rotation+reflection.
\end{center}

Suppose $n$ is even.  In how many different ways can you do this?





\item You're working for the (insert secret scary organization here)!  As such, you want to manufacture secret identification cards so that your secret operatives can access your secret hall of secrets.  

Identification cards are (for secret reasons) $n \times n$ square grids, in which some cells are ``punched out'' of your square.  As such, the owners of such cards cannot tell which face is up or which edge faces which way.  

When your secret society was first founded by its six secret founders, they only needed $2 \times 2$ grids to give each founder their own identifying card.
\begin{center}
\includegraphics[width=3in]{keycards.pdf}
\end{center}

However, your secret society has secretly grown by quite a lot!  As such, you have been tasked with the problem of determining for any $n$ the maximum number of different $n \times n$ cards (where we regard two cards as the same if one can be rotated/flipped in such a way to be the same as another card.)

Can you find a closed formula based on $n$ for the number of such cards?



\end{enumerate}



\section{Extra-Credit Section}

Solve any problem below for extra credit! If you want this problem to be graded, write it on a separate piece of paper and submit it separately/directly to me.
 
\begin{enumerate}
\item On last week's HW, you determined the number of ways to paint the faces of a tetrahedron with $n$ colors up to rotations.  

Answer the same problem for all of the other regular polyhedra!
\end{enumerate}
\end{document}

