% 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 --- Solutions}

\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.

\begin{proof}
Let $x$ and $y$ be rational numbers.
By definition, there exist integers $p$ and $q$ with $q \neq 0$ such that $x = \frac{p}{q}$.
By definition, there exist integers $j$ and $k$ with $k \neq 0$ such that $y = \frac{j}{k}$.
Then,
\[
	x + y = \frac{p}{q}+\frac{j}{k} = \frac{kp + qj}{qk}, \quad
	\text{ and }
	\quad
	xy = \frac{p}{q}\cdot \frac{j}{k} = \frac{pj}{qk}.
\]
Since $q \neq 0$ and $k \neq 0$, $qk \neq 0$.
Since $p,q,j,k$ are integers, the values $kp+qj$ and $pj$ are integers.
Thus, $x+y = \frac{kp+qj}{qk}$ is a rational number and $xy = \frac{pj}{qk}$ is a rational number.
\end{proof}

% 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. [Note: For $xy$ to be irrational, this requires that $x$ is nonzero! We will use this and you can, too!]

\begin{proof}
We use proof by contrapositive. [Note: a proof by contradiction could also work here.]
Suppose that $x+y$ and $xy$ are not both irrational. 
We will show that if $x$ is rational, then $y$ is rational. (Note: this is equivalent to the negation of ``$x$ is rational and $y$ is not rational.'')
Since we will suppose that $x$ is rational, there exist integers $p$ and $q$ with $q \neq 0$ such that $x = \frac{p}{q}$.
Since $x \neq 0$, then $p \neq 0$.

Case 1: $x+y$ is rational.
By definition, there exist integers $j$ and $k$ with $k \neq 0$ such that $x + y = \frac{j}{k}$.
Then, $y = (x+y) - x = \frac{j}{k} - \frac{p}{q} = \frac{qj-kp}{kq}$.
Since $qj-kp$ and $kq$ are integers, and $kq \neq 0$, this implies that $y$ is a rational number.

Case 2: $xy$ is rational.
By definition, there exist integers $j$ and $k$ with $k \neq 0$ such that $xy = \frac{j}{k}$.
Then, $y = (xy)(1/x) = \frac{j}{k} \cdot \frac{q}{p} = \frac{jq}{kp}$.
Since $jq$ and $kp$ are integers, and $kp \neq 0$, this implies that $y$ is a rational number.
\end{proof}


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

\begin{proof}
We adapt the proof that $\sqrt{2}$ is irrational.
Assume for the sake of contradiction that $\sqrt{35}$ is a rational number.
Thus, there exist integer $p, q$ with $q \neq 0$ such that $\sqrt{35} = \frac{p}{q}$.
We can select these integers $p$ and $q$ such that they have no common factors.

This implies that $35 = \frac{p^2}{q^2}$ and hence $p^2 = 35q^2$.

Since $p^2$ is a multiple of $35$, and the prime factorization of $35$ is $5 \cdot 7$, $p$ is a multiple of $5$ and a multiple of $7$. [here we are using high-school math skills, you can also prove this.]
Thus, there exists an integer $m$ such that $p = 35m$.
Hence, $35q^2 = p^2 = (35)^2m^2$ and therefore $q^2 = 35m^2$.
Then $q^2$ is a multiple of 35 and hence $q$ is a multiple of $5$.
However, this contradicts that $p$ and $q$ had no common factors.
\end{proof}


% 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.

\textbf{Claim:} $A$ is a Knave and $B$ is a Toggler.

(\emph{The typical approach to this problem is to use case analysis. We will reduce cases by observing some facts first.})

\begin{proof}
Since $A$'s two statements are in direct contradiction, $A$ is not a Knight.
Since $B$'s two statements are in direct contradiction, $B$ is not a Knight.
Consider the type of $A$.

Case 1: $A$ is a Knave.
	Thus, $A$ lies both times. 
	This implies that $B$ is not a Knave or a Knight, so $B$ must be a Toggler.
	Since $A$ is a Knave, $B$'s first statement is true and $B$'s second statement is false.
	Therefore, the case when $A$ is a Knave and $B$ is a Toggler is consistent.
	
