In any sequence of $n^2 + 1$ distinct real numbers, there exists either an increasing subsequence of length $n+1$ or a decreasing subsequence of length $n+1$.

Proof sketch: Label each element $a_i$ in the sequence with $(x_i, y_i)$ where $x_i$ is the length of the longest increasing subsequence ending at $a_i$ and $y_i$ is the length of the longest decreasing subsequence ending at $a_i$.

If no increasing or decreasing subsequence has length $n+1$, then all labels $(x_i, y_i)$ satisfy $1 \leq x_i \leq n$ and $1 \leq y_i \leq n$. This gives only $n^2$ possible labels. With $n^2 + 1$ elements, by the pigeonhole principle, two elements $a_i$ and $a_j$ (with $i < j$) must have the same label.

But if $a_i < a_j$, then $x_j > x_i$ (contradiction), and if $a_i > a_j$, then $y_j > y_i$ (contradiction). Therefore, some sequence must have length $n+1$.

In any graph with $n$ vertices and chromatic number $\chi(G)$, there exists an independent set of size at least $\lceil n/\chi(G) \rceil$.

Proof: In a proper $k$-coloring of $G$ (where $k = \chi(G)$), vertices are partitioned into $k$ color classes, each forming an independent set. By the pigeonhole principle, at least one color class contains at least $\lceil n/k \rceil$ vertices.

Euler's totient function $\phi(n)$, which counts integers from 1 to $n$ that are coprime to $n$, can be computed using inclusion-exclusion. If $n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$, then: $\phi(n) = n \prod_{i=1}^{k} \left(1 - \frac{1}{p_i}\right)$

This follows from inclusion-exclusion: let $A_i$ be the set of integers from 1 to $n$ divisible by $p_i$. Then: $\phi(n) = n - \left|\bigcup_{i=1}^{k} A_i\right|$

Applying inclusion-exclusion: $= n - \sum_{i} \frac{n}{p_i} + \sum_{i<j} \frac{n}{p_i p_j} - \sum_{i<j<\ell} \frac{n}{p_i p_j p_\ell} + \cdots$ $= n\left(1 - \sum_i \frac{1}{p_i} + \sum_{i<j} \frac{1}{p_i p_j} - \cdots\right) = n\prod_{i=1}^{k}\left(1 - \frac{1}{p_i}\right)$

How many functions $f: \{1,2,3,4,5\} \to \{1,2,3\}$ are there such that $f$ is onto (surjective)?

Using inclusion-exclusion, let $A_i$ be the set of functions that do not map to $i$. We want $|A_1^c \cap A_2^c \cap A_3^c|$, which by complement equals the total minus $|A_1 \cup A_2 \cup A_3|$.

Total functions: $3^5 = 243$

$|A_1| = |A_2| = |A_3| = 2^5 = 32$ (functions using only 2 values)

$|A_1 \cap A_2| = |A_1 \cap A_3| = |A_2 \cap A_3| = 1^5 = 1$ (functions using only 1 value)

$|A_1 \cap A_2 \cap A_3| = 0$ (impossible to map to no values)

By inclusion-exclusion: $|A_1 \cup A_2 \cup A_3| = 3(32) - 3(1) + 0 = 96 - 3 = 93$

Therefore, the number of onto functions is $243 - 93 = 150$.