\documentclass[11pt]{article}
\usepackage{jeffe,handout,multicol,tikz,kgm}
\usepackage{graphicx}

\newcommand{\kgmcomment}[1]{}
\renewcommand{\gcd}{\mathrm{gcd}}

\begin{document}
\headers{Math378}{Homework 4}{Due Fri. Feb 13, 2026}

%\makeatletter
%\def\@oddfoot{\hfill \tikz \node[draw] {over} ; }
%\makeatother

%\newcommand{\seq}[1]{\left\langle #1\right\rangle}

\newcommand{\RR}{\mathbb{R}}
\newcommand{\ZZ}{\mathbb{Z}}

\makeatletter
\def\@oddfoot{}
\makeatother

\noindent
\textbf{Directions:} Solve the following problems.  All written work must be your own.  See the course syllabus for detailed rules.

\begin{enumerate}

\item {} [2.1.6] You have a $3\times 3$-square, and you throw 10 darts at it.  Show that no matter where the darts land, there are two darts whose distance is at most $\sqrt{2}$.

\item {} [2.1.22] I have 51 rectangular pieces of cardboard, each of which has an integer length and width in the set $\{1,\ldots,100\}$.  (Note that squares are allowed.)  Prove that there are two rectangles such that one can fully cover the other when placed on top.

\item Let $a_0 = 4$, $a_1 = 10$, $a_2 = 88$, and $a_n =a_{n-1} + 21a_{n-2} - 45a_{n-3}$ for $n\ge 3$.  Use the characteristic equation method to solve the recurrence.

\item For positive $m$ and $n$, a domino tiling of an $m\times n$ grid is \emph{rigid} if every horizontal and vertical cut crosses a domino.  In this problem, we characterize the grids with even dimensions that have rigid domino tilings.
\begin{enumerate}
	\item Prove that if $m=2r$, $n=2s$, and the $m\times n$ grid has a rigid domino tiling, then $(r-2)(s-2) \ge 2$.  (Hint: generalize our argument in class that the $6\times 6$ grid has no rigid domino tiling.)
	\item Construct a rigid domino tiling of the $6\times 8$ grid.
	\item Prove that if $m\ge 3$ and the $m\times n$ grid has a rigid domino tiling, then the $m\times (n+2)$ grid also has a rigid domino tiling.  (Hint: show how to modify an arbitrary rigid domino tiling of the $m\times n$ grid to obtain a rigid domino tiling of the $m\times (n+2)$ grid.)
	\item Let $m$ and $n$ be positive, even integers with $m\le n$.  Prove that the $m\times n$ grid has a rigid domino tiling if and only if $m\ge 6$ and $n\ge 8$.  (Hint: for the forward direction, use part (a) to give a direct proof.  For the backward direction, use parts (b) and (c) to give an inductive proof.)
\end{enumerate}



\end{enumerate}
\end{document}
