Maths Olympiad Prep

Library / /43 of 43

, 2007

Combinatorics Difficulty 7.5 National Olympiad, round 2 Prove it Italy

A flea moves jumping back and forth along a line. The flea's den is a point on the line. The jumping rules are as follows:
- if the flea is at a distance less than or equal to one meter from the den, after the next jump it will be at twice the previous distance, moving even further away from the den.
- if the flea is at a distance dd greater than one meter from the den, after the next jump it will be at a distance 1d\frac{1}{d} from the den but on the opposite side from where it currently is.
If after 5 jumps the flea is at 80 cm80~\mathrm{cm} from the den in a certain direction, with how many distinct sequences of jumps could it have reached that position?

Solution

The answer is 6. We observe first of all that, regardless of the initial position, after the first jump the flea will be at a distance less than or equal to 2 meters from the den and with subsequent jumps it will not be able to reach positions more than two meters from the den.

Note further that, based on the jumping rules, a point at distance xx less than 1/21/2 meter or greater than or equal to one meter from the den can be reached with a jump only starting from the point at distance x/2x/2 from the den.

The positions at distance 1/2≤∣x∣<11/2 \leq |x| < 1 from the den can instead be reached either starting from x/2x/2 or starting from −1/x-1/x. Retracing backwards the route traveled by the flea, these will be positions from which 2 possible backward trajectories start.

Let us try to establish in which positions the flea could have been after the first jump: the final position of the flea is at 4/54/5 meters from the den. This is a branching point: the final position can be reached starting either from 2/5 m2/5~\mathrm{m} or starting from −5/4 m-5/4~\mathrm{m}.

In the first case, 2/5<1/22/5 < 1/2 and so it can be reached only with the sequence 1/20,1/10,1/5,2/51/20, 1/10, 1/5, 2/5. At −5/4-5/4 one arrives only starting from −5/8-5/8, which however is a branching point: it can be reached coming from −5/32,−5/16-5/32, -5/16 or coming from 4/5,8/54/5, 8/5.

Summarizing, there are three possible positions after the first jump (and hence 3 possible sequence of jumps) that allow reaching 4/54/5:
45,85,−58,−54,45;120,110,15,25,45;−532,−516,−58,−54,45. \frac{4}{5}, \frac{8}{5}, -\frac{5}{8}, -\frac{5}{4}, \frac{4}{5} ; \quad \frac{1}{20}, \frac{1}{10}, \frac{1}{5}, \frac{2}{5}, \frac{4}{5} ; \quad -\frac{5}{32}, -\frac{5}{16}, -\frac{5}{8}, -\frac{5}{4}, \frac{4}{5} .
The flea's initial position is not subject to any constraint, in particular it is not necessarily a position reachable with a jump. This means that each of the three positions after a jump is reachable starting from initial situations, that is, respectively, coming from
25 and −54;140 and −20;−564 and 325 \frac{2}{5} \text{ and } -\frac{5}{4} ; \quad \frac{1}{40} \text{ and } -20 ; \quad -\frac{5}{64} \text{ and } \frac{32}{5}
The possible sequences are therefore 6. What has been described is summarized in the figure on the following page.

Figure 1

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from it; metadata (topic, difficulty) added by this project.