Wednesday, 24 November 2010

Catching a spy and Infinity

I apologize for the hiatus, but I have been buried under overwhelming quantities of work lately. I'll take a break from the regular expression program to show you a puzzle I've found quite interesting:

Catching a spy

A spy is located on a one-dimensional line. At time 0, the spy is at location A. With each time interval, the spy moves B units to the right (if B is negative, the spy is moving left). A and B are fixed integers, but they are unknown to you. You are to catch the spy. The means by which you can attempt to do that is: at each time interval (starting at time 0), you can choose a location on the line and ask whether or not the spy is currently at that location. That is, you will ask a question like "Is the spy currently at location 27?" and you will get a yes/no answer. Devise an algorithm that will eventually find the spy.
 

Whoa, that looks quite difficult. Not only do you not know where A is (and there's a lot of places where it could be) but you don't know the spy's velocity either (or direction!). Do not fret, let's make baby steps.

First step: Since the numbers of unknowns and cases is quite large, let's answer a simple version of the question. Set A at 0 and let B only be positive. This means that we know that the thief starts from A = 0 and he's only moving towards the right. What now? Well, let's systematically try and eliminate values of B. Assume B = 1. Then, to rule this option out just ask at t = 1 “Is the spy at position 1?”. If he's not, that means that B 1. Ok, what about B = 2? At t = 2 ask “Is the spy at position 4?” as this is where he would be if B = 2. If he's not, that means that B 2. Keep going this way and at moment t ask “Is the spy at position B*t?”. Since we are systematically working our way up through the possible values of B, we know that after B questions we will find the thief!

Second step: Let's look at a more general case. Let B be negative as well. We have more possibilities to worry about (actually, it's just as many as before. Infinity is weird like that.). We can't try and be done with the positive values first and then start working on the negative ones, as we will never get there. Instead, we need to creep our way both directions at the same time. Alternate the positive and negative values of B that we are eliminating with each question. That is eliminate: 1, -1, 2, -2, 3, -3 etc. (Can you work out what positions you have to inquire about at each t?)

Third step: Great, now that we know how to check for all B, we can start worrying about the values of A which, until now, has been fixed. Oh dear, it looks like too many things are moving at the same time! Let's take a look at this (simple) table. Each row lists a value of A and each column a value of B. What we have to do now is find a way to traverse this table by making sure we hit each cell after only a finite amount of time. 

 

Note: We can work out a formula which tells us about which position to enquire at a given time. So, at moment t, if we want to eliminate value a for A and value b for B we can ask about position s(t,a,b) = a + t*b, since that is where the spy would be at that time.

How should we walk around the table? Trying to check the first row first would not work as we will never start checking the second row. Trying to go for the first column would not work either, for the same reason. Fear not, for there is a solution, given by Cantor. Simply take the following path. I'll let you figure out why each cell will be reached after a finite amount of time.



Here's some generalizations you might want to think about. It would help if you have some notions of infinity before thinking about some of these:
  1. What if the spy runs around in 2 dimensions? That is, he is either moving up, down, left or right.
  2. What about 3 dimensions? 4? Countably infinite ones?
  3. What if A = 0 and B can take real values?
  4. What if A = 0 and B can take positive real values, but at any given time t you can ask “Is the spy in the vicinity of x?” where x is a real number and by “vicinity” you mean in the interval (x-d, x+d) for a given, fixed d.
  5. Same as above, but B can also be negative.
  6. Same as above again, but now both A and B can take real values?

1 comment:

  1. A very nice problem and very nicely explaining solution :)

    ReplyDelete