\DocumentMetadata{
  pdfstandard=ua-2, 
  lang=en-US,
  tagging=on,
  tagging-setup = {
    math/setup=mathml-SE,
    math/alt/use,
    table/header-rows = 1
  }
}

\documentclass[11pt]{article}
\usepackage{multicol,tikz,kgm2}
\usepackage{hyperref}
\usetikzlibrary{arrows,automata}
%\usepackage{fullpage}


\tikzstyle{vertex}=[circle,draw]

\newcommand{\kgmclass}{Math303}
\newcommand{\kgmtitle}{Homework 8}
\newcommand{\kgmdate}{Due: Fri. Oct 23, 2026}
\newcommand{\kgmcomment}[1]{}

\hypersetup{
  pdftitle={\kgmtitle},  % Registers the PDF Title metadata
  pdfauthor={K.G. Milans},          % Registers the Author metadata
  pdfdisplaydoctitle=true           % Tells PDF viewers to display the title, not filename
}

\begin{document}
\headers{\kgmclass}{\kgmtitle}{\kgmdate}

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

\makeatletter
\def\@oddfoot{}
\makeatother

%\noindent
%\hfill Name: \underline{\hspace{3.5in}} 

%\begin{flushright}
%Name: \underline{\hspace{3.5in}} \\
%\end{flushright}
%\hrule

\def\columnseprule{0.4pt}

\noindent
\textbf{Directions:} You may work to solve these problems in groups, but all written work must be your own.  Unless the problem indicates otherwise, all problems require some justification; a correct answer without supporting reasoning is not sufficient.  See ``Guidelines and advice'' on the course webpage for more information.

\begin{enumerate}

\item Use the method of contrapositive proof to prove the following.
\begin{enumerate}
	\item If $n$ is an integer and $n^2$ is odd, then $n$ is odd.
	\item If $x\in\RR$ and $x^3-x>0$, then $x>-1$.
	\item Suppose that $x,y,z\in\ZZ$ and $x\ne 0$.  If $x\nmid yz$, then $x\nmid y$ and $x\nmid z$.
	\item If $a$ is an integer and $4\nmid a^2$, then $a$ is odd.
\end{enumerate}

\item Give either a direct proof or a contrapositive proof of each of the following.
\begin{enumerate}
	\item If $a,b\in\ZZ$ and $a$ and $b$ have the same parity, then $3a+7$ and $7b-4$ do not.
	\item Suppose $a,a',b,b',m\in\ZZ$ and $m\ge 1$.  If $a\equiv a'\pmod{m}$ and $b\equiv b'\pmod{m}$, then $ab \equiv a'b'\pmod{m}$.  
	
	\emph{Comment}: this says that when computing $ab$ modulo $m$, we are free to replace $a$ and $b$ with integers $a'$ and $b'$ of our choice, provided that $a'$ is congruent to $a$ and $b'$ is congruent to $b$. 
	\item For all $a,b\in\ZZ$, we have $(a+b)^3\equiv a^3+b^3 \pmod{3}$.
	\item If $n\in\ZZ$, then $4\nmid (n^2 - 3)$.
\end{enumerate}

\item \emph{Forced division.}
\begin{enumerate}
	\item Prove that for each $n\in\NN$, there exist nonnegative integers $r$ and $s$ such that $s$ is odd and $n=2^r s$.
	\item Show that for each $n\in\NN$, the expression for $n$ obtained in part (a) is \emph{unique}.  That is, prove that if $n=2^{r_1} s_1$ and $n=2^{r_2} s_2$ where $r_1$ and $r_2$ are nonnegative integers and $s_1$ and $s_2$ are odd integers, then $r_1=r_2$ and $s_1=s_2$.
	\item Use part (a) to prove that if $A\subseteq \{1,2,\ldots,2m\}$ and $|A| > m$, then there exist integers $b,c\in A$ such that $b\mid c$.  (Hint: find a way to partition $\{1,2,\ldots,2m\}$ into $m$ buckets such that the each bucket forms a division chain, with the smallest number in the bucket dividing the second smallest, the second smallest dividing the third smallest, and so on.)
\end{enumerate}

\item Three people that mutually hate each other are confined to a unit square.  (The people are small compared to the square, so they can be modeled as points.)  Their \emph{buffer} is the distance between the closest pair.  What is the maximum possible buffer?  As usual, be sure to show your work.



\end{enumerate}
\end{document}