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.

One thought on “Le Monde problem: “Nationale 7”

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s