PUMaC 2012 · 团队赛 · 第 12 题
PUMaC 2012 — Team Round — Problem 12
题目详情
- (5 digits) You and your friend play the following dangerous game. You two start off at some point ( x, y ) on the plane, where x and y are nonnegative integers. When it is player A ’s turn, A tells his opponent B to move to another point on the plane. Then A waits for a while. If B is not eaten by a tiger, then A moves to that point as well. From a point ( x, y ) there are three places A can tell B to walk to: leftwards to ( x − 1 , y ), downwards to ( x, y − 1), and simultaneously downwards and leftwards to ( x − 1 , y − 1). However, you cannot move to a point with a negative coordinate. Now, what was this about being eaten by a tiger? There is a tiger at the origin, which will eat the first person that goes there! Needless to say, you lose if you are eaten. Consider all possible starting points ( x, y ) with 0 ≤ x ≤ 346 and 0 ≤ y ≤ 346, and x and y are not both zero. Also suppose that you two play strategically, and you go first (i.e., by telling your friend where to go). For how many of the starting points do you win? 2 4 πi/ 3 2.2 Down and to the left ( e ) √
解析
- Problem: (5 digits) You and your friend play the following dangerous game. You two start off at some point ( x, y ) on the plane, where x and y are nonnegative integers. When it is player A ’s turn, A tells his opponent B to move to another point on the plane. Then A waits for a while. If B is not eaten by a tiger, then A moves to that point as well. From a point ( x, y ) there are three places A can tell B to walk to: leftwards to ( x − 1 , y ), downwards to ( x, y − 1), and simultaneously downwards and leftwards to ( x − 1 , y − 1). However, you cannot move to a point with a negative coordinate. Now, what was this about being eaten by a tiger? There is a tiger at the origin, which will eat the first person that goes there! Needless to say, you lose if you are eaten. Consider all possible starting points ( x, y ) with 0 ≤ x ≤ 346 and 0 ≤ y ≤ 346, and x and y are not both zero. Also suppose that you two play strategically, and you go first (i.e., by telling your friend where to go). For how many of the starting points do you win? Answer: 90133 Solution: Let’s include the origin as a starting point since it will not affect the count. If we work backwards starting from the origin, we see that you will win if and only if at least one of coordinates the starting point ( x, y ) is odd. The starting points where you would lose are { (2 a, 2 b ) : 0 ≤ a ≤ 174 , 0 ≤ b ≤ 174 } 2 2 2 Thus, there are 174 bad points, so 347 − 174 = 90133 good points. Author: Alan 4 πi/ 3 2.2 Down and to the left ( e ) √