HMMT 二月 2010 · TEAM1 赛 · 第 1 题

英文解析

1. You are trying to sink a submarine. Every second, you launch a missile at a point of your choosing onthe x -axis. If the submarine is at that point at that time, you sink it. A firing sequence is a sequenceof real numbers that specify where you will fire at each second. For example, the firing sequence
   2 , 3 , 5 , 6 , . . . means that you will fire at 2 after one second, 3 after two seconds, 5 after three seconds,
   6 after four seconds, and so on.
   (a) [ 5 ] Suppose that the submarine starts at the origin and travels along the positive x -axis with an
   (unknown) positive integer velocity. Show that there is a firing sequence that is guaranteed to hitthe submarine eventually.
   Solution: The firing sequence 1 , 4 , 9 , . . . , n , . . . works. If the velocity of the submarine is v ,2
   then after v seconds it will be at x = v , the same location where the mine explodes at time v .2
   (b) [ 10 ] Suppose now that the submarine starts at an unknown integer point on the non-negativex -axis and again travels with an unknown positive integer velocity. Show that there is still afiring sequence that is guaranteed to hit the submarine eventually.
   Solution: Represent the submarine’s motion by an ordered pair ( a, b ), where a is the startingpoint of the submarine and b is its velocity. We want to find a way to map each positive integerto a possible ordered pair so that every ordered pair is covered. This way, if we fire at b n + an nat time n , where ( a , b ) is the point that n maps to, then we will eventually hit the submarine.
   n n
   (Keep in mind that b n + a would be the location of the submarine at time n .) There are manyn nsuch ways to map the positive integers to possible points; here is one way:
   1 → (1 , 1) , 2 → (2 , 1) , 3 → (1 , 2) , 4 → (3 , 1) , 5 → (2 , 2) , 6 → (1 , 3) , 7 → (4 , 1) , 8 → (3 , 2) ,
   9 → (2 , 3) , 10 → (1 , 4) , 11 → (5 , 1) , 12 → (4 , 2) , 13 → (3 , 3) , 14 → (2 , 4) , 15 → (1 , 5) , . . .
   (The path of points trace out diagonal lines that sweep every lattice point in the coordinate plane.)
   Since we cover every point, we will eventually hit the submarine.
   Remark: The mapping shown above is known as a bijection between the positive integers andordered pairs of integers ( a, b ) where b > 0.