Maths Olympiad Prep

Library / /326 of 348

Combinatorics Difficulty 5.2 AIME, harder Find the answer

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. Spacing and $ signs are ignored.

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)(mod10)A_{(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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.