\documentclass[11pt]{article}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{multicol}
\usepackage{latexsym}
\usepackage{verbatim}
\usepackage[pdftex]{graphicx}
\usepackage{url}
\usepackage{mathrsfs}

\usepackage[all,arc]{xy}
\usepackage{hyperref}
\hypersetup{colorlinks=true}
\usepackage{textcomp}
\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}

\final{}{Due Wednesday, 6pm, to my office (SH 6516.)}


This final has \textbf{three} sections!

\begin{enumerate}
\item \textbf{Non-Collaboration Section}  ($33\%$.)  This section contains four quiz-styled problems, of which you will pick two.   If you attempt more than two, only your first two problems will be graded.  You are allowed to use your notes from class and the online class notes in this section; however, other resources (e.g. the internet, Mathematica, classmates) are off-limits.  You get \textbf{four} hours to complete this section!
\item \textbf{Collaboration Section} ($67\%$.) This section contains four homework-styled problems, of which you will pick two.  If you attempt more than two, only your first two problems will be graded.  You are allowed to use your notes from class, online class notes, Wikipedia, textbooks, Mathematica/Wolfram Alpha/etc, and can also collaborate with other people in the class.  As with the HW, you must cite all of your collaborators, and prove any results that you want to use that haven't been proven in class.  Also, all proofs/writeups/etc must be done in your own words.  You get \textbf{eight} hours to complete this section!
\item \textbf{Extra-Credit Section} (+$10\%$.) This section contains a single extra credit problem, worth up to $10\%$ extra on your final exam grade!  It has no time limit.  With that said, focus on the first two sections first; they're worth much more for your grade!
\end{enumerate}

The way time limits work is via the honor system, and as follows:\ 
\begin{itemize}
\item On the second page of this final, you can find a table for logging start/stop times on your work. 
\item When you start work, write down when you start the problem.
\item When you stop --- i.e., to take a break, or go to sleep, or go for a run --- write down when you stop.
\item Work is somewhat subjective, but can be broadly construed as ``thinking about and/or working on the problems.''  As long as you are being fairly reasonable and ethical here, you are likely doing the right thing!
\end{itemize}

You can send in questions by email or ask them at office hours; I will be a bit more cryptic than normal, but will still be helpful!  Over finals week, I will run extended office hours to help with questions: there will be OH on Monday and Tuesday from 12-3pm.

Good luck and have fun!
\newpage
\begin{center}
\textbf{Non-Collaboration Section Timesheet}\\
\begin{tabular}{|c|c|}\hline
\qquad\qquad\qquad Time started \qquad\qquad\qquad&\qquad\qquad\qquad Time stopped\qquad\qquad\qquad\\\hline
&\\\hline
&\\\hline
&\\\hline
&\\\hline
&\\\hline
&\\\hline
&\\\hline
&\\\hline
&\\\hline
&\\\hline
&\\\hline
&\\\hline
&\\\hline
&\\\hline
&\\\hline
&\\\hline
\end{tabular}
\end{center}

\begin{center}
\textbf{Collaboration Section Timesheet}\\
\begin{tabular}{|c|c|}\hline
\qquad\qquad\qquad Time started \qquad\qquad\qquad&\qquad\qquad\qquad Time stopped\qquad\qquad\qquad\\\hline
&\\\hline
&\\\hline
&\\\hline
&\\\hline
&\\\hline
&\\\hline
&\\\hline
&\\\hline
&\\\hline
&\\\hline
&\\\hline
&\\\hline
&\\\hline
&\\\hline
&\\\hline
&\\\hline
&\\\hline
&\\\hline
&\\\hline
&\\\hline
&\\\hline
&\\\hline
&\\\hline
&\\\hline
\end{tabular}
\end{center}
\newpage


\section{Non-Collaboration Section}
Do \textbf{two} of the \textbf{four} problems in this section!  All problems are on their own page.


