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

HMMT February 2009 — Guts Round — Problem 31

[ 18 ] How many ways are there to win tic-tac-toe in R ? (That is, how many lines pass through three n of the lattice points ( a , . . . , a ) in R with each coordinate a in { 1 , 2 , 3 } ?) Express your answer in 1 n i terms of n .

解析

[ 18 ] How many ways are there to win tic-tac-toe in R ? (That is, how many lines pass through three n of the lattice points ( a , . . . , a ) in R with each coordinate a in { 1 , 2 , 3 } ?) Express your answer in 1 n i terms of n . n n Answer: (5 − 3 ) / 2 Solution: A line consists of three points. Each coordinate can do one of 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 to n increase by 1, and one way to decrease by 1, so there are 5 possible types of behavior. Determining this behavior uniquely determines the end point and start point except that we have traced every line n exactly twice (forwards and backwards) and incorrectly counted the 3 “lines” where each coordinate n stays the same, so we subtract 3 and divide by 2. 7