HMMT 二月 2010 · TEAM1 赛 · 第 8 题
HMMT February 2010 — TEAM1 Round — Problem 8
题目详情
- [ 30 ] A knight moves on a two-dimensional grid. From any square, it can move 2 units in one axis- parallel direction, then move 1 unit in an orthogonal direction, the way a regular knight moves in a game of chess. The knight starts at the origin. As it moves, it keeps track of a number t , which is initially 0. When the knight lands at the point ( a, b ), the number is changed from x to ax + b . Show that, for any integers a and b , it is possible for the knight to land at the points (1 , a ) and ( − 1 , a ) with t equal to b . Page 1 of 2 n n − 1
解析
- [ 30 ] A knight moves on a two-dimensional grid. From any square, it can move 2 units in one axis- parallel direction, then move 1 unit in an orthogonal direction, the way a regular knight moves in a game of chess. The knight starts at the origin. As it moves, it keeps track of a number t , which is initially 0. When the knight lands at the point ( a, b ), the number is changed from x to ax + b . Show that, for any integers a and b , it is possible for the knight to land at the points (1 , a ) and ( − 1 , a ) with t equal to b . Solution: For convenience, we will refer to ( a, b ) as [ ax + b ], the function it represents. This will make it easier to follow the trajectory of t over a given sequence of moves. Suppose we start at [ x + 1] with t = a . Taking the path [ x + 1] → [ − x ] → [ x − 1] → [ − x ] → [ x + 1] will yield t = a + 2. So we can go from t = a to t = a + 2 at [ x + 1]. We can also move until we get to [ − 3], then go [ − 3] → [ x − 1] to end up with t = − 4 at [ x − 1]. But going [ x − 1] → [3 x ] → [ x − 1] means we can go from t = a to t = 3 a − 1 at x − 1. Since we can start with t = − 4, this means we can therefore get arbitrarily small even and odd numbers at [ x − 1], hence also [3 x ], hence also at [ x + 1]. This implies we can get any value of t we want at [ x + 1], so we can also get any value of t we want at [ − x ], [ x − 1], [ − x − 2], [ x − 3], etc., as well as [ − x + 2], [ x + 3], [ − x + 4], [ x + 5], etc. We can do a similar thing starting at [ − x + 1] to get from t = a to t = a + 2, and use the [ − x − 1] → [ − 3 x ] → [ − x − 1] loop to get arbitrarily small integers of both parities. So we can get any value of t we want at all points of the form [ ± x + k ] for any integer k . n n − 1