\documentclass[11pt]{article}
\usepackage{jeffe,handout,multicol,tikz,ulem}
\usetikzlibrary{arrows,automata}
\usepackage[latin1]{inputenc}

\tikzstyle{vertex}=[circle,draw]

\newcommand{\kgmcomment}[1]{}

\begin{document}
\headers{Math 303}{Homework 9}{Due: Fri. Mar 29, 2023}

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

\newcommand{\PS}{\mathcal{P}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\st}{\colon \,}
\newcommand{\comp}[1]{\overline{#1}}
\renewcommand{\emptyset}{\varnothing}
\newtheorem{theorem}{Theorem}{}


\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.  Submissions must be stapled.  See ``Guidelines and advice'' on the course webpage for more information.

\begin{enumerate}

\item Prove the following using the method of proof by contradiction.
\begin{enumerate}
	\item Show that $2^{\frac{1}{3}}$ is irrational.
	\item Suppose that $a,b,c\in\ZZ$.  Show that if $a^2+b^2=c^2$, then $a$ or $b$ is even. 
	\item Prove that there are no integers $a$ and $b$ such that $21a + 30b = 1$.
\end{enumerate}

\item Irrational powers of three.
\begin{enumerate}
	\item Let $a$ be an integer.  Prove that if $3\mid a^2$, then $3\mid a$.
	\item Prove that if $k$ is an odd positive integer, then $\sqrt{3^k}$ is irrational.  Hint: suppose for a contradiction that the implication is false for some values of $k$, and let $k$ be the \emph{least} odd positive integer for which the implication fails.
\end{enumerate}

\item Using only logic and trigonometry (not calculus), show that $\sin(x) + \sqrt{3}\cos(x) \le 2$ for each real number $x$.  (Hint: recall that $\tan(\pi / 3) = \sqrt{3}$.)

\item {} Critique the following argument.  (Be careful!)
\begin{center}
\begin{minipage}{0.90\textwidth}
\begin{theorem}
If $p_1, \ldots, p_k$ is a list of the first $k$ primes, then $p_1 p_2 \cdots p_k + 1$ is also a prime.
\end{theorem}
\begin{proof}
Let $n=p_1p_2\cdots p_k + 1$, and note that $1=n-p_1 p_2 \cdots  p_k$.  

Suppose for a contradiction that some prime $p_i$ less than $n$ divides $n$.  If this were true, then $p_i$ divides both terms on the right hand side of $1=n-p_1 p_2  \cdots  p_k$ and therefore $p_i$ must also divide the left hand side of this equation.  Since no prime divides $1$, we have a contradiction.  

The contradiction implies that no prime less than $n$ divides $n$, and therefore $n$ is prime.
\end{proof}
\end{minipage}
\end{center}

\item Counting Subsets and The Binomial Theorem.
\begin{enumerate}
\item Suppose that $A$ is a set and $|A| = 84$.  How many subsets of $A$ have $0$ elements?  How many have $10$ elements?  How many have $74$ elements?

\item Suppose that $A$ is a set and there are $330$ subsets of $A$ of size $7$.  What is $|A|$?

\item Use the binomial theorem to find the coefficient of $x^4y^8$ in $(3x-2y)^{12}$.
\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}
