\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:14}
%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}
\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): homework set 6}
\ohead{page \thepage}
\cfoot{}
\begin{document}

\begin{center}
\textbf{Math 221 Winter 2025 (Darij Grinberg): homework set 6}

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

Please solve only \textbf{3 of the 7 exercises}.
\end{center}

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

The first three exercises are about functions and their properties:

\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{Z}  &  \rightarrow\mathbb{Z},\\
x  &  \mapsto x^{2}.
\end{align*}


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


\textbf{(c)} The function%
\begin{align*}
f:\mathbb{Z}\times\mathbb{Z}  &  \rightarrow\mathbb{Z},\\
\left(  x,y\right)   &  \mapsto x^{2}+y^{2}.
\end{align*}


\textbf{(d)} The function%
\begin{align*}
f:\mathbb{Z}  &  \rightarrow\mathbb{Z},\\
x  &  \mapsto3-x.
\end{align*}


\textbf{(e)} The function%
\begin{align*}
f:\mathbb{Z}  &  \rightarrow\mathbb{Z},\\
x  &  \mapsto3-2x.
\end{align*}


\textbf{(f)} The function%
\begin{align*}
f:\mathbb{N}  &  \rightarrow\mathbb{N},\\
x  &  \mapsto x!.
\end{align*}
(Keep in mind that $0\in\mathbb{N}$.) \medskip

\textbf{(g)} The function%
\begin{align*}
f:\mathbb{Z}\times\mathbb{Z}  &  \rightarrow\mathbb{Z}\times\mathbb{Z},\\
\left(  x,y\right)   &  \mapsto\left(  x+y,\ x-y\right)  .
\end{align*}


\textbf{(h)} The function%
\begin{align*}
f:\mathbb{Z}\times\mathbb{Z}  &  \rightarrow\mathbb{Z}\times\mathbb{Z},\\
\left(  x,y\right)   &  \mapsto\left(  x-y,\ y-x\right)  .
\end{align*}


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


\textbf{(j)} The function%
\begin{align*}
f:\mathbb{Z}\times\mathbb{Z}  &  \rightarrow\mathbb{Z}\times\mathbb{Z},\\
\left(  x,y\right)   &  \mapsto\left(  x+2y,\ 2x+y\right)  .
\end{align*}

\end{exercise}

\begin{exercise}
Let $A,B,C,D$ be four sets. Let $f:A\rightarrow C$ and $g:B\rightarrow D$ be
two maps. Define a new map $f\ast g:A\times B\rightarrow C\times D$ by setting%
\[
\left(  f\ast g\right)  \left(  a,b\right)  =\left(  f\left(  a\right)
,\ g\left(  b\right)  \right)  \ \ \ \ \ \ \ \ \ \ \text{for every pair
}\left(  a,b\right)  \in A\times B.
\]


Prove the following:

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

\textbf{(b)} If $f$ and $g$ are surjective, then $f\ast g$ is surjective.
\end{exercise}

\begin{exercise}
Let $X$ and $Y$ be two sets. Let $f:X\rightarrow Y$ be a map.

A \textbf{left inverse} of $f$ means a map $g:Y\rightarrow X$ that satisfies
$g\circ f=\operatorname*{id}\nolimits_{X}$ (but not necessarily $f\circ
g=\operatorname*{id}\nolimits_{Y}$).

A \textbf{right inverse} of $f$ means a map $g:Y\rightarrow X$ that satisfies
$f\circ g=\operatorname*{id}\nolimits_{Y}$ (but not necessarily $g\circ
f=\operatorname*{id}\nolimits_{X}$).

\textbf{(a)} Prove that $f$ has a right inverse if and only if $f$ is surjective.

\textbf{(b)} Assume that $X\neq\varnothing$. Prove that $f$ has a left inverse
if and only if $f$ is injective.

\textbf{(c)} Find two distinct left inverses of the map%
\[%
%TCIMACRO{\TeXButton{tikzpicture}{\begin{tikzpicture}
%\filldraw[fill=cyan!20!white] (0, 1.5) ellipse (1 and 1);
%\node(1) at (0, 2) {$1$};
%\node(2) at (0, 1) {$2$};
%\node(Cname) at (0, 3) {$X$};
%\filldraw[fill=cyan!20!white] (3, 1) ellipse (1 and 1.5);
%\node(5) at (3, 2) {$1$};
%\node(6) at (3, 1) {$2$};
%\node(7) at (3, 0) {$3$};
%\node(Dname) at (3, 3) {$Y$};
%\draw[->, very thick, green!50!black] (1) -- (5);
%\draw[->, very thick, green!50!black] (2) -- (7);
%\end{tikzpicture}}}%
%BeginExpansion
\begin{tikzpicture}
\filldraw[fill=cyan!20!white] (0, 1.5) ellipse (1 and 1);
\node(1) at (0, 2) {$1$};
\node(2) at (0, 1) {$2$};
\node(Cname) at (0, 3) {$X$};
\filldraw[fill=cyan!20!white] (3, 1) ellipse (1 and 1.5);
\node(5) at (3, 2) {$1$};
\node(6) at (3, 1) {$2$};
\node(7) at (3, 0) {$3$};
\node(Dname) at (3, 3) {$Y$};
\draw[->, very thick, green!50!black] (1) -- (5);
\draw[->, very thick, green!50!black] (2) -- (7);
\end{tikzpicture}%
%EndExpansion
\ \ .
\]


