\documentclass[12pt]{article}

\usepackage{mathrsfs}
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{graphicx}
\usepackage{csquotes}

\usepackage{tikz}
\usetikzlibrary{positioning, scopes} 			%always use these
\usetikzlibrary{backgrounds}

%table spacing
\newcommand{\T}{\rule{0pt}{2.6ex}}
\newcommand{\B}{\rule[-1.2ex]{0pt}{0pt}}


\newcommand{\RR}{\mathbb{R}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\lcm}{\operatorname{lcm}}


\newtheorem{theorem}{Theorem}
\renewcommand*{\thetheorem}{I.\arabic{theorem}}
\newtheorem{exercise}[theorem]{Exercise}
\theoremstyle{definition}
\newtheorem*{definition}{Definition}

\setlength{\oddsidemargin}{0in} \setlength{\evensidemargin}{0in}
\setlength{\marginparwidth}{0in} \setlength{\marginparsep}{0in}
\setlength{\topmargin}{0in} \setlength{\headheight}{0pt}
\setlength{\headsep}{23pt} \setlength{\footskip}{.3in}
\setlength{\textwidth}{6.5in} \setlength{\textheight}{8.2in}%\setlength{\textheight}{9.2in}
\setlength{\parskip}{4pt}


\begin{document}

\begin{center}
{\large{\textsc{Math 3345 Bonus Problems}}}
\end{center}

\thispagestyle{empty}

\noindent The following bonus problems are worth extra credit, which will be added to the homework component of your course grade (not to exceed 100\%).

\noindent Each problem is worth up to $5$ points. Full credit will only be awarded to solutions which are \textbf{complete, correct, and readable.}

\noindent You may turn in solutions to any number of these problems, individually or in batches, \textbf{at any time but no later than Friday, April 19.}



\begin{enumerate}
\item We define a logical connective $\downarrow$ as follows: $P \downarrow Q$ is true when both $P$ and $Q$ are false, and it is false otherwise. (We read $P \downarrow Q$ as ``$P$ nor $Q$'').
\begin{enumerate}
\item Write a truth table for $P \downarrow Q$ and check that $P \downarrow Q$ is logically equivalent to $\neg (P \vee Q)$.
\item Check that $P \downarrow Q \equiv Q \downarrow P$. That is, $\downarrow$ is commutative.
\item Show that $(P \downarrow Q) \downarrow R$ and $P \downarrow (Q \downarrow R)$ are logically inequivalent. That is, $\downarrow$ is \emph{not} associative.
\item Show that the logical connectives $\neg$, $\wedge$, and $\vee$ can each be expressed entirely in terms of $\downarrow$, without using any other logical connectives. Specifically, prove the following:
\begin{enumerate}
\item $\neg P \equiv (P \downarrow P)$.
\item $P \wedge Q \equiv (P \downarrow P) \downarrow (Q \downarrow Q)$.
\item $P \vee Q \equiv (P \downarrow Q) \downarrow (P \downarrow Q)$.
\end{enumerate}
\item Prove that the logical connective $\Rightarrow$ can be expressed entirely in terms of $\downarrow$. That is, show that the sentence $P \Rightarrow Q$ is logically equivalent to a sentence involving $\downarrow$ and no other logical connectives.
\end{enumerate}

\vfill

\item Let $a$ be an odd integer. Prove by induction that $a^{2^n} - 1$ is divisible by $2^{n+1}$ for every integer $n \geq 0$.

\vfill

\item Let $p$ be an integer such that $p \geq 2$. Suppose that for all $x, y \in \ZZ$, if $p | xy$ then $p | x$ or $p | y$. Prove that $p$ is prime. (This is the converse of the ``Theorem on Division by a Prime.'')

\vfill

\newpage

\item In this problem, we consider integers of the form $a^3 + b^3 + c^3$, where $a, b, c \in \ZZ$. For example, it was discovered in 2019 that
\[ 33 = (8, 866, 128, 975, 287, 528)^3 + (-8, 778, 405, 442, 862, 239)^3 + (-2, 736, 111, 468, 807, 040)^3. \]
\begin{enumerate}
\item Find integers $a$, $b$, and $c$ such that $0 = a^3 + b^3 + c^3$.
\item Find integers $a$, $b$ and $c$ such that $1 = a^3 + b^3 + c^3$.
\item Prove that for every $a \in \ZZ$, we have
\[ a^3 \equiv 0 \mod{9}, \qquad a^3 \equiv 1 \mod{9}, \qquad \text{or} \qquad a^3 \equiv -1 \mod{9}. \]
\item Use part (c) to show that if $n = a^3 + b^3 + c^3$, where $a, b, c \in \ZZ$, then $n \not\equiv 4 \mod{9}$ and $n \not\equiv 5 \mod{9}$.
\end{enumerate}
The converse of part (d) is an open problem. If you make any progress on it, let me know!

\vfill

\item For $n, k \in \ZZ$ such that $0 \leq k \leq n$, define
\[ \binom{n}{k} = \frac{n!}{k! (n-k)!}. \]
Note that, by convention, $0! = 1$.
\begin{enumerate}
\item Prove that $\binom{n}{0} = 1$, $\binom{n}{n} = 1$, and
\[ \binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1} \qquad \text{if} \qquad 1 \leq k \leq n-1. \]
\item Use part (a) and induction to prove that $\binom{n}{k}$ is a positive integer for all $n, k \in \ZZ$ such that $0 \leq k \leq n$.
\item Let $x, y \in \RR$. Prove that for every integer $n \geq 0$,
\[ (x + y)^n = \sum_{k=0}^n \binom{n}{k} x^{n-k} y^{k}, \]
\end{enumerate}

