Problem 865

Tip: Instead of counting the paths that work, we will count those that do not: a bad path must pass through the right (d) just below the main diagonal. We can look at what happens if we reflect, with respect to (d), the part of the path before it first meets (d): if we choose the bottom left corner as the origin, we get a path from the point with coordinates $(1,0)$ to the top right corner. This is a bijection, so there are $\binom{2 n}{n+1}$ bad paths, and a little calculation shows that there are $\frac{1}{n+1}\binom{2 n}{n}$ good ones.

Remark 1.6. The numbers obtained (the $\frac{1}{n+1}\binom{2 n}{n}$) are called Catalan numbers, and they allow counting a wide variety of combinatorial objects, using bijections with the paths from the exercise. Here are some examples:

- Correct parenthesizations, i.e., the ways to place $n$ opening parentheses and $n$ closing parentheses so that there are never more closing parentheses than opening ones. For example, $(()())$ works but not ()$)(()$.
- The ways to connect two by two with segments $2 n$ points on a circle without any two segments intersecting.
- The ways to go from a point to itself while staying on a half-line starting from that point and taking $2 \mathrm{n}$ steps of 1 meter to the right or to the left.
- The family trees with $n$ vertices describing the descent from a person.

## 2 Group B

## 1 Functions

The notion of function is relatively recent in mathematics, as it is due to Leonhard Euler (1707 - 1783). Most of the theorems you will study in high school are older, including those used to study the variations of a function, such as Rolle's theorem. For before Euler, one knew how to study how a "quantity" varied in relation to another quantity.

Euler's original idea was to introduce a mathematical object "function" that associates a value with a variable. This is a very general notion: the variable and the associated value are not necessarily numbers. And the functions thus defined do not have properties a priori; it is the hypothesis that allows defining properties in relation to the problem posed. Most of the functions you will handle are "good functions," such as polynomial functions or the exponential function, for example. But when you need to solve a very general problem about functions, for example, a functional equation (about $10 \%$ of Olympiad problems are functional equations), even if, in the end, the solution is a very elementary function, you cannot use, in the proof, the assumption that you are looking for a "good function."