\documentclass[11pt]{article}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{latexsym}
\usepackage{verbatim}
\usepackage[pdftex]{graphicx}
\usepackage{url}
\usepackage[table]{xcolor}
\usepackage[all,arc]{xy}
\usepackage{color, colortbl}
\usepackage{mathrsfs}
\usepackage{hyperref}
\hypersetup{colorlinks=true}
\setlength{\oddsidemargin}{.15in}
\setlength{\evensidemargin}{.15in}
\setlength{\textwidth}{6.2in}
\setlength{\topmargin}{-0.5in}
\setlength{\textheight}{8.6in}


\input{preamble.tex}

\begin{document}

\homework{9: Latin Squares}{Due Tuesday, week 10, at the start of class}


\section*{Checkdown problem}
Prove one of the two problems below!

\begin{enumerate}
\item In class, we made the following claim.  Prove it!
\begin{claim}
Suppose that $n$ is a prime number.  Then $\langle \mathbb{Z}/n\mathbb{Z}, +, \cdot\rangle$ has the following property: 
\begin{center}
For any $a, b \in \{0, \ldots n-1\}$, if $a \cdot b \equiv 0 \mod n$, then at least one of $a, b$ are equal to 0.
\end{center}
\end{claim}
\item In class, we made the following claim.  Prove it!
\begin{claim}
Suppose that $n$ is a prime.  Take any $ a \in \mathbb{Z}/n\mathbb{Z}$.  If $a \neq 0$. then there is some $b \in \mathbb{Z}/n\mathbb{Z}$ such that $a \cdot b = 1$.
\end{claim}
\end{enumerate}

\section*{Extra-credit problems}

\begin{enumerate}
\item In class, every pair of orthogonal Latin squares were related to each other by simple row permutations: that is, if $L$ and $M$ were orthogonal, then we could turn $L$ into $M$ by switching the rows of $L$ around.  

Prove that this is not true for all Latin squares!  That is: find a pair of mutually orthogonal Latin squares $L, M$ such that you cannot switch the rows of $L$ around to get $M$.

\item Given a pair of mutually orthogonal Latin squares $(A,B)$ of order $m$ and another pair of mutually orthogonal Latin squares $(C,D)$ of order $n$, create a pair of mutually orthogonal Latin squares $(X, Y)$ of order $mn$.
\item Write a computer program that, given inputs $n, k$, will try to find $k$ mutually orthogonal Latin squares of order $n$.  For what values of $n, k$ does your program finish running in (say) under half a hour?
\end{enumerate}

\end{document}