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?
( )
40202
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 xand y uniquely corresponds to a path the ant could take to (2010 , 2010), because we can take orderedpairs from the two lists and match them up to a valid step the ant can take. So the number of waysthe ant can end up at (2010 , 2010) after 4020 seconds is equal to the number of ways to arrange plusses
( )
4020
and minuses for both x and y , or ( ) .2
1005