Notices
Results 1 to 7 of 7

Thread: Another puzzle:

  1. #1 Another puzzle: 
    Forum Professor river_rat's Avatar
    Join Date
    Jun 2006
    Location
    South Africa
    Posts
    1,517
    A submarine is travelling with constant speed on a one-dimensional grid. Its position at the end of every minute is always an integer and its velocity per minute is also an integer. You can specify a number for each minute and a missile will hit that number on the grid at the end of the minute.

    Does there exist a strategy so that you are guaranteed to hit the vessel at some future time even though you don't know its position and velocity?

    (I've worked out a "mathematical" solution but i'm interested to see if anyone has one that doesn't need the maths)


    As is often the case with technical subjects we are presented with an unfortunate choice: an explanation that is accurate but incomprehensible, or comprehensible but wrong.
    Reply With Quote  
     

  2.  
     

  3. #2  
    Forum Professor sunshinewarrior's Avatar
    Join Date
    Sep 2007
    Location
    London
    Posts
    1,525
    Just to clarify - this grid is unbounded? Infinitely long in either direction?

    And the submarine, are there any hidden assumptions - it only moves in one direction?


    Reply With Quote  
     

  4. #3  
    Forum Professor river_rat's Avatar
    Join Date
    Jun 2006
    Location
    South Africa
    Posts
    1,517
    1. The grid is unbounded (it is more of a line then a grid, i just used the language the problem was originally phrased in when i found it)

    2. No other assumptions about the submarine other then what is stated.
    As is often the case with technical subjects we are presented with an unfortunate choice: an explanation that is accurate but incomprehensible, or comprehensible but wrong.
    Reply With Quote  
     

  5. #4  
    Forum Professor river_rat's Avatar
    Join Date
    Jun 2006
    Location
    South Africa
    Posts
    1,517
    no takers?
    As is often the case with technical subjects we are presented with an unfortunate choice: an explanation that is accurate but incomprehensible, or comprehensible but wrong.
    Reply With Quote  
     

  6. #5  
    Forum Professor serpicojr's Avatar
    Join Date
    Jul 2007
    Location
    JRZ
    Posts
    1,069
    Okay, here's a solution... It's probably along the lines of what you did. So the submarine's position at time t is determined by its initial position p and velocity v--namely, assuming we start at t = 0, the submarine is at the point p + tv at time t. The space of such initial conditions is countable--p and t are integers. So by choosing some ordering on Z^2 (for example (a,b) < (c,d) if |a|+|b| < |c|+|d|; if they're equal, then if a < c; and if these are equal, if b < d), we can list the initial conditions in a sequence (p_t, v_t), t = 0, 1, ... Then I'd send a missile to p_t + tv_t at time t.

    My motivation? Cantor's diagonal argument, of course!
    Reply With Quote  
     

  7. #6  
    Forum Professor river_rat's Avatar
    Join Date
    Jun 2006
    Location
    South Africa
    Posts
    1,517
    Same as mine, i was wondering if you can give a strategy that does not use the fact that ZxZ is countable (so you can give this problem to people without maths backgrounds). I'm stumped there, so i reverted to giving an example of the surjection from N onto NxN (changing the problem accordingly) on another forum but it is not ideal.
    As is often the case with technical subjects we are presented with an unfortunate choice: an explanation that is accurate but incomprehensible, or comprehensible but wrong.
    Reply With Quote  
     

  8. #7  
    Forum Professor sunshinewarrior's Avatar
    Join Date
    Sep 2007
    Location
    London
    Posts
    1,525
    A-ha! I thought of Cantor's diagonal counting argument - but couldn't see how it could apply. Thanks for that (once I've figured it out).
    Reply With Quote  
     

Bookmarks
Bookmarks
Posting Permissions
  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •