Maths Olympiad Prep

Library / /246 of 740

Combinatorics Difficulty 4.9 AIME Find the answer United States

Problem:

An apartment building consists of 20 rooms numbered 1,2,,201, 2, \ldots, 20 arranged clockwise in a circle. To move from one room to another, one can either walk to the next room clockwise (i.e. from room ii to room (i+1)mod20(i+1) \bmod 20) or walk across the center to the opposite room (i.e. from room ii to room (i+10)mod20(i+10) \bmod 20). Find the number of ways to move from room 10 to room 20 without visiting the same room twice.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Solution:

One way is to walk directly from room 10 to 20. Else, divide the rooms into 10 pairs A0=(10,20),A1=(1,11),A2=(2,12),,A9=(9,19)A_{0} = (10, 20), A_{1} = (1, 11), A_{2} = (2, 12), \ldots, A_{9} = (9, 19). Notice that
- each move is either between rooms in AiA_{i} and A(i+1)mod10A_{(i+1) \bmod 10} for some i{0,1,,9}i \in \{0, 1, \ldots, 9\}, or between rooms in the same pair, meaning that our path must pass through A0,A1,,A9A_{0}, A_{1}, \ldots, A_{9} in that order before coming back to room 20 in A0A_{0},
- in each of the pairs A1,A2,,A8A_{1}, A_{2}, \ldots, A_{8}, we can choose to walk between rooms in that pair 0 or 1 times, and
- we have to walk between rooms 9 and 19 if and only if we first reach A9A_{9} at room 9 (so the choice of walking between A9A_{9} is completely determined by previous choices).

Thus, the number of ways to walk from room 10 to 20 is 1+28=2571 + 2^{8} = 257.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.