% This is a TeX file
% It is essentially a programming language for mathematics documents
% You can ignore this first portion of the file, as it is essentially a bunch of "include" statements.
\documentclass[10pt]{article}

\usepackage{pictex, latexsym, graphicx,amsmath,amssymb,amsbsy,amsfonts,amsthm,verbatim}
\usepackage{graphics}
\usepackage{fullpage}
\usepackage{fancyhdr}
\usepackage{hyperref}

\usepackage{algorithm,algorithmic}
\usepackage{multirow}

\setlength{\voffset}{-0.25in}
\setlength{\headsep}{0.25in}
\setlength{\parskip}{1em}
\setlength{\parindent}{0em}

% The following denotes a counter for the problems.
\newcounter{problem}
\newcommand{\problem}{\textbf{\refstepcounter{problem}Problem \theproblem.} }

% These are macro shortcuts! Helpful!
\def\vu{\mathbf{u}}
\def\vx{\mathbf{x}}
\def\vb{\mathbf{b}}
\def\vv{\mathbf{v}}
\def\vw{\mathbf{w}}

\renewcommand{\implies}{\rightarrow}
\renewcommand{\lor}{\vee}
\renewcommand{\land}{\wedge}
\newcommand{\xor}{\oplus}
\renewcommand{\iff}{\leftrightarrow}
\newcommand{\TRUE}{\mathbf{T}}
\newcommand{\FALSE}{\mathbf{F}}
\newcommand{\universe}{\mathcal{U}}

\begin{document}
\pagestyle{fancyplain}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% NOW you can start typing your text that will appear in the PDF!!!

% Note that anything after a '%' is a comment!

% Anything immediately after a '\' is a command. 
% Some denote formatting, some are for special characters.
% The '$' symbol starts and ends "math mode". Use this only for mathematical statements
% In math mode, any sequence of letters is meant to be a list of variables, so use "\sin x" for the sine of x, which will look much different from "sin x"
\chead{COM S 330 --- Homework 04 --- INSERT NAME HERE}

\textit{Type your answers to the following questions and submit a PDF file to Blackboard. 
One page per problem.}


% Problems about Proofs!
\problem [5pts] Give a direct proof of the following statement: If $x$ and $y$ are rational numbers, then $x + y$ and $xy$ are rational numbers.

% Be sure to use this \clearpage to make sure your problems are on separate pages!
%\clearpage
\problem [5pts] Give a proof of the following statement: If $x$ is a rational number and $y$ is irrational, then $x+y$ and $xy$ are irrational.



% Be sure to use this \clearpage to make sure your problems are on separate pages!
%\clearpage
\problem [5pts] Prove that $\sqrt{35}$ is irrational.


% Be sure to use this \clearpage to make sure your problems are on separate pages!
%\clearpage
\problem [10pts]  In the country of Togliristan (where Knights, Knaves, and Togglers live), Togglers will alternate between telling the truth and lying (no matter what other people say). You meet two people, $A$ and $B$.
They say, in order:
\begin{quote}
$A$ : $B$ is a Knave.

$B$ : $A$ is a Knave.

$A$ : $B$ is a Knight.

$B$ : $A$ is a Toggler.
\end{quote}
Determine what types of people $A$ and $B$ are.



% Be sure to use this \clearpage to make sure your problems are on separate pages!
%\clearpage
\problem [15pts] The \emph{L-shaped Tetris piece} (or \emph{tetromino}, see \href{http://en.wikipedia.org/wiki/Tetromino}{the Wikipedia page}) consists of four squares: three of which are in a line and a fourth attached to one end of that line. See the figure below for all of the arrangements of the L-shaped Tetris piece (or L-piece).

% If you are using this TeX file for your homework, you will want to comment this out!
\begin{center}
\includegraphics[height=0.5in]{figures/tetrominoes-L}
\end{center}

Adapt the proofs from the book and class about domino tilings to prove the following:

\textbf{a.} [5pts] If $m$ is an even number and $n$ is a multiple of 4, then the $m \times n$ chessboard can be tiled using L-pieces.

\textbf{b.} [5pts] If a chessboard has a tilling using L-pieces, then the chessboard has a domino tiling.

\textbf{c.} [5pts] If $m$ and $n$ are odd numbers, then the $m\times n$ chessboard cannot be tiled using L-pieces. 

\textbf{d.} [Bonus] Consider a $3 \times 4k$ chessboard. 

[2pts] Show that if $k$ is even, then the $3 \times 4k$ chessboard can be tiled using L-pieces. 

[3pts] Show that if $k$ is odd, then the $3 \times 4k$ chessboard \emph{cannot} be tiled using L-pieces.
(Hint: For the odd case, you may need the principle of \emph{strong induction}. In short: Prove that you cannot tile a $3 \times 4$ chessboard, then assume that there is no tiling of a $3 \times 4\ell$ chessboard for all odd $\ell < k$, and use that to prove there is no tiling of a $3 \times 4k$ chessboard. THIS IS HARD.)



\end{document} 