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.

About these ads

Tags: Le Monde

This entry was posted on 23/03/2010 at 16:19 and is filed under Mathematical games. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

One Response to “Le Monde problem: “Nationale 7″”

Le Monde rank test « Xi'an's Og Says:
04/04/2010 at 22:12 | Reply
[...] a Brownian bridge crosses the axis in-between and but I have no clue whether this helps or not! Robin Ryder solved the question for the values and by establishing that the probability is still [...]

Robin Ryder's blog