\begin{enumerate}
\item Triphenylphosphine is a molecule made out of 18 carbons (\includegraphics[height=.1in]{carbon.pdf}), 15 hydrogens (\includegraphics[height=.1in]{hydrogen.pdf}), and one phosphorous molecule (\includegraphics[height=.1in]{phosphorous.pdf}), as drawn below:
\begin{center}
\includegraphics[width=2in]{molecule.pdf}
\end{center}

Suppose that you are interested in studying all of the possible molecules that can arise after some of the hydrogen molecules above are replaced with bromine molecules (\includegraphics[height=.1in]{bromine.pdf}).  We consider two of these triphenylphosphine+bromine molecules to be the same if one can be transformed into the other by some combination of the following three operations:
\begin{itemize}
\item Rotating the whole molecule around its center.
\item Reflecting the whole molecule over some axis.
\item Reflecting any one of the three carbon hexagons over the carbon-phosphorous bond.
\end{itemize}  
\begin{center}
\includegraphics[width=5in]{molecule_ex.pdf}
\end{center}
How many different molecules are there in total?

\newpage 


\item A poset $\langle P, < \rangle$ is called \textbf{self-dual} if there is a bijection $f: P \to P$ such that for any $x, y \in P$, we have $f(x) \geq f(y)$ if and only if $x \leq y$.  
\begin{enumerate}
\item Show that the divisor poset is self-dual.
\item Show that the Boolean lattice is self-dual.
\item Find a poset that is not self-dual.
\item Find a lattice that is not self-dual.
\end{enumerate} 


\newpage 

\item Take the collection of all $4 \times 4$ Latin squares on the symbol set $\{1,2,3,4\}$.  There are 576 many such squares, as given in the notes.

Suppose that we consider two Latin squares to be equivalent if one can be rotated or flipped in such a way that it becomes another.  So, for example, we would think that
\begin{align*}
\begin{array}{|c|c|c|c|}\hline
1 & 2 & 3 & 4 \\\hline
2 & 3 & 4 & 1 \\\hline
3 & 4 & 1 & 2 \\\hline
4 & 1 & 2 & 3 \\\hline
\end{array}, \qquad \begin{array}{|c|c|c|c|}\hline
4 & 3 & 2 & 1 \\\hline
1 & 4 & 3 & 2 \\\hline
2 & 1 & 4 & 3 \\\hline
3 & 2 & 1 & 4 \\\hline
\end{array}, \qquad \begin{array}{|c|c|c|c|}\hline
3 & 2 & 1 & 4 \\\hline
2 & 1 & 4 & 3 \\\hline
1 & 4 & 3 & 2 \\\hline
4 & 3 & 2 & 1 \\\hline
\end{array}
\end{align*}
are all equivalent, amongst others, as we can rotate the first by $90^\circ$ clockwise to get the second, and flip the second over its horizontal axis to get the third.

How many $4 \times 4$ Latin squares are distinct under this notion of equivalence?

\newpage




