HMMT 十一月 2009 · 冲刺赛 · 第 2 题

HMMT November 2009 — Guts Round — Problem 2

[ 5 ] A knight begins on the lower-left square of a standard chessboard. How many squares could the knight end up at after exactly 2009 legal knight’s moves? (A knight’s move is 2 squares either horizontally or vertically, followed by 1 square in a direction perpendicular to the first.)

解析

[ 5 ] A knight begins on the lower-left square of a standard chessboard. How many squares could the knight end up at after exactly 2009 legal knight’s moves? (A knight’s move is 2 squares either horizontally or vertically, followed by 1 square in a direction perpendicular to the first.) Answer: 32 The knight goes from a black square to a white square on every move, or vice versa, so after 2009 moves he must be on a square whose color is opposite of what he started on. So he can only land on half the squares after 2009 moves. Note that he can access any of the 32 squares (there are no other parity issues) because any single jump can also be accomplished in 3 jumps, so with 2009 jumps, he can land on any of the squares of the right color.