HMMT 二月 2009 · 冲刺赛 · 第 31 题

英文解析

31. [ 18 ] How many ways are there to win tic-tac-toe in R ? (That is, how many lines pass through threenof the lattice points ( a , . . . , a ) in R with each coordinate a in { 1 , 2 , 3 } ?) Express your answer in
    1 n iterms of n .
    n n
    Answer: (5 − 3 ) / 2 Solution: A line consists of three points. Each coordinate can do oneof three things passing from the first point to the last point: increase by 1 each time, stay the same,
    or decrease by 1 each time. There are three ways to stay the same (three coordinates), one way tonincrease by 1, and one way to decrease by 1, so there are 5 possible types of behavior. Determiningthis behavior uniquely determines the end point and start point except that we have traced every lineexactly twice (forwards and backwards) and incorrectly counted the 3 “lines” where each coordinatennstays the same, so we subtract 3 and divide by 2. 7