Olympiad Maths Prep

Library / /21 of 22

Combinatorics Difficulty 6.4 National olympiad Prove it Ukraine

There are n3n \ge 3 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 11 to nn and define the "distance" between the burrows ii and jj by iji - j (it can be negative).

First Tom checks all the burrows from 11 to nn 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 22 (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 nn-th burrow, Jerry will be in a burrow with a number of the different parity than nn. After this Jerry moves to the burrow with a number of the same parity as nn. So, if now Tom checks all the burrows from nn to 11 one after another, he will necessarily catch Jerry by the above arguments because the "distance" between them is now even.

Looking for a route rather than 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 and solution reproduced as published; topic and difficulty added by this site.