\documentclass[numbers=enddot,12pt,final,onecolumn,notitlepage]{scrartcl}%
\usepackage{amsfonts}
\usepackage[headsepline,footsepline,manualmark]{scrlayer-scrpage}
\usepackage[all,cmtip]{xy}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{framed}
\usepackage{comment}
\usepackage{color}
\usepackage{hyperref}
\usepackage[sc]{mathpazo}
\usepackage[T1]{fontenc}
\usepackage{needspace}
\usepackage{tabls}
\usepackage{tikz}
\usepackage{ytableau}
\usepackage{skak}
\usepackage{rotating}
\usepackage[framemethod=tikz]{mdframed}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.50.0.2960}
%TCIDATA{LastRevised=Friday, February 24, 2023 13:04:56}
%TCIDATA{SuppressPackageManagement}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{BibliographyScheme=Manual}
%BeginMSIPreambleData
\providecommand{\U}[1]{\protect\rule{.1in}{.1in}}
%EndMSIPreambleData
\newcounter{exer}
\theoremstyle{definition}
\newtheorem{theo}{Theorem}[section]
\newenvironment{theorem}[1][]
{\begin{theo}[#1]\begin{leftbar}}
{\end{leftbar}\end{theo}}
\newtheorem{lem}[theo]{Lemma}
\newenvironment{lemma}[1][]
{\begin{lem}[#1]\begin{leftbar}}
{\end{leftbar}\end{lem}}
\newtheorem{prop}[theo]{Proposition}
\newenvironment{proposition}[1][]
{\begin{prop}[#1]\begin{leftbar}}
{\end{leftbar}\end{prop}}
\newtheorem{defi}[theo]{Definition}
\newenvironment{definition}[1][]
{\begin{defi}[#1]\begin{leftbar}}
{\end{leftbar}\end{defi}}
\newtheorem{remk}[theo]{Remark}
\newenvironment{remark}[1][]
{\begin{remk}[#1]\begin{leftbar}}
{\end{leftbar}\end{remk}}
\newtheorem{coro}[theo]{Corollary}
\newenvironment{corollary}[1][]
{\begin{coro}[#1]\begin{leftbar}}
{\end{leftbar}\end{coro}}
\newtheorem{conv}[theo]{Convention}
\newenvironment{condition}[1][]
{\begin{conv}[#1]\begin{leftbar}}
{\end{leftbar}\end{conv}}
\newtheorem{quest}[theo]{Question}
\newenvironment{algorithm}[1][]
{\begin{quest}[#1]\begin{leftbar}}
{\end{leftbar}\end{quest}}
\newtheorem{warn}[theo]{Warning}
\newenvironment{conclusion}[1][]
{\begin{warn}[#1]\begin{leftbar}}
{\end{leftbar}\end{warn}}
\newtheorem{conj}[theo]{Conjecture}
\newenvironment{conjecture}[1][]
{\begin{conj}[#1]\begin{leftbar}}
{\end{leftbar}\end{conj}}
\newtheorem{exam}[theo]{Example}
\newenvironment{example}[1][]
{\begin{exam}[#1]\begin{leftbar}}
{\end{leftbar}\end{exam}}
\newtheorem{exmp}[exer]{Exercise}
\newenvironment{exercise}[1][]
{\begin{exmp}[#1]\begin{leftbar}}
{\end{leftbar}\end{exmp}}
\newenvironment{statement}{\begin{quote}}{\end{quote}}
\newenvironment{fns}{\begin{footnotesize}}{\end{footnotesize}}
\iffalse
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\fi
\let\sumnonlimits\sum
\let\prodnonlimits\prod
\let\cupnonlimits\bigcup
\let\capnonlimits\bigcap
\renewcommand{\sum}{\sumnonlimits\limits}
\renewcommand{\prod}{\prodnonlimits\limits}
\renewcommand{\bigcup}{\cupnonlimits\limits}
\renewcommand{\bigcap}{\capnonlimits\limits}
\makeatletter
\newcommand\binomialCoefficient[2]{        \c@pgf@counta=#1    \c@pgf@countb=#2            \c@pgf@countc=\c@pgf@counta    \advance\c@pgf@countc by-\c@pgf@countb    \ifnum\c@pgf@countb>\c@pgf@countc        \c@pgf@countb=\c@pgf@countc    \fi            \c@pgf@countc=1    \c@pgf@countd=0    \pgfmathloop        \ifnum\c@pgf@countd<\c@pgf@countb        \multiply\c@pgf@countc by\c@pgf@counta        \advance\c@pgf@counta by-1        \advance\c@pgf@countd by1        \divide\c@pgf@countc by\c@pgf@countd    \repeatpgfmathloop    \the\c@pgf@countc}
\makeatother
\setlength\tablinesep{3pt}
\setlength\arraylinesep{3pt}
\setlength\extrarulesep{3pt}
\voffset=0cm
\hoffset=-0.7cm
\setlength\textheight{22.5cm}
\setlength\textwidth{15.5cm}
\newenvironment{verlong}{}{}
\newenvironment{vershort}{}{}
\newenvironment{noncompile}{}{}
\excludecomment{verlong}
\includecomment{vershort}
\excludecomment{noncompile}
\newcommand{\id}{\operatorname{id}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\set}[1]{\left\{ #1 \right\}}
\newcommand{\abs}[1]{\left| #1 \right|}
\newcommand{\tup}[1]{\left( #1 \right)}
\newcommand{\ive}[1]{\left[ #1 \right]}
\newcommand{\underbrack}[2]{\underbrace{#1}_{\substack{#2}}}
\newcommand{\are}{\ar@{-}}
\newcommand{\arebi}[1][]{\ar@{<-}@/_/[#1] \ar@/^/[#1]}
\ihead{Math 221 Winter 2023 (Darij Grinberg): midterm 2}
\ohead{page \thepage}
\cfoot{}
\begin{document}

\begin{center}
\textbf{Math 221 Winter 2023 (Darij Grinberg): midterm 2}

due date: Sunday 2023-03-05 at 11:59PM on gradescope (
\url{https://www.gradescope.com/courses/487830} ).

Please solve only \textbf{4 of the 6 exercises}.

\textbf{NO collaboration allowed -- this is a midterm!}

(But you can still ask me questions.)
\end{center}

Recall that $\mathbb{N}=\left\{  0,1,2,\ldots\right\}  $.

\bigskip

Theorem 3.6.3 in Lecture 10 shows that if $p$ is a prime, then all the
binomial coefficients $\dbinom{p}{i}$ in the $p$-th row of Pascal's triangle
are divisible by $p$ (except for the two $1$'s on the borders of the
triangle). The following exercise, in contrast, claims that the binomial
coefficients in the $\left(  p-1\right)  $-st row are alternatingly congruent
to $1$ and to $-1$ modulo $p$:

\begin{exercise}
Let $p$ be a prime. Prove that%
\[
\dbinom{p-1}{i}\equiv\left(  -1\right)  ^{i}\operatorname{mod}%
p\ \ \ \ \ \ \ \ \ \ \text{for each }i\in\left\{  0,1,\ldots,p-1\right\}  .
\]


[\textbf{Hint:} What connects the three binomial coefficients $\dbinom{p-1}%
{i}$, $\dbinom{p-1}{i-1}$ and $\dbinom{p}{i}$ ?]
\end{exercise}

Here is another divisibility related to prime numbers:

\begin{exercise}
Let $p$ be a prime larger than $3$. Prove that $p^{2}\equiv1\operatorname{mod}%
24$.

[\textbf{Hint:} Recall some older problems. Also note that the integers $3$
and $8$ are coprime.]
\end{exercise}

\bigskip

Now to some counting problems. The symbol \textquotedblleft%
\#\textquotedblright\ means \textquotedblleft number\textquotedblright.

To \textquotedblleft compute\textquotedblright\ a number means to find a
closed-form expression for this number (with no summation signs) and to prove
this formula. I expect proofs to be given at the level of detail and rigor
seen in Lectures 12 and 13.

\begin{exercise}
Let $n\geq2$ be an integer.

\textbf{(a)} Compute the \# of subsets of $\left\{  1,2,\ldots,n\right\}  $
that contain both $1$ and $2$.

\textbf{(b)} Compute the \# of $3$-element subsets of $\left\{  1,2,\ldots
,n\right\}  $ that contain both $1$ and $2$.
\end{exercise}

\begin{exercise}
Let $n\in\mathbb{N}$. Compute the \# of all pairs $\left(  a,b\right)
\in\left\{  1,2,\ldots,n\right\}  \times\left\{  1,2,\ldots,n\right\}  $
satisfying $a\equiv b\operatorname{mod}2$.

(The answer will depend on whether $n$ is even or odd. You can find a unified
formula using the floor of a number, but you don't have to.)
\end{exercise}

\begin{exercise}
Let $n\in\mathbb{N}$. Compute the \# of all pairs $\left(  a,b\right)
\in\left\{  1,2,\ldots,n\right\}  \times\left\{  1,2,\ldots,n\right\}  $
satisfying $2a\leq b$.

(Again, the answer will depend on whether $n$ is even or odd.)
\end{exercise}

\bigskip

Finally, an exercise combining functions with number theory:

\begin{exercise}
For any positive integer $d$, let us define the function%
\begin{align*}
r_{d}:\mathbb{Z}  & \rightarrow\mathbb{Z},\\
n  & \mapsto n\%d
\end{align*}
(which sends each integer $n$ to the remainder of the division of $n$ by $d$).
For example, $r_{5}\left(  18\right)  =18\%5=3$ and $r_{6}\left(  18\right)
=18\%6=0$.

\textbf{(a)} Make a table of the values of the function $r_{2}\circ r_{3}$ on
the inputs $0,1,2,3,4,5$.

\textbf{(b)} Prove that $r_{2}\circ r_{3}\neq r_{2}$.

\textbf{(c)} Let $d$ and $e$ be two positive integers such that $d\mid e$.
Prove that $r_{d}\circ r_{e}=r_{d}$.
\end{exercise}

\subsection*{Appendix: Rows $0$ to $15$ of Pascal's triangle}%

\[
\hspace{-1pc}%
%TCIMACRO{\TeXButton{tikz pascal}{\begin{tikzpicture}[scale=1.2]
%\foreach\n in {0,1,4,6,8,9,10,12,14,15} {
%\foreach\k in {0,...,\n} {
%\node at (\k-\n/2,-\n) {$\binomialCoefficient{\n}{\k}$};
%}
%}
%\foreach\n in {2,3,5,7,11,13} {
%\foreach\k in {0,...,\n} {
%\node at (\k-\n/2,-\n) {$\mathbf{\binomialCoefficient{\n}{\k}}$};
%}
%}
%\end{tikzpicture}}}%
%BeginExpansion
\begin{tikzpicture}[scale=1.2]
\foreach\n in {0,1,4,6,8,9,10,12,14,15} {
\foreach\k in {0,...,\n} {
\node at (\k-\n/2,-\n) {$\binomialCoefficient{\n}{\k}$};
}
}
\foreach\n in {2,3,5,7,11,13} {
\foreach\k in {0,...,\n} {
\node at (\k-\n/2,-\n) {$\mathbf{\binomialCoefficient{\n}{\k}}$};
}
}
\end{tikzpicture}%
%EndExpansion
\]
Rows corresponding to prime numbers $n$ are printed in bold. LaTeX/tikz source
code \href{https://tex.stackexchange.com/a/17527/}{courtesy of Caramdir on
tex.stackexchange (post \#17527).}


\end{document}