\item Consider the collection $\mathcal{P}_n$ of all partial $n \times n$ Latin squares.  So, for example, $P_2$ is the following set:
\begin{align*}
\mathcal{P}_2 = \Bigg\{ & \begin{array}{|c|c|}\hline 1 & 2 \\\hline 2 & 1 \\\hline \end{array}, \begin{array}{|c|c|}\hline  & 2 \\\hline 2 & 1 \\\hline \end{array}, \begin{array}{|c|c|}\hline 1 & \\\hline 2 & 1 \\\hline \end{array}, \begin{array}{|c|c|}\hline 1 & 2 \\\hline  & 1 \\\hline \end{array}, \begin{array}{|c|c|}\hline 1 & 2 \\\hline 2 &  \\\hline \end{array}, \begin{array}{|c|c|}\hline  &  \\\hline 2 & 1 \\\hline \end{array}, \begin{array}{|c|c|}\hline  & 2 \\\hline  \hphantom{1}& 1 \\\hline \end{array}, \begin{array}{|c|c|}\hline  & 2 \\\hline 2 &  \\\hline \end{array}, \\
& \begin{array}{|c|c|}\hline 1 &  \\\hline  & 1 \\\hline \end{array}, \begin{array}{|c|c|}\hline 1 & \\\hline 2 & \hphantom{1} \\\hline \end{array}, \begin{array}{|c|c|}\hline 1 & 2\\\hline  &  \\\hline \end{array}, \begin{array}{|c|c|}\hline 1 &  \hphantom{1}\\\hline &  \\\hline \end{array},  \begin{array}{|c|c|}\hline \hphantom{1} & 2 \\\hline  &  \\\hline \end{array},  \begin{array}{|c|c|}\hline  &\hphantom{1} \\\hline 2 &  \\\hline \end{array},  \begin{array}{|c|c|}\hline  \hphantom{1}&  \\\hline  & 1 \\\hline \end{array}, \begin{array}{|c|c|}\hline \hphantom{2} & ~ \\\hline ~ & \hphantom{2} \\\hline \end{array} ,\\
~~
& \begin{array}{|c|c|}\hline 2 & 1 \\\hline 1 & 2 \\\hline \end{array}, \begin{array}{|c|c|}\hline  & 1 \\\hline 1 & 2 \\\hline \end{array}, \begin{array}{|c|c|}\hline 2 & \\\hline 1 & 2 \\\hline \end{array}, \begin{array}{|c|c|}\hline 2 & 1 \\\hline  & 2 \\\hline \end{array}, \begin{array}{|c|c|}\hline 2 & 1 \\\hline 1 &  \\\hline \end{array}, \begin{array}{|c|c|}\hline  &  \\\hline 1 & 2 \\\hline \end{array}, \begin{array}{|c|c|}\hline  & 1 \\\hline  \hphantom{2}& 2 \\\hline \end{array}, \begin{array}{|c|c|}\hline  & 1 \\\hline 1 &  \\\hline \end{array}, \\
& \begin{array}{|c|c|}\hline 2 &  \\\hline  & 2 \\\hline \end{array}, \begin{array}{|c|c|}\hline 2 & \\\hline 1 & \hphantom{2} \\\hline \end{array}, \begin{array}{|c|c|}\hline 2 & 1\\\hline  &  \\\hline \end{array}, \begin{array}{|c|c|}\hline 2 &  \hphantom{2}\\\hline &  \\\hline \end{array},  \begin{array}{|c|c|}\hline \hphantom{2} & 1 \\\hline  &  \\\hline \end{array},  \begin{array}{|c|c|}\hline  &\hphantom{2} \\\hline 1 &  \\\hline \end{array},  \begin{array}{|c|c|}\hline  \hphantom{2}&  \\\hline  & 2 \\\hline \end{array}, \begin{array}{|c|c|}\hline \hphantom{2} & ~ \\\hline ~ & \hphantom{2} \\\hline \end{array} \Bigg\}.
\end{align*}
Consider the following relation $<$ that we can define on $\mathcal{P}_n$: for any two partial $n \times n$ Latin squares $P, Q \in \mathcal{P}_n$, define $P < Q$ if and only if $P \neq Q$ and every filled cell of $P$ is a filled cell of $Q$, containing the same values.  So, for example, we have $\begin{array}{|c|c|}\hline  & 2 \\\hline 2 &  \\\hline \end{array} < \begin{array}{|c|c|}\hline 1 & 2 \\\hline 2 &  \\\hline \end{array}$ because every filled cell on the left-hand side is filled in on the right with the same values.  However, $\begin{array}{|c|c|}\hline  & 2 \\\hline 2 &  \\\hline \end{array} \not< \begin{array}{|c|c|}\hline  &  \\\hline 2 & 1 \\\hline \end{array}$ because the left-hand side has cells filled in that are blank on the right, and $\begin{array}{|c|c|}\hline  & 2 \\\hline 2 &  \\\hline \end{array} \not< \begin{array}{|c|c|}\hline  & 1 \\\hline 1 & 2 \\\hline \end{array}$ because the filled cells on the left disagree with the filled cells at the right.

