HMMT 二月 2010 · TEAM1 赛 · 第 1 题
HMMT February 2010 — TEAM1 Round — Problem 1
题目详情
- You are trying to sink a submarine. Every second, you launch a missile at a point of your choosing on the x -axis. If the submarine is at that point at that time, you sink it. A firing sequence is a sequence of 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 hit the submarine eventually. (b) [ 10 ] Suppose now that the submarine starts at an unknown integer point on the non-negative x -axis and again travels with an unknown positive integer velocity. Show that there is still a firing sequence that is guaranteed to hit the submarine eventually.
解析
- You are trying to sink a submarine. Every second, you launch a missile at a point of your choosing on the x -axis. If the submarine is at that point at that time, you sink it. A firing sequence is a sequence of 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 hit the submarine eventually. 2 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 . (b) [ 10 ] Suppose now that the submarine starts at an unknown integer point on the non-negative x -axis and again travels with an unknown positive integer velocity. Show that there is still a firing 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 starting point of the submarine and b is its velocity. We want to find a way to map each positive integer to a possible ordered pair so that every ordered pair is covered. This way, if we fire at b n + a n n at 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 many n n such 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 and ordered pairs of integers ( a, b ) where b > 0.