Skip to main content
OlympiadHQ

Browse · MathNet

Print

51st Ukrainian National Mathematical Olympiad, 4th Round

Ukraine counting and probability

Problem

There are burrows on a straight line. Mouse Jerry is hiding in one of these burrows. Cat Tom has a possibility to put his paw into one of the burrows and to catch Jerry if he is hiding in this burrow. After every Tom's attempt Jerry necessarily runs to the neighboring (left or right) burrow. Can Tom always catch Jerry?
Solution
Enumerate the burrows from left to right with numbers from to and define the "distance" between the burrows and by (it can be negative).

First Tom checks all the burrows from to one after another. If at the moment when Tom checks the first burrow Jerry is in a burrow with an odd number, then Tom will necessarily catch Jerry during this check.

Indeed, if at the moment when Tom checks the first burrow there is no Jerry, then at this moment the "distance" between them is a positive even number. If he still did not catch Jerry when he checks the last burrow, this would mean that the "distance" between them at this moment is a negative even number. Note, that after every Jerry's run and Tom's move the "distance" between them either does not change (if they move in the same direction) or changes by (if they move in different directions). So if we start with a positive even number and end up with a negative even number, there should be a moment when the "distance" between them is zero, which means that Tom catches Jerry.

If at the beginning Jerry is in a burrow with an even number, then at the moment when Tom checks the -th burrow, Jerry will be in a burrow with a number of the different parity than . After this Jerry moves to the burrow with a number of the same parity as . So, if now Tom checks all the burrows from to one after another, he will necessarily catch Jerry by the above arguments because the "distance" between them is now even.
Final answer
Yes, Tom can always catch Jerry.

Techniques

Invariants / monovariantsGames / greedy algorithms