## Task 1 - 191231

Let $n$ and $m$ be natural numbers with $n \geq 1, m \geq 1$; $N$ be the set of natural numbers from 1 to $n$ and $M$ the set of natural numbers from 1 to $m$.

Determine the number of all those subsets of $N$ that have common elements with $M$.
A subset of $N=\{1,2, \ldots, n\}$ has obviously no common elements with $M=\{1,2, \ldots, m\}$ if and only if it is also a subset of $M \backslash N$.

By subtracting the number of these from the total number of subsets of $N$, we then obtain for the number $A_{m, n}$ of all subsets of $N$ that have common elements with $M$,

$$
A_{m, n}= \begin{cases}2^{n}-1, & \text { if } n \leq m \\ 2^{n-m}\left(2^{m}-1\right), & \text { if } n>m\end{cases}
$$

or, summarized,

$$
A_{m, n}=2^{n}-2^{\max (n-m, 0)}
$$