\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 10}{Due: Wed. Apr 5, 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}{}





%%
%% FUTURE/ HW11:
%%  $Let a,b,c,d\in\ZZ$ and suppose that $|bc-ad| = 1$.  Prove that $\gcd(an+b,cn+d)=1$ for each $n\in\ZZ$.
%% Suppose n bits are arranged.  In each interval of size m, we want an odd number of bits set to 1.  For which pairs $(n,m)$ is this possible?
%%
%%  Cake flipping problem.  Cut slices with angle $\theta$.  In terms of $\theta$, will cake ever be all facing up again?  Will it ever be all face down?
%%

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

\item An identity.
\begin{enumerate}
	\item Using the binomial theorem, show that $\displaystyle \sum_{k=0}^n \binom{n}{k} = 2^n$.  (Hint: substitute appropriate values for $x$ and $y$ in the equation from the binomial theorem.)
	\item By counting the subsets of an $n$-element set in two different ways, give a combinatorial proof that $\displaystyle \sum_{k=0}^n \binom{n}{k} = 2^n$.
\end{enumerate}

\item Aces.  Recall that a standard deck of cards has one card for each suit/rank pair, where the 4 suits are clubs, diamonds, hearts, and spades, and the 13 ranks are ace, 2 through 10, jack, queen, and king.  A \emph{poker hand} is a set of 5 cards.  Use a sentence or two to explain in detail how your how you derived your answer.  Express your answers first using binomial coefficients, and then apply the algebraic formula $\binom{n}{k} = \frac{n!}{k!(n-k)!}$ to obtain simplified numbers.
\begin{enumerate}
	\item How many poker hands contain the ace of spades?  If dealt a poker hand from a freshly shuffled deck, what is the probability it contains the ace of spades?
	\item How many poker hands contain exactly one ace?
	\item How many poker hands contain no aces?
	\item How many poker hands contain at least two aces?
\end{enumerate}

\item Prove the following (using any method).
\begin{enumerate}
	\item Suppose that $x\in\ZZ$.  Prove that $x$ is even if and only if $3x+5$ is odd.
	\item An integer $a$ is odd if and only if $a^3$ is odd.
	\item Suppose $x,y\in\RR$.  Then $(x+y)^2 = x^2 + y^2$ if and only if $x=0$ or $y=0$.
\end{enumerate}

\item Prove that for each $d\in\NN$, there exists a prime $p$ such that $p>1000$ and $p+d$ is not prime. (Hint: try proof by contradiction.  What does it mean for this claim to be false?  In other words, what is the logical negation of this claim?  If you have trouble formulating the negation, then it may be helpful to translate the claim into a symbolic logic formula $\varphi$, negate $\varphi$ and simplify, and finally translate back into English.)

\end{enumerate}
\end{document}
