HMMT 十一月 2016 · 团队赛 · 第 7 题

英文解析

7. [ 6 ] Rachel has two indistinguishable tokens, and places them on the first and second square of a 1 × 6
   grid of squares, She can move the pieces in two ways:
   • If a token has free square in front of it, then she can move this token one square to the right
   • If the square immediately to the right of a token is occupied by the other token, then shecan“leapfrog” the first token; she moves the first token two squares to the right, over the othertoken, so that it is on the square immediately to the right of the other token.
   If a token reaches the 6 th square, then it cannot move forward any more, and Rachel must move the other one until it reaches the 5 th square. How many different sequences of moves for the tokens can
   Rachel make so that the two tokens end up on the 5 th square and the 6 th square?
   Proposed by: Christopher Shao
   Answer: 42
   We put a marker on ( i, j ) when a token is on i th and j th square and i > j . When the token infront/behind moves one step forward to a blank square, move the marker rightward/upward one unitcorrespondingly. When a ”leapfrog” happens, the marker moves from ( x − 1 , x ) to ( x, x + 1). We cantranslate this movement into: 1. move the marker upward to ( x, x ); 2. move the marker rightwardto ( x, x + 1). Thus, we set up a lattice path way from (2 , 1) to (6 , 5) staying under y = x . This is abijection since every intersection of the path way and y = x indicates a ”leapfrog”. According to thedefinition of Catalan Number, the answer is the number of such lattice path ways, which is C = 42. 5