\documentclass[11pt]{article}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{hhline}
\usepackage{multicol}
\usepackage{latexsym}
\usepackage{hhline}
\usepackage[table]{xcolor}
\usepackage{verbatim}
\usepackage[pdftex]{graphicx}
\usepackage{enumerate}
\usepackage{url}
\usepackage{color}
\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};}}
            
            \def\zero{\multicolumn{1}{>{\columncolor{white}}c}{0}}

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

\begin{document}

\homework{8: Latin Squares}{Due Friday, Week 10}


This set is different, because it's the last week.  You have just \textbf{one} section here: it's the collaboration section!  There are \textbf{four} problems here.  Do \textbf{at least two} here to receive full credit.  

If you're looking for extra credit, though, attempt \textbf{more}!  Unlike normally, all of the problems you attempt will be graded.  Problems beyond your highest two scoring problems will count for half a point; i.e. the maximum score on the HW set is $150\%.$   

Have fun!


\section{Collaboration Section}

\begin{enumerate}
\item Given a $n \times n$ Latin square $L$, a $k \times k$ \textbf{subarray} $M$ of $L$ is any subset of $k$ of $L$'s rows and $k$ of its columns; this gives us a $k \times k$ array by simply taking all of the cells of $L$ that are contained within the intersection of these rows and columns.

A $k \times k$ subarray is called a \textbf{subsquare} if it is a Latin square in its own right; i.e. it is a $k \times k$ square filled with $k$ different symbols with no repeats in any row or column.  So, for example, 
\begin{align*} 
\begin{array}{|c|c|c|c|c|c|}
\hline \cellcolor{blue!25}1 & 2 & 3 & 4 & \cellcolor{blue!25}5 & 6\\
\hline 3& 1 & 2 & 6 & 4 & 5\\
\hline 2& 3 & 1 & 5 & 6 & 4\\
\hline 4 & 6& 5 & 1 & 3 & 2\\
\hline \cellcolor{blue!25} 5& 4 & 6 & 2 &\cellcolor{blue!25} 1 & 3\\
\hline 6& 5 & 4 & 3 & 2 & 1\\
\hline
\end{array}
\end{align*}
is a $6 \times 6$ Latin square containing a $2 \times 2$ subsquare.
\begin{enumerate}
\item For any prime $n$, find a $n \times n$ Latin square that contains no $k \times k$ subsquare, for any $1 < k < n$.
\item Show that if $L$ is a $n \times n$ Latin square that contains a $k \times k$ subsquare $M$, then either $k \leq n/2$ or $k = n$.
\end{enumerate}

\item Given a group $\langle G, \cdot \rangle$ containing $n$ elements $g_1, g_2, \ldots g_n$, a \textbf{group table} for $G$ consists of the $n \times n$ table where we put $g_i \cdot g_j$ in the entry $(i,j)$:
\begin{align*}
\begin{array}{c||c|c|c|c|}
g_i \cdot g_j & g_1 & g_2 & \ldots & g_n \\\hhline{=#====|}
g_1 & g_1 \cdot g_1 & g_1 \cdot g_2 & \ldots & g_1 \cdot g_n \\\hline
g_2 & g_2 \cdot g_1 & g_2 \cdot g_2 & \ldots & g_2 \cdot g_n \\\hline
\vdots & \vdots & \vdots & \ddots & \vdots \\\hline
g_n & g_n \cdot g_1 & g_n \cdot g_2 & \ldots & g_n \cdot g_n \\\hline
\end{array}
\end{align*}

For example, consider the set $(\mathbb{Z}/2\mathbb{Z})\times(\mathbb{Z}/2\mathbb{Z})$, otherwise denoted as $(\mathbb{Z}/2\mathbb{Z})^2$.  This set has four elements: $(0,0), (0,1), (1,0), (1,1)$, and is a group under the operation of ``pairwise addition mod 2.''  It has the following group table:
\begin{align*}
\begin{array}{c||c|c|c|c}
+  & (0,0) & (1,1) & (1,0) & (0,1) \\\hhline{=#====}
(0,0) & (0,0)& (1,1)& (1,0)&(0,1)\\\hline
(1,1) & (1,1) & (0,0) & (0,1)& (1,0)\\\hline
(1,0) &(1,0)& (0,1)& (0,0)& (1,1)\\\hline
(0,1) & (0,1)& (1,0)& (1,1)& (0,0)\\
\end{array}
\end{align*}
\begin{enumerate}
\item Show that if you ignore the row and column labels, the $n \times n$ table given by the group table of any group is a Latin square.
\item Is is true that for any Latin square, there is a corresponding group $G$ and enumeration of $G$'s elements?  Or is this false: i.e. can you find a Latin square $L$ such that no group $G$ can possibly correspond to this square?
\end{enumerate}

\item This problem introduces the idea of ``orthogonality'' for Latin squares: 
\begin{enumerate}
\item Take the 16 aces, kings, queens, and jacks from a deck of playing cards.  Can you arrange these 16 cards into a $4 \times 4$ array, so that in each column and row, no two cards share the same suit or same face value?
\item A pair of $n \times n$ Latin squares are called \textbf{mutually orthogonal} if when we superimpose them (i.e. place one on top of the other), each of the possible $n^2$ ordered pairs of symbols occur exactly once.  So, in the problem above, you basically created a pair of mutually orthogonal $4 \times 4$ Latin squares.  

Does every Latin square have an orthogonal mate?  That is: for any Latin square $L$, can you find a Latin square $M$ such that $L, M$ are orthogonal?
\end{enumerate}

\item For every $n \in \mathbb{N}$, find a $2n \times 2n$ partial Latin square $P$ such that
\begin{itemize}
\item no row, column, or symbol is used more than $n+1$ times in total, and
\item $P$ cannot be completed to a Latin square.
\end{itemize}

To give an example:
\begin{align*}
P = \begin{array}{|c|c|c|c|}\hline
1 & 2 & 3 & \\\hline
   & 3 & 4 & 2 \\\hline
3 & 4 & 1 & \\\hline
2 &    &    &  4 \\\hline
\end{array}
\end{align*}
is a $4 \times 4$ partial Latin square in which no row is used more than three times in total (i.e. no row contains more than three nonblank cells,) no column is used more than three times in total, and no symbol is used in the entire square more than three times in total.

\end{enumerate}




\end{document}

