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.