\textbf{(d)} Find two distinct right inverses of the map%
\[%
%TCIMACRO{\TeXButton{tikzpicture}{\begin{tikzpicture}
%\filldraw[fill=cyan!20!white] (0, 1) ellipse (1 and 1.5);
%\node(1) at (0, 2) {$1$};
%\node(2) at (0, 1) {$2$};
%\node(3) at (0, 0) {$3$};
%\node(Cname) at (0, 3) {$X$};
%\filldraw[fill=cyan!20!white] (3, 1.5) ellipse (1 and 1);
%\node(5) at (3, 2) {$1$};
%\node(6) at (3, 1) {$2$};
%\node(Dname) at (3, 3) {$Y$};
%\draw[->, very thick, green!50!black] (1) -- (5);
%\draw[->, very thick, green!50!black] (2) -- (6);
%\draw[->, very thick, green!50!black] (3) -- (5);
%\end{tikzpicture}}}%
%BeginExpansion
\begin{tikzpicture}
\filldraw[fill=cyan!20!white] (0, 1) ellipse (1 and 1.5);
\node(1) at (0, 2) {$1$};
\node(2) at (0, 1) {$2$};
\node(3) at (0, 0) {$3$};
\node(Cname) at (0, 3) {$X$};
\filldraw[fill=cyan!20!white] (3, 1.5) ellipse (1 and 1);
\node(5) at (3, 2) {$1$};
\node(6) at (3, 1) {$2$};
\node(Dname) at (3, 3) {$Y$};
\draw[->, very thick, green!50!black] (1) -- (5);
\draw[->, very thick, green!50!black] (2) -- (6);
\draw[->, very thick, green!50!black] (3) -- (5);
\end{tikzpicture}%
%EndExpansion
\ \ .
\]

\end{exercise}

\bigskip

Some exercises on counting will follow now. Recall that $\left[  n\right]  $
denotes the set $\left\{  1,2,\ldots,n\right\}  $ whenever $n\in\mathbb{N}$.

\begin{exercise}
Let $n\in\mathbb{N}$. Compute the \# of $4$-tuples $\left(  a,b,c,d\right)
\in\left[  n\right]  ^{4}$ that satisfy $a\leq b<c\leq d$. (Not a typo: the
second sign is a $<$, not a $\leq$.)

(Recall that $\left[  n\right]  ^{4}=\left[  n\right]  \times\left[  n\right]
\times\left[  n\right]  \times\left[  n\right]  $, so that a $4$-tuple
$\left(  a,b,c,d\right)  \in\left[  n\right]  ^{4}$ means a $4$-tuple of
integers $a,b,c,d\in\left\{  1,2,\ldots,n\right\}  $.)
\end{exercise}

\begin{exercise}
Let $n\in\mathbb{N}$. Compute the \# of pairs $\left(  A,B\right)  $ of
subsets of $\left[  n\right]  $ that satisfy $A\cap B=\varnothing$.

(For example, if $n=2$, then this \# is $9$, since there are $9$ such pairs:%
\begin{align*}
&  \left(  \varnothing,\ \varnothing\right)  ,\qquad\left(  \varnothing
,\ \left\{  1\right\}  \right)  ,\qquad\left(  \varnothing,\ \left\{
2\right\}  \right)  ,\qquad\left(  \varnothing,\ \left\{  1,2\right\}
\right)  ,\\
&  \left(  \left\{  1\right\}  ,\ \varnothing\right)  ,\qquad\left(  \left\{
1\right\}  ,\ \left\{  2\right\}  \right)  ,\qquad\left(  \left\{  2\right\}
,\ \varnothing\right)  ,\qquad\left(  \left\{  2\right\}  ,\ \left\{
1\right\}  \right)  ,\qquad\left(  \left\{  1,2\right\}  ,\ \varnothing
\right)  .
\end{align*}
)
\end{exercise}

\begin{exercise}
A set $S$ of integers will be called \textbf{pseudolacunar} if it has the
property that no two elements $s,t$ of $S$ satisfy $\left\vert s-t\right\vert
=2$. For instance, the set $\left\{  2,5,6\right\}  $ is pseudolacunar, but
the set $\left\{  2,5,7\right\}  $ is not (since $\left\vert 5-7\right\vert
=2$).

For each $n\in\mathbb{N}$, let $p_{n}$ be the \# of pseudolacunar subsets of
$\left[  n\right]  $.

Prove that
\[
p_{n}=p_{n-1}+p_{n-3}+p_{n-4}\ \ \ \ \ \ \ \ \ \ \text{for each }n\geq4.
\]


[\textbf{Hint:} To each pseudolacunar subset, assign one of three colors.]
\end{exercise}

\begin{exercise}
A set $S$ of integers shall be called \textbf{self-starting} if its size
$\left\vert S\right\vert $ is also its smallest element. (For example,
$\left\{  3,5,6\right\}  $ is self-starting, while $\left\{  2,3,4\right\}  $
and $\left\{  3\right\}  $ are not.)

Let $n\in\mathbb{N}$.

\textbf{(a)} For any $k\in\left[  n\right]  $, find the number of
self-starting subsets of $\left[  n\right]  $ having size $k$.

\textbf{(b)} Find the number of all self-starting subsets of $\left[
n\right]  $.
\end{exercise}


\end{document}