HMMT 二月 2012 · TEAM1 赛 · 第 6 题
HMMT February 2012 — TEAM1 Round — Problem 6
题目详情
- [ 30 ] It has recently been discovered that the right triangle with vertices (0,0), (0,2012), and (2012,0) is a giant pond home to many frogs. Frogs have the special ability that, if they are at a lattice point ( x, y ), they can hop to any of the three lattice points ( x + 1 , y + 1), ( x − 2 , y + 1), ( x + 1 , y − 2), assuming the given lattice point lies in or on the boundary of the triangle. Frog Jeff starts at the corner (0 , 0), while Frog Kenny starts at the corner (0 , 2012). Show that the set of points Jeff can reach is equal in size to the set of points that Kenny can reach.
解析
- [ 30 ] It has recently been discovered that the right triangle with vertices (0,0), (0,2012), and (2012,0) is a giant pond that is home to many frogs. Frogs have the special ability that, if they are at a lattice point ( x, y ), they can hop to any of the three lattice points ( x +1 , y +1), ( x − 2 , y +1), and ( x +1 , y − 2), assuming the given lattice point lies in or on the boundary of the triangle. Frog Jeff starts at the corner (0 , 0), while Frog Kenny starts at the corner (0 , 2012). Show that the set of points that Jeff can reach is equal in size to the set of points that Kenny can reach. Answer: see below Team A √ y 3 ( x, y ) 7 → ( x + , y ) 2 2 We transform the triangle as follows: map each lattice point ( x, y ) to the point √ √ x (1 , 0) + y (1 / 2 , 3 / 2) = ( x + y/ 2 , y 3 / 2). This transforms the right triangle into an equilateral triangle as shown above. Now, the three allowed movements ( x, y ) 7 → ( x + 1 , y + 1) , ( x, y ) 7 → ( x − 2 , y + 1) , ( x, y ) 7 → ( x + 1 , y − 2) become the movements √ ( x, y ) 7 → ( x + 3 / 2 , y + 3 / 2) , √ ( x, y ) 7 → ( x − 3 / 2 , y + 3 / 2) , √ ( x, y ) 7 → ( x, y − 3) √ ◦ That is, each step is a movement of 3 in any of these three directions, which are separated by 120 ◦ angles. The pond is now completely symmetrical with respect to 120 rotations, so it does not matter which vertex you start at. The lower left vertex corresponds to the original point (0 , 0), and the top vertex corresponds to the original point (0 , 2012).