## Le Monde problem: “Nationale 7”

It seems that solving mathematical puzzles from Le Monde is becoming the main focus of this blog. This week’s problem is about a road with 100 trees: 50 elms and 50 plane trees, in a random order. We are asked to show that whatever the order of the trees, there exists a sequence of 50 consecutive trees with exactly 25 elms and 25 plane trees.

Let $v_k (k=1,\ldots 51)$ be the number of elms between positions $k$ and $k+49$; we are asked to prove that there exists a $k$ such that $v_k=25$. Note that $v_1+v_{51}=50$, since that includes all the trees exactly once. By symmetry, we can assume that $v_1\leq 25$ and $v_{51}\geq 25$. Note also that the sets considered for $v_k$ and $v_{k+1}$ differ by only one tree, hence $| v_k - v_{k+1} | \leq 1$. Looking at the sequence $(v_k)$ we need to go from an integer below $25$ to an integer above $25$ by taking steps of size $0$ or $1$. At some point, we will necessarily go through $25$.

The exact same proof holds with only 98 trees (49 of each species). However, going down to 96 trees (48 of each), the following arrangement has no set of 50 consecutive trees with half of each: 24 elms, then 48 plane trees, then 24 elms.