HMMT 二月 2010 · COMB 赛 · 第 6 题

HMMT February 2010 — COMB Round — Problem 6

[ 5 ] An ant starts out at (0 , 0). Each second, if it is currently at the square ( x, y ), it can move to ( x − 1 , y − 1), ( x − 1 , y + 1), ( x + 1 , y − 1), or ( x + 1 , y + 1). In how many ways can it end up at (2010 , 2010) after 4020 seconds?

解析

[ 5 ] An ant starts out at (0 , 0). Each second, if it is currently at the square ( x, y ), it can move to ( x − 1 , y − 1), ( x − 1 , y + 1), ( x + 1 , y − 1), or ( x + 1 , y + 1). In how many ways can it end up at (2010 , 2010) after 4020 seconds? ( ) 2 4020 Answer: Note that each of the coordinates either increases or decreases the x and y- 1005 coordinates by 1. In order to reach 2010 after 4020 steps, each of the coordinates must be increased 3015 times and decreased 1005 times. A permutation of 3015 plusses and 1005 minuses for each of x and y uniquely corresponds to a path the ant could take to (2010 , 2010), because we can take ordered pairs from the two lists and match them up to a valid step the ant can take. So the number of ways the ant can end up at (2010 , 2010) after 4020 seconds is equal to the number of ways to arrange plusses ( ) 4020 2 and minuses for both x and y , or ( ) . 1005