\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=Monday, February 17, 2025 17:19:22}
%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 2025 (Darij Grinberg): midterm 3}
\ohead{page \thepage}
\cfoot{}
\begin{document}

\begin{center}
\textbf{Math 221 Winter 2025 (Darij Grinberg): midterm 3}

due date: Monday 2025-03-17 at 11:59PM on gradescope (
\url{https://www.gradescope.com/courses/930212} ).

Please solve only \textbf{3 of the 8 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\}  $. Recall also that
$\left[  n\right]  $ denotes the set $\left\{  1,2,\ldots,n\right\}  $
whenever $n\in\mathbb{N}$.

\begin{exercise}
For each of the following functions, determine whether it is injective,
surjective and/or bijective:

\textbf{(Proofs are not required in this exercise!) }\medskip

\textbf{(a)} The function%
\begin{align*}
f:\mathbb{Q}  &  \rightarrow\mathbb{Q},\\
x  &  \mapsto\dfrac{x}{1+x^{2}}.
\end{align*}


\textbf{(b)} The function%
\begin{align*}
f:\mathbb{Z}  &  \rightarrow\mathbb{Q},\\
x  &  \mapsto\dfrac{x}{1+x^{2}}.
\end{align*}


\textbf{(c)} The function%
\begin{align*}
f:\left\{  \text{finite nonempty subsets of }\mathbb{Z}\right\}   &
\rightarrow\mathbb{Z},\\
S  &  \mapsto\min S
\end{align*}
(which sends each set to its smallest element). \medskip

\textbf{(d)} The function
\begin{align*}
f:\mathbb{Z}\times\mathbb{Z}  &  \rightarrow\mathbb{Z},\\
\left(  x,y\right)   &  \mapsto2x+3y.
\end{align*}


\textbf{(e)} The function%
\begin{align*}
f:\mathbb{N}\times\mathbb{N}  &  \rightarrow\mathbb{N},\\
\left(  x,y\right)   &  \mapsto2x+3y.
\end{align*}

\end{exercise}

\bigskip

\begin{exercise}
Let $n\in\mathbb{N}$. Consider the set $\left[  2n\right]  =\left\{
1,2,\ldots,2n\right\}  $.

A set of integers will be called \textbf{parity-ambivalent} if it contains at
least one even element and at least one odd element. (For instance, $\left\{
2,4,5\right\}  $ is parity-ambivalent, but $\left\{  2,4,10\right\}  $ is not.)

Compute the \# of all parity-ambivalent subsets of $\left[  2n\right]  $.
\medskip

[\textbf{Hint:} One way to solve it is by negation: How many subsets of
$\left[  2n\right]  $ contain \textbf{no} even element? How many contain
\textbf{no} odd element? How many contain neither?]
\end{exercise}

\bigskip

\begin{exercise}
\label{exe.simple-counts}\textbf{(a)} How many $7$-digit numbers are there? (A
\textquotedblleft$k$-digit number\textquotedblright\ means a nonnegative
integer that has $k$ digits when written in the decimal system (without
leading zeroes). For example, $3902$ is a $4$-digit number, not a $5$-digit number.)

\textbf{(b)} How many $7$-digit numbers are there that have no two equal digits?

\textbf{(c)} How many $7$-digit numbers have an even sum of digits?

\textbf{(d)} How many $7$-digit numbers are palindromes? (A \textquotedblleft%
\textbf{palindrome}\textquotedblright\ is a number such that reading its
digits from right to left yields the same number. For example, $5$ and $1331$
and $49094$ are palindromes.)

[If your answer is a product or power, \textbf{you do not need to simplify it
to a number}.]
\end{exercise}

\bigskip

Recall the notion of a \textquotedblleft left inverse\textquotedblright\ of a
map (as defined in Exercise 3 on homework set \#6).

\begin{exercise}
Let $n,m\in\mathbb{N}$. Let $X$ be an $n$-element set. Let $Y$ be an
$m$-element set. Let $f:X\rightarrow Y$ be an injective map. Prove that $f$
has exactly $n^{m-n}$ many left inverses.
\end{exercise}

\bigskip

If $S$ is any set, and $n$ is any nonnegative integer, then the Cartesian
product $\underbrace{S\times S\times\cdots\times S}_{n\text{ times}}$ is
denoted by $S^{n}$. For example, $S^{3}=S\times S\times S$.

Recall that a $k$-tuple $\left(  i_{1},i_{2},\ldots,i_{k}\right)  $ is called
\textbf{injective} if its $k$ entries $i_{1},i_{2},\ldots,i_{k}$ are all
distinct (i.e., if $i_{a}\neq i_{b}$ for all $a\neq b$).

\begin{exercise}
Let $n\in\mathbb{N}$. How many injective $\left(  2n\right)  $-tuples $\left(
i_{1},i_{2},\ldots,i_{2n}\right)  \in\left[  2n\right]  ^{2n}$ are there such
that all of the first $n$ entries $i_{1},i_{2},\ldots,i_{n}$ are even?

(For instance, for $n=2$, there are $4$ such tuples: $\left(  2,4,1,3\right)
$, $\left(  2,4,3,1\right)  $, $\left(  4,2,1,3\right)  $ and $\left(
4,2,3,1\right)  $.)
\end{exercise}

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

\textbf{(a)} How many injective $n$-tuples $\left(  i_{1},i_{2},\ldots
,i_{n}\right)  \in\left[  n\right]  ^{n}$ begin with the entry $2$ ?

\textbf{(b)} How many injective $n$-tuples $\left(  i_{1},i_{2},\ldots
,i_{n}\right)  \in\left[  n\right]  ^{n}$ contain the entry $1$ before the
entry $2$ ? (\textquotedblleft Before\textquotedblright\ means
\textquotedblleft somewhere to the left of\textquotedblright, not necessarily
\textquotedblleft immediately before\textquotedblright. For instance, for
$n=4$, the $4$-tuple $\left(  1,3,2,4\right)  $ qualifies, but the $4$-tuple
$\left(  2,3,1,4\right)  $ does not.)

\textbf{(c)} How many injective $n$-tuples $\left(  i_{1},i_{2},\ldots
,i_{n}\right)  \in\left[  n\right]  ^{n}$ contain the entry $1$ immediately
preceding the entry $2$ ? (Here, $\left(  1,3,2,4\right)  $ no longer
qualifies, but $\left(  4,1,2,3\right)  $ does.)
\end{exercise}

\bigskip

If $h:S\rightarrow S$ is any map from a set to itself, then a \textbf{fixed
point} of $h$ means an element $s\in S$ satisfying $h\left(  s\right)  =s$.
The set of all fixed points of $h$ will be called $\operatorname*{Fix}h$.

\begin{exercise}
Let $X$ and $Y$ be two finite sets (not necessarily of the same size).

Let $f:X\rightarrow Y$ and $g:Y\rightarrow X$ be two maps. Prove that%
\[
\left\vert \operatorname*{Fix}\left(  f\circ g\right)  \right\vert =\left\vert
\operatorname*{Fix}\left(  g\circ f\right)  \right\vert .
\]


[\textbf{Hint:} Show that $f\left(  x\right)  \in\operatorname*{Fix}\left(
f\circ g\right)  $ for each $x\in\operatorname*{Fix}\left(  g\circ f\right)
$. Thus, there is a map%
\begin{align*}
f^{\prime}:\operatorname*{Fix}\left(  g\circ f\right)   &  \rightarrow
\operatorname*{Fix}\left(  f\circ g\right)  ,\\
x  &  \mapsto f\left(  x\right)  .
\end{align*}
Construct a similar map $g^{\prime}$ in the opposite direction. Prove that
these two maps $f^{\prime}$ and $g^{\prime}$ are inverse to each other.]
\end{exercise}

\bigskip

Now, recall Exercise 6 on homework set \#6. In that exercise, we decided to
call a set $S$ of integers \textbf{pseudolacunar} if no two elements $s,t$ of
$S$ satisfy $\left\vert s-t\right\vert =2$. We denoted the \# of pseudolacunar
subsets of $\left[  n\right]  $ (for a given $n\in\mathbb{N}$) by $p_{n}$.

Recall also the Fibonacci sequence $\left(  f_{0},f_{1},f_{2},\ldots\right)  $
that we introduced in \S 1.5. It is defined recursively by $f_{0}=0$ and
$f_{1}=1$ and $f_{n}=f_{n-1}+f_{n-2}$ for each $n\geq2$.

Finally, recall the floor notation (see Definition 3.3.13).

\begin{exercise}
Prove that
\[
p_{n}=f_{\left\lfloor \left(  n+1\right)  /2\right\rfloor +2}\cdot
f_{\left\lfloor n/2\right\rfloor +2}\ \ \ \ \ \ \ \ \ \ \text{for each }%
n\geq2.
\]


[\textbf{Hint:} What does the pseudolacunarity of a set $S$ mean for the even
elements of $S$ ? What does it mean for the odd elements of $S$ ?]
\end{exercise}


\end{document}