Case 2: $A$ is a Toggler.
	Thus, $A$ lies exactly once and tells the truth exactly once.
	However, we know that $B$ is not a Knight, so $A$'s second statement is false.
	Thus, $A$'s first statement must be true, and $B$ is a Knave.
	However, $B$'s second statement is true, contradicting that $B$ is a Knave.
	Therefore, $A$ cannot be a Toggler.
\end{proof}


% 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.

\begin{proof}
The $2 \times 4$ chessboard can be tiled using L-pieces in a simple way. A picture suffices to demonstrate this.
\begin{center}
\includegraphics[height=0.5in]{figures/tetrominos-L-3x8tiling}
\end{center}

If $m = 2k$ and $n = 4\ell$, then the $2\times 4$ chessboard appears $k\ell$ times in the $m \times n$ chessboard. 
For each of these copies, place two L-pieces in the copy as in the tiling of the $2 \times 4$ chessboard.
\end{proof}

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

\begin{proof}
There is a tiling of the L-piece using two dominoes.
If the chessboard has a tiling using L-pieces, then replace each L-piece with two dominoes as in that tiling.
\end{proof}

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

\begin{proof}
An L-piece covers exactly four squares.
If an $m \times n$ chessboard has a tiling using L-pieces, then the number of squares in the chessboard is a multiple of four.
Thus, $mn$ is even, and one of $m$ or $n$ must be even.
\end{proof}

\clearpage
\textbf{Problem 5.} (Continued)

\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. 

\begin{proof}
The $3 \times 8$ chessboard can be tiled using L-pieces. See picture.

\begin{center}
\includegraphics[height=0.5in]{figures/tetrominoes-L}
\end{center}

If $k$ is even, then $k = 2\ell$ and $4k = 8\ell$. 
Thus, the $3\times 4k$ chessboard can be tiled using $\ell$ copies of the above tiling.
\end{proof}


[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.)

\begin{proof}
We will use \emph{strong} induction to prove that if $k \geq 1$ is odd, then the $3 \times 4k$ chessboard cannot be tiled using L-pieces. 
We first make a claim about any tiling:

\textbf{Claim:} Any tiling of the $3 \times 4k$ chessboard using L-pieces must use an L-piece covering all three rows on the left-most and right-most edges.

\begin{proof}[Proof of Claim.]
Suppose there is a tiling that does not use an L-piece on an edge of length three (without loss of generality, we use the left edge).
The top-left corner must be covered by some L-piece. 
Consider the possible placements, by how many squares of the L-piece are on the left edge.

Case 1: Exactly one square of the L-piece is on the left edge. In this case, the L-piece covers the three squares in the second column, leaving two squares on the left edge that cannot be covered by an L-piece!

\begin{center}
\begin{tabular}[h]{c@{\qquad}c}
\includegraphics[height=0.5in]{figures/tetrominos-L-onesquareleft} & 
\includegraphics[height=0.5in]{figures/tetrominos-L-twosquaresleft} 
\\
Case 1. & Case 2.
\end{tabular}
\end{center}

Case 2: Exactly two squares of the L-piece are on the left edge.
There are two ways for the L-piece to cover two squares on the left edge.
However, since the bottom-left corner must be covered by an L-piece, the top-left corner piece cannot cover three squares in the middle row.
So, the top-left corner is covered by an L-piece that has three squares on the top edge.
Finally, the bottom-left corner must be covered by an L-piece and the only way this can be placed is with three squares on the bottom edge.
This leaves the square in the $(2,2)$ position surrounded by squares already covered, so no L-piece can cover this square!
\end{proof}

Case $k = 1$:
By the claim above, any tiling of the $3 \times 4$ chessboard must include an L-piece covering three squares of the left edge.
Also, the tiling must include an L-piece covering three squares of the right edge.
These L-pieces are either arranged such that they cover adjacent squares, or do not.
When they cover adjacent squares, the four squares not covered by these two pieces form a $2 \times 2$ chessboard, which cannot fit an L-piece.
When they do not cover adjacent squares, the four squares not covered by these two pieces form a $3 \times 2$ chessboard with two opposite corners missing, which cannot fit an L-piece.
Therefore, there is no tiling of the $3 \times 4$ chessboard.

\begin{center}
\begin{tabular}[h]{c@{\qquad}c}
\includegraphics[height=0.5in]{figures/tetrominos-L-3x4-adjacent} & 
\includegraphics[height=0.5in]{figures/tetrominos-L-3x4-nonadjacent} \\
Covering Adjacent Squares & Not Covering Adjacent Squares
\end{tabular}
\end{center}

