\documentclass{article}
\input{../notes/preamble.tex}
\usepackage{url,colortbl,hhline}
\title{Assignment 1}
\date{Friday May 25, 2012}
\newcommand{\df}{\textbf}
\newcolumntype{M}{>{\columncolor{white}}c!{\color{black}\vline}}
\begin{document}
\maketitle
This is Assignment 1. The problems are arranged in the natural order which we learn the material. You should do as much as you can everyday, but if you don't recognize something that means we probably have learned that material yet.
{\bf Remember to show all work, and argue any claim, unless otherwise stated. Getting a correct answer does not suffice}
This assignment is due Friday May 25.
\section{Puzzles}
It is intended for you to complete this section on Monday May 21.
\subsection{Return to Smullyan Island}
Recall that on the island of Smullyan Island, all people are either Knights or Knaves. Knights always tell the truth, and Knaves always lie.
After visiting the island, you told many of your friends about the amazing time you had. Word spread quickly, and the island has become overrun with tourists! Tourists, like you, can choose to either lie or tell the truth. You return the island, and are more confused than ever!
For the following, give your answer and an argument.
\begin{prob}
You encounter a young child on the island who is repeatedly yelling, "I'm a Knave!" What can you say about the child, aside from the fact he is annoying?
\end{prob}
\begin{prob}
You encounter a group of three people: Albert, Betty, and Catherine. You know one is a knight, another a knave, and another a tourist, although you don't know which is which. Albert tells you that Catherine is a Knave, but Catherine insists she is a tourist. Betty, in order to help clear this confusing situation up, tells you that Albert is a Knight. Who is who?
\end{prob}
\subsection{More with Chessboards}
\begin{prob}
Take a 8x8 chessboard, and remove two adjacent squares from each corner. Can you cover the board with T-shaped tetrominoes (tetris pieces)? If so, how? If not, why not? (See picture)
\begin{center}
\begin{tabular}{c c}
\begin{minipage}{1.75in}
\begin{tabular}{!{\color{black}\vline} M M M M M M M M }
\hhline{~~------}
\multicolumn{2}{c}{\cellcolor[gray]{1}}&\cellcolor[gray]{0}&&\cellcolor[gray]{0}&&\cellcolor[gray]{0}& \\
\hline
&\cellcolor[gray]{0}&&\cellcolor[gray]{0}&&\cellcolor[gray]{0}&&\cellcolor[gray]{0} \\
\hline
\cellcolor[gray]{0}&&\cellcolor[gray]{0}&&\cellcolor[gray]{0}&&\cellcolor[gray]{0}& \\
\hline
&\cellcolor[gray]{0}&&\cellcolor[gray]{0}&&\cellcolor[gray]{0}&&\cellcolor[gray]{0} \\
\hline
\cellcolor[gray]{0}&&\cellcolor[gray]{0}&&\cellcolor[gray]{0}&&\cellcolor[gray]{0}& \\
\hline
&\cellcolor[gray]{0}&&\cellcolor[gray]{0}&&\cellcolor[gray]{0}&&\cellcolor[gray]{0} \\
\hline
\cellcolor[gray]{0}&&\cellcolor[gray]{0}&&\cellcolor[gray]{0}&&\cellcolor[gray]{0}& \\
\hline
&\cellcolor[gray]{0}&&\cellcolor[gray]{0}&&\cellcolor[gray]{0}&\multicolumn{2}{c}{} \\
\hhline{------~~}
\end{tabular}
\end{minipage}
&
\begin{minipage}{1in}
\begin{tabular}{ | c | c | c | }
\hline
& & \\
\hline
\multicolumn{1}{l|}{} & &\multicolumn{1}{r}{} \\
\cline{2-2}
\end{tabular}
\end{minipage}
\end{tabular}
\end{center}
\end{prob}
\newpage
\begin{prob}
A bee is on the corner of a cubic bird house (the front is shown below) at noon. Every 5 minutes, the bee moves from one corner of the bird house to a neighboring corner. He would like to be at the corner of the cube opposite to the one that he started at 12:32. Note that opposite corners of a cube are ones which are across a interior diagonal of the cube. Is it possible? If so, how? If not, why not?
\begin{center}
\setlength{\unitlength}{4144sp}%
%
\begingroup\makeatletter\ifx\SetFigFont\undefined%
\gdef\SetFigFont#1#2#3#4#5{%
\reset@font\fontsize{#1}{#2pt}%
\fontfamily{#3}\fontseries{#4}\fontshape{#5}%
\selectfont}%
\fi\endgroup%
\begin{picture}(2093,2325)(211,-1696)
\thinlines
{\color[rgb]{0,0,0}\put(901,-61){\line( 0,-1){1350}}
\put(901,-1411){\line( 1, 0){1350}}
\put(2251,-1411){\line( 0, 1){1350}}
\put(2251,-61){\line(-1, 0){1350}}
\put(901,-61){\line( 0, 1){ 0}}
}%
{\color[rgb]{0,0,0}\put(901,-1411){\line(-1, 1){450}}
\put(451,-961){\line( 0, 1){1350}}
\put(451,389){\line( 1,-1){450}}
\put(901,-61){\line( 0,-1){1350}}
}%
{\color[rgb]{0,0,0}\put(451,389){\line( 1,-1){450}}
\put(901,-61){\line( 1, 0){1350}}
\put(2251,-61){\line(-1, 1){450}}
\put(1801,389){\line(-1, 0){1350}}
\put(451,389){\line( 0, 1){ 0}}
}%
{\color[rgb]{0,0,0}\put(451,389){\circle{90}}
}%
{\color[rgb]{0,0,0}\put(2251,-1411){\circle{90}}
}%
\put(226,479){\makebox(0,0)[lb]{\smash{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}Start}%
}}}}
\put(2161,-1681){\makebox(0,0)[lb]{\smash{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}End}%
}}}}
\end{picture}%
\end{center}
\end{prob}
\section{Inequalities}
It is intended for you to complete this section on Tuesday May 22.
\subsection{Understanding}
\begin{prob}
You are planning a party! (No work is necessary for these problems, just the inequalities)
\begin{enumerate}
\item Let $c$ be the number of chairs, and $t$ be the number of tables. Write an inequality that says, ``We have at least four times as many chairs as tables.''
\item Let $p$ be the number of people at your party. Write an inequality that says, ``There are enough tables so that no more than 6 people are at one table."
\item Write an inequality to relate chairs to tables.
\end{enumerate}
\end{prob}
\subsection{AGM}
Recall that the AGM inequality states that for $x,y \geq 0$ we have that
\[
\sqrt{xy} \leq \frac{x+y}{2}
\]
\begin{prob}
Prove the AGM inequality for the arithmetic mean and geometric mean of $4$ non-negative reals. That is, prove, for all $a,b,c,d > 0$:
\[
\sqrt[4]{abcd} \leq \frac{a + b + c + d}{4}
\]
\end{prob}
\section{Logic}
It is intended for you to complete this section on Wednesday May 23.
\subsection{Some Proofs}
\begin{prob} \label{easy_proofs}
Prove the following:
\begin{enumerate}
\item $(A\oand B) \to (A\to B)$
\item $ (A\oand B) \to (( (A\to C) \oor (B\to C) ) \to C)$
\item $ (A \oor B) \to ( \neg A \to B )$
\end{enumerate}
\end{prob}
\begin{prob}
Prove the following:
\begin{enumerate}
\item $( A\to (B\to C) ) \to ((A\oand B) \to C)$
\item $((A\oand B) \to C) \to ( A\to (B\to C) )$
\item Consider the following statement:
\begin{itemize}
\item If $x$ is a positive real number, then if $y>1$ we have $xy > x$.
\end{itemize}
Restate this statement using the logical equivalence proved above. (No work is necessary for this part, just the restatement)
\item Give your own example of a statement which can be rephrased using this equivalence.
\end{enumerate}
\end{prob}
\section{Logical Semantics}
It is intended for you to complete this section on Thursday May 24.
\subsection{Contrapositives}
\begin{prob}
Write the contrapositive and converse of the following English sentences. (No work is necessary for these problems, just the sentences)
\end{prob}
\begin{enumerate}
\item If a person is short then they are not tall.
\item It rains if it pours.
\item Whenever I see a painting by Van Gogh, I think that it is beautiful.
\item I can't take you if the car is full.
\item I can take you if the car isn't full.
\end{enumerate}
\subsection{Truth Tables}
\begin{prob}
Write truth tables for Problem \ref{easy_proofs} to verify they are true (No work is necessary for this problem, just the truth tables)
\end{prob}
\end{document}