\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}{.25in}
\setlength{\evensidemargin}{.25in}
\setlength{\textwidth}{6in}
\setlength{\topmargin}{-0.4in}
\setlength{\textheight}{8.5in}

\input{preamble.tex}

\begin{document}
\pagenumbering{gobble}
\clearpage
\thispagestyle{empty}
\homework{2: Error-Correcting Codes}{Due Tuesday, Week 2}

Try some of the problems below!  As always, work on problems here until you've spent at least 90 minutes on this set.  Show your work, so that I can see that you've spent time/effort on this!

\begin{enumerate}
\item Here's a fun problem from a UCSB mathematics Ph.D. student\footnote{Todd Ebert, 1998.  The silly framing is me.} from their dissertation:
\begin{quest}
You and two friends have been captured by eeeeevil logicians!  They tell you ahead of time about the following puzzle they have for you:\
\begin{itemize}
\item You will all be led into a locked room.
\item Each person will have a hat placed on their head; hats are either black or white, and randomly decided for each person by flipping a fair coin.  
\item No one can see their own hat.
\item Each person can see other people's hats.
\item You and your friends cannot communicate once in the room.  
\item When the guards say so, you and your friends must all either guess (simultaneously) the color of their own hat, or say ``pass.''
\item If at least one person guesses correctly and no one is incorrect, you're free!
\item If anyone guesses incorrectly, you are sad/eaten by bears.
\end{itemize}
Find a strategy that insures that on average, you are not eaten by bears three-quarters of the time.
\end{quest}
\item Historically, one of the first codes developed was the Hamming $[7,4]$ code.  It works like this: take any string of four bits (i.e. any string of four 0's and 1's.)  Turn this into a string of seven bits in the following way:
\begin{itemize}
\item Place the bits of the original message, in order, in the slots $3,5,6,7$.
\item In slot 1, put the parity\footnote{The parity of a number $n$ is just $n \mod 2$.  In other words, it is 1 if $n$ is odd, and 0 if $n$ is even.}  of the sum of the bits in slots $3,5,7$.
\item In slot 2, put the parity of the sum of the bits in slots $3,6,7$.
\item In slot 4, put the parity of the sum of the bits in slots $5,6,7$.
\end{itemize}
For example, to encode the message 1010, we would first place
\begin{align*}
\_\_1\_010;
\end{align*}
then, because $1+0+0 = 1, 1+1+0 = 0, 0+1+0 = 1$, we would fill in the remaining slots to get 
\begin{align*}
1011010.
\end{align*}
This is a 2-ary code of length 7.  Find its information density and its minimum distance.  


\end{enumerate}


\end{document}