Now suppose that the statement is true for all $k < K$.

Case $K$: Suppose that we have a tiling of the $3\times 4K$ chessboard using L-pieces.
If an L-piece is placed vertically so it covers all three rows of the chessboard, then the tiling of the $3 \times 4K$ chessboard partitions into tilings of a $3 \times m$ chessboard and a $3 \times (4K-m)$ chessboard, for some $m$.
Since L-pieces cover 4 squares each, these tilings cover a multiple of 4 squares, so $3m$ is a multiple of 4 and therefore $m = 4n$ for some integer $n$.
Finally, this implies that the $3\times 4n$ chessboard and the $3 \times 4(K-n)$ chessboard are tiled using L-pieces.
Since $K$ is odd, one of $n$ or $K-n$ is odd. 
Suppose without loss of generality, $n$ is odd,  but by the induction hypothesis the $3 \times 4n$ chessboard cannot be tiled using L-pieces.

Therefore, no L-piece is placed vertically to cover all three rows of the chessboard, except for the left-most edge and the right-most edge.

We now investigate our tiling, starting on the left edge.
As claimed, all three squares on this edge are covered by the same L-piece.
Since the square in the (2,2) position must be covered by an L-piece, the only arrangement of an L-piece covering this square without immediately making a tiling impossible is to have that L-piece cover the other open position in the second column.
Therefore, we definitely have a tiling that looks like the below (or its vertical mirror).
\begin{center}
\includegraphics[height=0.5in]{figures/tetrominos-L-oddtiling-case0.pdf}
\end{center}
We now consider how the (3,3) position is covered. Note that if it is covered by an L-piece without also covering the (2,3) position, the (2,3) position cannot be covered by an L-piece.
Thus, both the (3,3) and (3,2) positions are covered by the same L-piece.
There are two options to cover these two by a single L-piece, and they each ``force'' another L-piece, as in the pictures below.
\begin{center}
\includegraphics[height=0.5in]{figures/tetrominos-L-oddtiling-case2}

\includegraphics[height=0.5in]{figures/tetrominos-L-oddtiling-case2-alt}
\end{center}
Observe that both options cover the same set of squares, so we can take either option.
We now consider how the (1,5) position is covered, and there is exactly one option.
\begin{center}
\includegraphics[height=0.5in]{figures/tetrominos-L-oddtiling-case3}
\end{center}
Given this set of covered squares, we can now consider the (3,7) position.
This cannot be covered by an L-piece that covers all three rows (as below) because that would create a vertical L-piece, which we demonstrated does not exist.
\begin{center}
\includegraphics[height=0.5in]{figures/tetrominos-L-oddtiling-case4-bad}

Bad example!
\end{center}
Therefore, the L-piece covering the (3,7) position covers three squares on the bottom edge.
\begin{center}
\includegraphics[height=0.5in]{figures/tetrominos-L-oddtiling-case4}
\end{center}
This forces the (2,8) position to be covered by an L-piece that has three squares on the top edge.
\begin{center}
\includegraphics[height=0.5in]{figures/tetrominos-L-oddtiling-case5}
\end{center}
Now consider how the (2,10) position is covered by an L-piece.
If it is covered by an L-piece that does not have three squares on the bottom row, observe that the tiling cannot continue in one or two more placements of L-pieces [I know this is sketchy, but its' getting late].
Thus, the (2,10) position is covered by an L-piece covering three squares on the bottom row, as in the picture below.
\begin{center}
\includegraphics[height=0.5in]{figures/tetrominos-L-oddtiling-case6}
\end{center}
Now, see the two thick black lines. If we remove all of the L-pieces between them and take the two L-pieces on the left, flip them vertically, they fit nicely with the rest of the tiling to the right.
See the picture below.
\begin{center}
\includegraphics[height=0.5in]{figures/tetrominos-L-oddtiling-case6-conclusion}
\end{center}
Therefore, our tiling of the $3 \times 4K$ chessboard gives us a way to tile the $3 \times 4(K-2)$ chessboard. However, our induction hypothesis claims this is impossible, so we have a contradiction!
\end{proof}


\end{document} 