\begin{enumerate}
\item Prove that $\langle \mathcal{P}, <\rangle$ is a poset.
\item Suppose that $P, Q \in \mathcal{P}$ are two $n \times n$ partial Latin squares such that $P$ contains $k$ filled cells, $Q$ contains $l$ filled cells, and $P < Q$.  Find a closed formula for $\mu(P, Q)$, the M\"obius function on this poset, that depends only on $k$ and $l$.
\end{enumerate}


\end{enumerate}


\newpage



\section{Collaboration Section}
Do \textbf{two} of the four problems in this section!  All problems are on their own page.

\begin{enumerate}

\item Recall that a \textbf{partition} of the set $\{1, \ldots n\}$ is any way to write this set as the union of disjoint subsets of $\{ 1, \ldots n\}$.  So, for example, one partition of $\{1,2,3,4\}$ is $\{1,2\}, \{3\}, \{4\}$; another partition is $\{1\}, \{2,3,4\}$, and a third partition is $\{1,2,3,4\}$. 

Take $n \in \mathbb{N}$, and consider the set $\Pi_n$ consisting of all possible partitions of $\{1,\ldots n\}$.  So, for example,
\begin{align*}
\Pi_3 = \Bigg\{ \Big\{ \{1,2,3\} \Big\},  \Big\{ \{1,2\}, \{3\} \Big\},   \Big\{ \{1,3\}, \{2\} \Big\},  \Big\{ \{2,3\}, \{1\} \Big\},  \Big\{ \{1\}, \{2\} \{3\} \Big\} \Bigg\}
\end{align*}

Define the relation $<$ on this set as follows: for any two partitions $\alpha, \beta \in \Pi_n$, we have $\alpha < \beta$ if and only if $\alpha \neq \beta$ and every subset in $\beta$ can be written as the union of some blocks in $\alpha$.  So, for example, $\Big\{ \{1,2\}, \{3\}, \{4\} \Big\} < \Big\{ \{1,2\}, \{3,4\} \Big\}$, as we can write each set on the right as a union of sets on the left. As well, $\Big\{ \{1,2\}, \{3,4\} \Big\} \not< \Big\{ \{1,4\}, \{2,3\} \Big\}$, because we cannot write $\{1,4\}$ on the left as the union of any of the sets in $\{ \{1,2\}, \{3,4\} \Big\}$.
\begin{enumerate}
\item Show that this is a poset.  
\item Show that this is a lattice.
\item Show that for any $\alpha \in \Pi_n$, we have
\begin{align*}
\Big\{ \{1\}, \{2\}, \ldots \{n\} \Big\} \leq \alpha \leq \Big\{ \{1,2,\ldots n\} \Big\}.
\end{align*}
(In this sense our poset has a unique biggest element and unique smallest element. Name the minimal element $\Big\{ \{1\}, \{2\}, \ldots \{n\} \Big\} = \hat{0}$ and similarly name $\Big\{ \{1,2,\ldots n\} \Big\} = \hat{1}$ for shorthand.)

\item Let $\mu$ be the M\"obius function on this lattice.  Prove that 
\begin{align*}
\mu(\hat{0}, \hat{1}) = (-1)^{n-1} (n-1)!.
\end{align*}

(Hint: try using HW6, problem 2, on some easy-to-work-with value of $a$.)
\end{enumerate}

\newpage 


