\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=Saturday, December 04, 2021 00:27:04}
%TCIDATA{SuppressPackageManagement}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{BibliographyScheme=Manual}
%TCIDATA{ComputeDefs=
%$f\left(  n\right)  =\prod_{k=0}^{n}\dbinom{n}{k}$
%$g\left(  n\right)  =\dfrac{n!^{n+1}}{\left(  \prod_{k=0}^{n}k!\right)  ^{2}}$
%$h\left(  n\right)  =\prod_{j=1}^{n}j^{2j-n-1}$
%$s\left(  n\right)  =\dfrac{\prod_{k=1}^{n}k^{2k}}{\left(  n!\right)  ^{n+1}}$
%}
%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}
\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 220-002 Fall 2021 (Darij Grinberg): final exam}
\ohead{page \thepage}
\cfoot{}
\begin{document}

\begin{center}
\textbf{Math 220-002 Fall 2021 (Darij Grinberg): final exam}

due date: Sunday 2021-12-12 at noon on gradescope

( \url{https://www.gradescope.com/courses/313263} ).

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

\begin{exercise}
Let $n\in\mathbb{N}$. Prove that%
\[
\underbrace{1+2+\cdots+n}_{=\sum_{k=1}^{n}k}=\underbrace{n^{2}-\left(
n-1\right)  ^{2}+\left(  n-2\right)  ^{2}-\left(  n-3\right)  ^{2}\pm
\cdots+\left(  -1\right)  ^{n-1}1^{2}}_{=\sum_{k=1}^{n}\left(  -1\right)
^{n-k}k^{2}}.
\]

\end{exercise}

Recall the notation $\prod_{k=i}^{j}a_{k}$ for a product $a_{i}a_{i+1}%
a_{i+2}\cdots a_{j}$. (If $i>j$, then this product is empty and understood to
equal $1$. If $i=j$, then this product has only one factor and equals $a_{i}$.)

\begin{exercise}
Prove the following: \medskip

\textbf{(a)} For each $n\in\mathbb{N}$, we have%
\[
\prod_{k=0}^{n}k!=\prod_{k=1}^{n}k!=\prod_{k=1}^{n}k^{n-k+1}.
\]


\textbf{(b)} For each $n\in\mathbb{N}$, we have
\[
\prod_{k=1}^{n}k^{k-1}=\prod_{k=1}^{n}\dfrac{n!}{k!}.
\]

\end{exercise}

\begin{exercise}
Let $m$ be a positive integer, and let $m_{d}m_{d-1}\cdots m_{0}$ be its
decimal representation, so that $m_{0},m_{1},\ldots,m_{d}$ are digits
satisfying%
\[
m=m_{d}\cdot10^{d}+m_{d-1}\cdot10^{d-1}+\cdots+m_{0}\cdot10^{0}=\sum_{k=0}%
^{d}m_{k}\cdot10^{k}.
\]
Let $a$ be the alternating sum of digits of $m$; this is defined by%
\[
a:=m_{0}-m_{1}+m_{2}-m_{3}\pm\cdots+\left(  -1\right)  ^{d}m_{d}=\sum
_{k=0}^{d}\left(  -1\right)  ^{k}m_{k}.
\]
Prove that $11\mid m$ if and only if $11\mid a$. (This is the classical
divisibility test for divisibility by $11$.)
\end{exercise}

\begin{exercise}
Let $n$ be an integer such that $n>1$ but $n$ is not a prime. Let $d$ be the
smallest divisor of $n$ that is larger than $1$. Prove that $d\leq\sqrt{n}$. \medskip

(You can use standard properties of inequalities -- e.g., the equivalence
$\left(  u\leq v\right)  \ \Longleftrightarrow\ \left(  u^{2}\leq
v^{2}\right)  $ when $u$ and $v$ are positive.)
\end{exercise}

\begin{exercise}
Let $p$ be a prime. \medskip

\textbf{(a)} Prove that $\left(  a+1\right)  ^{p}\equiv a^{p}%
+1\operatorname{mod}p$ for each integer $a$. \medskip

\textbf{(b)} Prove that $a^{p}\equiv a\operatorname{mod}p$ for each
$a\in\mathbb{N}$. \medskip

\textbf{(c)} Prove that $a^{p}\equiv a\operatorname{mod}p$ for each integer
$a$. \medskip

[\textbf{Hint:} The binomial formula and a certain property of $\dbinom{p}{k}$
can help.]
\end{exercise}

\begin{exercise}
Let $X$, $Y$ and $Z$ be three sets, and $f:Y\rightarrow Z$ and $g:X\rightarrow
Y$ be two maps. Which of the following are true? \medskip

\textbf{(a)} If $f$ and $g$ are injective, then $f\circ g$ is injective. \medskip

\textbf{(b)} If $f\circ g$ is injective, then $f$ is injective. \medskip

\textbf{(c)} If $f\circ g$ is injective, then $g$ is injective. \medskip

\textbf{(d)} If $f$ and $g$ are surjective, then $f\circ g$ is surjective. \medskip

\textbf{(e)} If $f\circ g$ is surjective, then $f$ is surjective. \medskip

\textbf{(f)} If $f\circ g$ is surjective, then $g$ is surjective. \medskip

\textbf{(g)} If $f$ and $g$ are bijective, then $f\circ g$ is bijective. \medskip

\textbf{(h)} If $f\circ g$ is bijective, then $f$ is bijective. \medskip

\textbf{(i)} If $f\circ g$ is bijective, then $g$ is bijective. \medskip

\textbf{(j)} Pick \textbf{one} of the nine claims above and justify your
answer (with a proof if the answer is \textquotedblleft yes\textquotedblright%
\ and a counterexample if the answer is \textquotedblleft no\textquotedblright%
). \medskip

[Other than this, justifications are \textbf{not} required in this exercise!]
\end{exercise}


\end{document}