Devil's Chessboard

\documentclass[12pt]{article}

\usepackage{graphicx}
\usepackage{fullpage}

\title{The Devil's Chessboard Solution}
\author{Garyados Oak}
\date{June 17, 2013}
\begin{document}
\maketitle

\section{Choosing Some Useful Groups}
We shall begin by finding a set of six groups of squares such that the intersection of any n groups will contain $\frac{64}{2^n}$ squares. Our motivation is to find a group where we can ask the question "Is the magic square in this group?" and regardless of the answer, we've ruled out half of our squares.


\textsc{Group 1} - This is simply the top half of our chessboard.

\begin{center}\includegraphics[scale=0.5]{group1.jpg}
\end{center}

\textsc{Group 2} - This is the left half of the chessboard.

\begin{center}\includegraphics[scale=0.5]{group2.jpg}
\end{center}

\textsc{Group 3} - This is every other double row.

\begin{center}\includegraphics[scale=0.5]{group3.jpg}
\end{center}

\textsc{Group 4} - This is every other double column.

\begin{center}\includegraphics[scale=0.5]{group4.jpg}
\end{center}

\textsc{Group 5} - This is every other single row.

\begin{center}\includegraphics[scale=0.5]{group5.jpg}
\end{center}

\textsc{Group 6} - This is every other single column.

\begin{center}\includegraphics[scale=0.5]{group6.jpg}
\end{center}

\section{Mapping a Square}{}
It just so happens (by construction) that every square has a unique set of groups to which it belongs (i.e. There is a bijection between the set of squares and the powerset of the set containing our 6 groups). So can represent each square by a string of 0s and 1s where the nth digit is 1 if that square is in group n and 0 otherwise. Consider d7:
\begin{center}\includegraphics[scale=0.5]{d7.jpg}
\end{center}

\begin{itemize}
\item It is in Group 1.
\item It is in Group 2.
\item It is in Group 3.
\item It is \textbf{not} in Group 4.
\item It is \textbf{not} in Group 5.
\item It is \textbf{not} in Group 6.
\end{itemize}

Thus d7 can be represented by 111000.

\section{Pointing to the Magic Square}

The trick to solving our problem is in manipulating the number of heads in each group so that counting them lets our friend know which square is the magic one.

First, find the string that represents the magic square like we did for d7 at the end of the previous section. Our goal is to make sure that if the magic square is in Group n, then group n has an odd number of heads, and an even number otherwise. Then our friend will take the set of Groups with an odd number and find the single square that lies only in those groups, and not in the groups that are even.

There are two types of groups we need to change, groups that should be odd, but aren't, and groups that are odd, but shouldn't be. Find the square that lies in all of these groups, and not in any of the other groups that are already correct. Switch the face on that coin and it will correct all the incorrect groups. The groups that were already correct will be unaffected since this square does not lie in those groups.

Now, when your friend comes in and count up each group and notice, "Group 1 is odd. Group 2 is odd. Group 3 is odd. Group 4 is even. Group 5 is even. Group 6 is even." So the magic square lies in Group 1:

\begin{center}
\includegraphics[scale=0.5]{group1.jpg}\\
\textsc{Group 1}
\end{center}

And it lies in Group 2:
\begin{center}
\includegraphics[scale=0.5]{group12.jpg}\\
\textsc{Group 1} $\cap$ \textsc{Group 2}
\end{center}

And lies in Group 3:
\begin{center}
\includegraphics[scale=0.5]{group123.jpg}\\
\textsc{Group 1} $\cap$ \textsc{Group 2} $\cap$ \textsc{Group 3}
\end{center}

But doesn't lie in Group 4:
\begin{center}
\includegraphics[scale=0.5]{group1234.jpg}\\
(\textsc{Group 1} $\cap$ \textsc{Group 2} $\cap$ \textsc{Group 3}) $\setminus$ \textsc{Group 4}
\end{center}

Nor does it lie in Group 5:
\begin{center}
\includegraphics[scale=0.5]{group12345.jpg}\\
(\textsc{Group 1} $\cap$ \textsc{Group 2} $\cap$ \textsc{Group 3}) $\setminus$ (\textsc{Group 4} $\cup$ \textsc{Group 5})
\end{center}

And nor does lie in Group 6:
\begin{center}
\includegraphics[scale=0.5]{group123456.jpg}\\
(\textsc{Group 1} $\cap$ \textsc{Group 2} $\cap$ \textsc{Group 3}) $\setminus$ (\textsc{Group 4} $\cup$ \textsc{Group 5} $\cup$ \textsc{Group 6})
\end{center}

Thus the magic square must be d7! In this example, at least.

\section{Putting it all Together}

\textbf{Your Turn.}
You enter the room and the devil shows you his chessboard and tells you which square is the magic square. Your instructions are:

\begin{enumerate}
\item The Lists A and B are two empty lists of groups.
\item For each of the six groups:
\begin{enumerate}
\item If the magic square is in the group and the number of heads in the group is even. Add the group to List A.
\item If the magic square is the group and the number of heads in the group is odd. Add the group to List B.
\item If the magic square is \textbf{not} in the group and the number of heads in the group is odd. Add the group to List A.
\item If the magic square is \textbf{not} in the group and the number of heads in the group is even. Add the group to List B.
\end{enumerate}
\item Find the square that is in all of the groups in List A and not in any of the groups in List B.
\item Flip the coin in that square.
\end{enumerate}

\textbf{Your Friend's Turn.} He enters the room and sees the board. His instructions are:

\begin{enumerate}
\item The Lists A and B are two empty lists of groups.
\item For each of the six groups:
\begin{enumerate}
\item If the number of heads in the group is odd, add it to list A.
\item If the number of heads in the group is even, add it to list B.
\end{enumerate}
\item Find the square that is in all of the groups in List A and not in any of the groups in List B.
\item That is the magic square.
\end{enumerate}

\end{document}