\item In class, I said that finding the exact number of distinct $n \times n$ Latin squares is an open problem.  However, you can get some pretty good lower bounds!  We do this here.
\begin{enumerate}
\item Suppose that $\mathcal{A} = \{A_1, \ldots A_n\}$ is a collection of subsets of $\{1, \ldots n\}$ such that the following holds: there is some natural number $k$ such that
\begin{itemize}
\item $|A_i| = k$ for every $i$.
\item For any $x \in \{1, \ldots n\}$, $x$ is in exactly $k$ of the sets $A_i$.
\end{itemize}
Prove that there are at least $k!$ different systems of distinct representatives for the sets $A_i$.  (Hint: induction!)


\item Use (a) to prove the following claim: if $L(n)$ denotes the number of distinct $n \times n$ Latin squares, show that
\begin{align*}
L(n) > n! \cdot (n-1)! \cdot \ldots \cdot 2! \cdot 1!.
\end{align*}
\end{enumerate}

\newpage 



\item For every $n \in \mathbb{N}$, consider the following poset $P_n$:
\begin{itemize}
\item Elements: $P$ consists of the following elements:
\begin{align*}
P = \{\hat{0}, \hat{1}\} \cup  \{a_1,a_2,\ldots a_n\} \cup \{b_1, b_2, \ldots b_n\}.
\end{align*}
\item Ordering: $\hat{0} \leq x$ for any $x \in P$; as well, $\hat{1} \geq x$ for any $x \in P$.  For the other elements, we make the following definitions:
\begin{itemize}
\item $a_i < a_j$ if and only if $i < j$.
\item $b_i < b_j$ if and only if $i < j$.
\item $a_i < b_j$ if and only if $i < j$.
\end{itemize} 
In particular, notice that $b_j \not< a_i$ for any $a_i, b_j$.
\end{itemize}
To give a concrete example, we draw $P_3$'s diagram here:
\begin{center}
\includegraphics[width=2in]{poset_pic.pdf}
\end{center} 

Find a nice closed form, dependent only on $n$, for the number of linear extensions\footnote{From HW4: a \textbf{linear extension} of a finite poset $P$ on $n$ elements is a bijective map $f: P \to \{1,2,\ldots n\}$, such that if $x < y \in P,$ then $f(x) < f(y).$} of $P_n$.


\newpage 



\item Take an arbitrary finite group $\langle G, \cdot \rangle$ containing $n$ elements, and let $e$ denote the identity element in this group.  For any number $m \in \mathbb{N}$, let $X$ denote the collection of all ordered $m$-tuples of elements $(g_0, g_1, \ldots g_{m-1})$ such that $g_0 \cdot g_1 \cdot \ldots g_{m-1} = e$.  

For example, let $G = D_6 = \{e, r_{120}, r_{240}, f_{\includegraphics[scale=.04]{triangle_sym1.pdf}},  f_{\includegraphics[scale=.04]{triangle_sym2.pdf}}, f_{\includegraphics[scale=.04]{triangle_sym3.pdf}} \}, $ the dihedral group given by the symmetries of a triangle, and let $m = 2$.  Then $X$ is the following set:
\begin{align*}
X = \big\{(e, e), (r_{120}, r_{240} ), (r_{240}, r_{120}),  (f_{\includegraphics[scale=.04]{triangle_sym1.pdf}},f_{\includegraphics[scale=.04]{triangle_sym1.pdf}}),   (f_{\includegraphics[scale=.04]{triangle_sym2.pdf}},f_{\includegraphics[scale=.04]{triangle_sym2.pdf}}),  (f_{\includegraphics[scale=.04]{triangle_sym3.pdf}},f_{\includegraphics[scale=.04]{triangle_sym3.pdf}}),\big\}.
\end{align*}

\begin{enumerate}
\item How many elements are in $X$?  You should find an expression for the size of $X$ that depends only on $n$ and $m$.
\item Let $\mathbb{Z}/m \mathbb{Z}$ act on $X$ as follows: for any $k \in \mathbb{Z}/m\mathbb{Z}$, define 
\begin{align*}
k \star (g_0, \ldots g_{m-1}) = (g_{0+k \mod m}, g_{1 + k \mod m}, \ldots g_{(m-1)+ k \mod m}).
\end{align*}
 Show\footnote{Be aware that $G$ may not be a commutative group; i.e. in general, $g \cdot h \neq h \cdot g$.  This makes your proof a little (but not much) trickier than it may seem at first.} that this is a group action.  
