Maths Olympiad Prep

Library / /170 of 183

, 2024

Combinatorics Difficulty 4.7 AIME Find the answer Canada

A standing desk has 3131
height settings, numbered from the lowest height, 11, to the highest height, 3131. Since the desk is not working
properly, when the up button is pressed, the desk goes up 66 settings at a time if possible,
otherwise it does not move. When the down button is pressed, the desk
goes down 44 settings at a time if
possible, otherwise it does not move. If the desk starts at setting
number 11, how many of the 3131 settings will the desk be able to stop
at?

Pick one

Solution

Beginning at height 1 and moving up 66 settings at a time, the desk can stop
at settings 77, 1313, 1919, 2525, and 3131.

Beginning at height 3131 and moving
down 4 settings at a time, the desk can stop at settings 2727, 2323, 1919, 1515, 1111, 77, and 33.

The desk originally begins at an odd-numbered height, 11.

Moving up 66 settings at a time, the
desk can stop at only odd-numbered heights (since an even number added
to an odd number is odd).

Similarly, moving down 44 settings
at a time, the desk can stop at only odd-numbered heights.

Thus, it is not possible for the desk to stop at an even-numbered
setting.

To this point, we have shown that the desk is able to stop at the
settings 1,3,7,11,13,15,19,23,25,27,31,1,3,7,11,13,15,19,23,25,27,31,and is not
able to stop at even-numbered settings.

Next, we will show that it is possible for the desk to stop at the
remaining odd-numbered settings, 55,
99, 1717, 2121, and 2929.

Since the desk can stop at setting 1313, then it can stop at settings 99 and 55 with one and two presses of the down
button, respectively.

Similarly, since the desk can stop at setting 2525, then it can stop at settings 2121 and 1717.

Finally, since the desk can stop at setting 2323, then one press of the up button will
take the desk to setting 2929.

The desk can stop at all odd-numbered settings from 11 to 3131 inclusive, and thus is able to stop at
1616 different settings.

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

Source: CEMC, University of Waterloo, licensed CC-BY-NC-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.