HMMT 十一月 2022 · GEN 赛 · 第 5 题

HMMT November 2022 — GEN Round — Problem 5

An apartment building consists of 20 rooms numbered 1 , 2 , . . . , 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 i to room ( i + 1) (mod 20)) or walk across the center to the opposite room (i.e. from room i to room ( i + 10) (mod 20)). Find the number of ways to move from room 10 to room 20 without visiting the same room twice.

解析

An apartment building consists of 20 rooms numbered 1 , 2 , . . . , 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 i to room ( i + 1) (mod 20)) or walk across the center to the opposite room (i.e. from room i to room ( i + 10) (mod 20)). Find the number of ways to move from room 10 to room 20 without visiting the same room twice. Proposed by: Papon Lapate Answer: 257 Solution: One way is to walk directly from room 10 to 20. Else, divide the rooms into 10 pairs A = (10 , 20) , A = (1 , 11) , A = (2 , 12) , ..., A = (9 , 19). Notice that 0 1 2 9 • each move is either between rooms in A and A for some i ∈ { 0 , 1 , ..., 9 } , or between i ( i +1) (mod 10) rooms in the same pair, meaning that our path must pass through A , A , ..., A in that order 0 1 9 before coming back to room 20 in A , 0 • in each of the pairs A , A , ..., A , we can choose to walk between rooms in that pair 0 or 1 times, 1 2 8 and • we have to walk between rooms 9 and 19 if and only if we first reach A at room 9 (so the choice 9 of walking between A is completely determined by previous choices). 9 8 Thus, the number of ways to walk from room 10 to 20 is 1 + 2 = 257.