\item By using the above group action, prove the following claim: if $G$ is a group of order $n$ and $p$ is a prime that divides $n$, then there is some $g \in G$, $g \neq e$, with $g^p = e$.
\end{enumerate} 


\end{enumerate}
\newpage



\section{Extra-Credit Section}

\begin{enumerate}
\item Take any $n \in \mathbb{N}$, and form the Boolean lattice $B_n$ made out of all of the subsets of $\{1, \ldots n\}$ ordered by inclusion, as described in the notes.  Consider the following two-player game that we can play on $B_n$:
\begin{itemize}
\item There are two players, player 1 and player 2. Player 1 goes first, and the players alternate turns until the game is done.
\item On a player's turn, they pick out an element on the lattice and delete it, along with every element ``beneath'' that element (i.e.\ if a player picks out $x$, they delete $x$ and every $y < x$ from our lattice.)
\item The game ends when someone takes the ``top'' element $\{1, \ldots n\}$ in our lattice; the person who does this loses the game.
\end{itemize}
For example, when $n=2,$ player 1 can always win with perfect play.  On the poset
\footnotesize
\begin{align*}
\xymatrix @R1em@C1em{
&\{1,2\}\ar@{-}[rd] \ar@{-}[ld]&\\
\{1\} \ar@{-}[rd] & & \{2\}  \ar@{-}[ld]\\
&\emptyset &
}
\end{align*}\normalsize
player 1 can always open by taking $\emptyset$.  Player 2 can then either respond by taking $\{1,2\}$ and thus losing (as this removes all of the entries in the lattice) or either of $\{1\}, \{2\}$.  In the latter case, player 1 can just take whichever single-element set player 2 did not take, which leaves player 2 with no choice but to take $\{1,2\}$ and lose.

\begin{enumerate}
\item Play me in this game, either in office hours or via email, on $B_4$:\footnotesize
\begin{align*}
\xymatrix @R1em@C1em{
&&&\{1,2, 3, 4\}\ar@{-}[rd] \ar@{-}[rrd] \ar@{-}[ld] \ar@{-}[lld]&&&\\
&\{1, 2, 3\} \ar@{-}[ld] \ar@{-}[d]  \ar@{-}[rd]& \{1,2,4\} \ar@{-}[lld] \ar@{-}[rrd] \ar@{-}[rrrd]& & \{1,3,4\} \ar@{-}[llld] \ar@{-}[d] \ar@{-}[rrd]& \{2,3,4\} \ar@{-}[llld] \ar@{-}[d] \ar@{-}[rd]&\\
\{1,2\} \ar@{-}[rd] \ar@{-}[rrd]& \{1,3\} \ar@{-}[d] \ar@{-}[rrrd]& \{2,3\} \ar@{-}[d] \ar@{-}[rrd] && \{1,4\} \ar@{-}[llld]  \ar@{-}[rd]& \{2,4\} \ar@{-}[llld] \ar@{-}[d]& \{3,4\} \ar@{-}[lld] \ar@{-}[ld] \\
& \{1\} \ar@{-}[rrd]& \{2\} \ar@{-}[rd]&& \{3\} \ar@{-}[ld]& \{4\} \ar@{-}[lld] \\
&&&\emptyset &&&
}
\end{align*}\normalsize
You can decide to go first or second.  You get credit for this problem if and only if you win. Only one attempt per person.
\item In general: can player 1 win with perfect play in this game for any $n$?  Or is there some $n$ such that player 2 can win with perfect play?
\end{enumerate}
\end{enumerate}
\end{document}