HMMT 二月 2010 · 冲刺赛 · 第 19 题
HMMT February 2010 — Guts Round — Problem 19
题目详情
- [ 10 ] A 5-dimensional ant starts at one vertex of a 5-dimensional hypercube of side length 1. A move √ is when the ant travels from one vertex to another vertex at a distance of 2 away. How many ways can the ant make 5 moves and end up on the same vertex it started at?
解析
- [ 10 ] A 5-dimensional ant starts at one vertex of a 5-dimensional hypercube of side length 1. A move √ is when the ant travels from one vertex to another vertex at a distance of 2 away. How many ways can the ant make 5 moves and end up on the same vertex it started at? 5 Answer: 6240 We let the cube lie in R with each corner with coordinates 1 or 0. Assume the ant starts at (0 , 0 , 0 , 0 , 0). Every move the ant adds or subtracts 1 to two of the places. Note that this means the ant can only land on a vertex with the sum of its coordinates an even number. Every move ( ) 5 the ant has = 10 choices. 2 From any vertex there are 10 two-move sequences that put the ant at the same vertex it started at. There are 6 two-move sequences to move from one vertex to a different, chosen vertex. If your chosen vertex differs from your current vertex by 2 of the 5 coordinates, your first move corrects for one of these two. There are 2 ways to choose which coordinate to correct for on the first move, and there are 3 ways to choose the second coordinate you change, yielding 6 sequences. If your chosen vertex differs from your current vertex by 4 of the 5 coordinates, each move corrects for two of these four. ( ) 4 This yields = 6 sequences. 2 Finally, there are 60 three-move sequences that put the ant at the same vertex it started at. There are 10 ways to choose the first move, and there are 6 ways to make two moves to return to your original position. The motion of the ant can be split into two cases. Case 1: After the 3rd move the ant is on the vertex it started at. There are (60)(10) = 600 different possible paths. Case 2: After the third move the ant is on a vertex different from the one it started on. There are 3 (10 − 60)(6) = (940)(6) = 5640 different possible paths. So there are 6240 total possible paths. Guts Round