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 be the number of elms between positions and ; we are asked to prove that there exists a such that . Note that , since that includes all the trees exactly once. By symmetry, we can assume that and . Note also that the sets considered for and differ by only one tree, hence . Looking at the sequence we need to go from an integer below to an integer above by taking steps of size or . At some point, we will necessarily go through .

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.

### Like this:

Like Loading...

*Related*

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.

04/04/2010 at 22:12 |

[…] 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 […]