\vfill

\newpage

\item The \textbf{Archimedean Property} of the real numbers is the following statement:
\begin{displayquote}
For every $x, y \in \RR$ such that $x > 0$ and $y > 0$, there exists $n \in \NN$ such that $nx > y$.
\end{displayquote}
\begin{enumerate}
\item Prove that for every $a \in \RR$, there exists $n \in \NN$ such that $n > a$. That is, $\NN$ is not bounded above. [\textsc{hint:} Proceed by contradiction, and use the Least Upper Bound Property of $\RR$.]
\item Use part (a) to prove that the Archimedean Property is true.
\item Use the Archimedean Property to prove that for every $x \in \RR$ such that $x > 0$, there exists $n \in \NN$ such that $\frac{1}{n} < x$.
\item Prove that there is a rational number between any two real numbers. That is, for every $a, b \in \RR$ with $a < b$, there exists $q \in \QQ$ such that $a < q < b$. [\textsc{hint:} Start by using part (c) to find a denominator for $q$. Then, use the Well-Ordering Axiom to choose a numerator for $q$.]
\end{enumerate}

\vfill

\item \begin{enumerate}
\item Let $x \in \QQ$. Prove that if $x^3 \in \ZZ$, then $x \in \ZZ$.
\item Let $n \in \ZZ$. Prove that if $n$ is not a perfect cube (i.e., there is no integer $m$ such that $n = m^3$), then $\sqrt[3]{n}$ is irrational.
\end{enumerate}

\vfill

\item Let $c, n \in \NN$. Use the rational roots theorem (see Homework 16) to prove that $\sqrt[n]{c}$ is either an integer or an irrational number. [\textsc{hint:} Consider the polynomial $x^n - c$.]

\vfill

\newpage

\item Let $a, b, c \in \ZZ$ be integers with $a$ and $b$ not both $0$. Let $d = \gcd(a,b)$.
\begin{enumerate}
\item Prove that there exist $x, y \in \ZZ$ such that
\[ ax + by = c \]
if and only if $d$ divides $c$.
\item Suppose there exist $x_0, y_0 \in \ZZ$ such that
\[ ax_0 + by_0 = c. \]
Show that for every $k \in \ZZ$, the numbers
\[ x = x_0 + \frac{kb}{d} \qquad \text{and} \qquad y = y_0 - \frac{ka}{d} \]
are integers and $ax + by = c$.
\item Suppose still that $x_0, y_0 \in \ZZ$ satisfy
\[ ax_0 + by_0 = c. \]
Show that if $x, y \in \ZZ$ satisfies the equation $ax + by = c$, then
\[ x = x_0 + \frac{kb}{d} \qquad \text{and} \qquad y = y_0 - \frac{ka}{d} \]
for some $k \in \ZZ$.
\item Use the results from parts (a)--(c) to explain why the equation
\[ 18x + 42y = 30 \]
has integer solutions, and find all integer solutions $x,y \in \ZZ$.
\end{enumerate}

\vfill

\newpage

\item For sets $A$ and $B$, define
\[ A \, \Delta \, B = (A \setminus B) \cup (B \setminus A). \]
\begin{enumerate}
\item Let $A$ and $B$ be sets. Prove that $A = B$ if and only if $A \, \Delta \, B = \emptyset$.
\item Let $A$ and $B$ be sets. Prove that $A \, \Delta \, B$ = $B \, \Delta \, A$.
\item Let $A$, $B$, and $C$ be sets. Prove that $(A \, \Delta \, B) \, \Delta \, C = A \, \Delta \, (B \, \Delta \, C)$.
\end{enumerate}

\vfill

\item For each $n \in \NN$, define $A_n = [0, 1 + \frac{1}{n}]$ and $B_n = [0, 1 - \frac{1}{n}]$.
\begin{enumerate}
\item Prove that $\bigcup_{n=1}^{\infty} A_n$ is an interval, and describe this interval explicitly.
\item Prove that $\bigcap_{n=1}^{\infty} A_n$ is an interval, and describe this interval explicitly.\item Prove that $\bigcup_{n=1}^{\infty} B_n$ is an interval, and describe this interval explicitly.
\item Prove that $\bigcap_{n=1}^{\infty} B_n$ is an interval, and describe this interval explicitly.
\end{enumerate}

\vfill

\item Define a function $f \colon \ZZ \times \ZZ \to \ZZ \times \ZZ$ by
\[ f(m, n) = (5m + 4n, \ 4m + 3n). \]
Prove that $f$ is a bijection and give a formula for its inverse function.

\vfill

\item 
\begin{enumerate}
\item Find a bijection $f \colon (0,\pi) \to \RR$ or prove that no such bijection exists.
\item Find a bijection $g \colon [0,\pi] \to \RR$ or prove that no such bijection exists.
\end{enumerate}

\vfill

\item Let $A$ be an infinite set. Prove that there exists an injective function $f \colon \NN \to A$.

\vfill

\end{enumerate}



\end{document}


