HMMT 二月 2010 · 冲刺赛 · 第 19 题

英文解析

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 wayscan the ant make 5 moves and end up on the same vertex it started at?
    Answer: 6240 We let the cube lie in R with each corner with coordinates 1 or 0. Assume the ant 5
    starts at (0 , 0 , 0 , 0 , 0). Every move the ant adds or subtracts 1 to two of the places. Note that thismeans the ant can only land on a vertex with the sum of its coordinates an even number. Every move
    ( )
    the ant has = 10 choices.5
    From any vertex there are 10 two-move sequences that put the ant at the same vertex it started at.2
    There are 6 two-move sequences to move from one vertex to a different, chosen vertex. If your chosenvertex differs from your current vertex by 2 of the 5 coordinates, your first move corrects for one ofthese two. There are 2 ways to choose which coordinate to correct for on the first move, and thereare 3 ways to choose the second coordinate you change, yielding 6 sequences. If your chosen vertexdiffers from your current vertex by 4 of the 5 coordinates, each move corrects for two of these four.
    ( )
    This yields = 6 sequences.4
    Finally, there are 60 three-move sequences that put the ant at the same vertex it started at. There are 2
    10 ways to choose the first move, and there are 6 ways to make two moves to return to your originalposition.
    The motion of the ant can be split into two cases.
    Case 1: After the 3 rd move the ant is on the vertex it started at. There are (60)(10) = 600 differentpossible paths.
    Case 2: After the third move the ant is on a vertex different from the one it started on. There are
    (10 − 60)(6) = (940)(6) = 5640 different possible paths.3
    So there are 6240 total possible paths.
    Guts Round