An apartment building consists of 20 rooms numbered 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 to room or walk across the center to the opposite room (i.e. from room to room . Find the number of ways to move from room 10 to room 20 without visiting the same room twice.
Solution
One way is to walk directly from room 10 to 20 . Else, divide the rooms into 10 pairs . Notice that - each move is either between rooms in and for some , or between rooms in the same pair, meaning that our path must pass through in that order before coming back to room 20 in - in each of the pairs , 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 at room 9 (so the choice of walking between is completely determined by previous choices). Thus, the number of ways to walk from room 10 to 20 is .
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.