HMMT 二月 2010 · TEAM1 赛 · 第 8 题

英文解析

8. [ 30 ] A knight moves on a two-dimensional grid. From any square, it can move 2 units in one axisparallel direction, then move 1 unit in an orthogonal direction, the way a regular knight moves in agame of chess. The knight starts at the origin. As it moves, it keeps track of a number t , which isinitially 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 willmake 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]. Butgoing [ x − 1] → [3 x ] → [ x − 1] means we can go from t = a to t = 3 a − 1 at x − 1. Since we can startwith t = − 4, this means we can therefore get arbitrarily small even and odd numbers at [ x − 1], hencealso [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 similarthing starting at [ − x + 1] to get from t = a to t = a + 2, and use the [ − x − 1] → [ − 3 x ] → [ − x − 1] loopto get arbitrarily small integers of both parities. So we can get any value of t we want at all points ofthe form [ ± x + k ] for any integer k .
   n n − 1