Find all functions $f: \mathbb{N}^{*} \rightarrow \mathbb{N}^{*}$ such that $f(1)+f(2)+\cdots+f(n) \mid 1+2+\ldots n$ for all $n>0$.

## Solutions
On $f(1) \mid 1$, so $f(1)=1$. Then, $1+f(2) \mid 3$, and $f(2)=2$ because $f(2)>0$. Next, $3+f(3) \mid 6$, and again $f(3)=3$ because $f(3)>0$. We can thus conjecture that $f(n)=n$ for all $n$, which we will prove by strong induction.

Initialization: We have just shown that $f(1)=1, f(2)=2, f(3)=3$.

Induction: Let $n \geqslant 3$ such that $f(i)=i$ for all $i \leqslant n$.

Then $1+2+\cdots+n+f(n+1) \mid 1+2+\ldots n+1$, so $\left.\frac{n(n+1)}{2}+f(n+1) \right\rvert\, \frac{(n+1)(n+2)}{2}$.

For $n \geqslant 3, \frac{\frac{n(n+1)}{2}}{\frac{(n+1)(n+2)}{2}}=\frac{n}{n+2}=1-\frac{2}{n+2}>\frac{1}{2}$, so $\frac{n(n+1)}{2}+f(n+1)>\frac{n(n+1)}{2}>$ $\frac{1}{2} \frac{(n+1)(n+2)}{2}$. The only possible integer value for $\frac{\frac{(n+1)(n+2)}{2}}{\frac{n(n+1)}{2}+f(n+1)}$ is thus 1, or equivalently $f(n+$ $1)=n+1$, as desired.

Thus our induction holds, and $f(n)=n$ for all $n>0$.

## 2 Pigeonhole Principle (Angela)

## Intuitive Idea

Suppose there are $n$ drawers and $n+1$ socks placed in these drawers. There is at least one drawer containing at least two socks.

Theorem 1 (Pigeonhole Principle).

More generally, if $n$ elements must be placed in $k$ drawers, then there is at least one drawer that contains at least $\left\lceil\frac{n}{k}\right\rceil$ elements.

Note: $\lceil x\rceil$ denotes the ceiling function, i.e., the unique integer such that $x \leqslant\lceil x\rceil<x+1$.

## Example 2.

How many children are needed in a school to ensure that at least 3 of them have their birthday on the same day?

If there are 733 students, then by the pigeonhole principle, we are guaranteed to have at least three students who have the same birthday (there are 366 possible dates). This number is minimal because there exists a configuration with 732 students without having three students with the same birthday.

The pigeonhole principle is a very simple and intuitive concept, but its consequences can be quite impressive. This type of reasoning is particularly effective for problems requiring the proof of the existence of an element. Of course, one must know how to identify the drawers and the socks, which can be very challenging.