[hristov]

It can be done. Imagine a two dimensional array. One dimension corresponds to A and the other to B. Each cell in the array, corresponds to one possibility of the values of A and B.

At a time X, the spy is in a position (A+BX). At each time you pick a cell, and then guess the position associated with the A and B values of that cell. So for example, at time zero, you can pick cell (1, 1) which corresponds to position 1+0x1=1. So you guess 1. Then at time 1 you can pick cell (1,2), which corresponds to position 1+2x1=3. So you guess 3.

Every time you make a wrong guess, you cross out the cell associated with your guess. But you also cross out all cells which would have resulted in the erroneous position you picked. Thus, taking the above example, at time 1, you cross out the cell you tried (cell (1,2)) as well as all other cells that would have resulted in position 3 at time 1. These include cell (2,1), cell (-2, 5), cell (10, -7) etc.

In general, if your guess at time X is Y, you cross out all cells (A,B) such that A+BX=Y.

Every time you make a new guess you just have to make sure that your guess is associated with a cell that you have not crossed out. Since A and B are finite numbers, eventually you will catch the spy.

Now there are a couple of wrinkles. One is, "doesn't the array need to be infinite for this to work?" The answer is not really. You can grow the array as you keep guessing. Eventually you will guess the right number and at that time the array will still be finite, because the A and B you guessed were finite.

The other wrinkle is: "isn't the number of cells you are supposed to cross out each turn infinite?" That can be avoided as well. You can keep a finite array and only cross out the cells in the array. But also store a history of wrong guesses. Whenever you cross out every cell in the array, you grow the array by increasing its bounds. Then you look at your history and cross off any of the new cells in the grown array that are associated with any of your previous wrong guesses.

Hope this helps.

[xenophanes]

As I read the problem, what we need is a mapping of the integers (not reals) to guesses that will cover all (A,B) possibilities.

To solve it, we basically need to specify an ordering of guesses, one after another, covering all possibilities. Or equivalently, we want a function that takes the (integer) time and returns a guess, and will return all needed guesses as time goes to infinity.

Orderings are very important when dealing with infinities. If you just start by guessing things of the form 0,T as time goes to infinity, planning to guess 1,T stuff later, you never finish the first part, so you fail. What's needed is something like a methodical way to cover everything that doesn't do infinite back tracking.

As an example, if we wanted to map all integers to positive integers, the ordering for all integers is very important. If you try "all the positive ones first, then all the negative ones" it doesn't work b/c you never run out of positive ones, never get to the second part of the plan. But what you can do is 0,1,-1,2,-2,3,-3,4,-4 etc. Then you cover everything methodically without planning to backtrack after infinite steps have happened.

The above attempted solution does specify an ordering. It basically just says "keep trying stuff until you get it" which doesn't really address the problem. It might help to imagine you had to write a computer program to make the guesses. What would it guess first? Second?

BTW one neat thing about having an ordering, aka a function of time returning the next guess, is that no storage is needed (besides the current time). Or in other words, if you're guessing in a correct pattern you don't have to keep any lists of previous guesses, all you have to do is know what the pattern is and where you are in the pattern so you can figure out the next thing in the sequence.

It's also not clear that the suggestion of crossing out additional stuff (other than the exact thing you guessed) helps anything. We don't care about efficiency when we have infinite guesses, crossing stuff out is only useful if we have an ordering that misses some guesses but we know they can all be crossed out in this way so it fills in the stuff we know we'd never guess directly. If the solution involves something like that, it's pretty tricky, so one would definitely have to say how it works to solve it.

I'm no expert at this. I tried some and found it's hard to make an ordering that works. Try it yourself and see. I won't be surprised if it's trivial for a mathematician though. And I assume it's possible or they wouldn't ask this question.

If anyone does know the solution I'd be interested in reading it or getting a hint.

[losvedir]

Yes, exactly, and very clearly written! The trick is at the bottom beneath "SPOILER", but unfortunately I can't think of a good hint that gets you partway there.

I learned of the method as part of the proof that the cartesian product of a countable set is still countable. (i.e. that if the integers are countable, then the set of all pairs (Z,Z) is countable, where Z is an integer.) If you're interested, you can look at Cantor's work on the different magnitudes of infinities. For instance, you'll notice that if (Z,Z) is as infinite as Z, then the set of all rational numbers is "as infinite" as the set of all integers, since a rational number is just one integer divided by another. But what about the real numbers? Cantor showed with a cute diagonalization proof that they are "more infinite". Is anything more infinite than the reals? (Yes) Is there some level of infinity between the rationals and the reals? (I forget, but I think this is unanswerable, or rather, can be proved both ways) Those are some of the questions he worked on.

SPOILER The trick is to think of a big square, with 0,-1,1,-2,2,etc going along the top and 0,-1,1,-2,2,etc going down the left side. Then the ordering is done by infinitely zig-zagging your way down from the top left to the bottom right.

[xenophanes]

Thanks! I worked out a different way, too.

SPOILER

For just positive numbers, have the first number count up to the second number. Then increment the second number and reset the first to 0. Then adjusting for negatives is no big deal. Pretty simple in concept. Here's non-simple ruby code for calculating the pair for any step directly:

  def inefficient(n)
    count = 0
    while n > count
      count += 1
      n -= count
    end
    [n, count]
  end
  
  def with_negatives(n)
    # wastes some steps trying to get the negative version of 0. whatever.
    tmp = inefficient(n/4)
    if n%4 == 1
      tmp[0] *= -1
    elsif n%4 == 2
      tmp[1] *= -1
    elsif n%4 == 3
      tmp[0] *= -1
      tmp[1] *= -1
    end
    tmp
  end
  
  50.times {|n| puts "#{n}: " + with_negatives(n).inspect}

[xenophanes]

Worked out the math to get rid of the loop.

  def efficient(x)
    num = (Math.sqrt(2 * x + 0.25) - 0.5).floor
    num2 = (num**2 + num)/2
    [x-num2, num]
  end

Edit: Or:

  def efficient2(x)
    num = (Math.sqrt(2 * x + 0.25) - 0.5)
    num2 = ((num - num.floor) * num).round
    [num2, num.floor]
  end

[anatoly]

Here's the easiest way I can think of to imagine an ordering that works for what you need. Imagine an infinite square lattice: a plane where the As lie on one axis and the Bs on the other, and there's a dot in every integer-coordinates point. Now just do a "spiral", for example counterclockwise: 0,0 -> 1,0 -> 1,1 and keep unwinding your way to infinity. The exact formulas can be written out but intuitively it should be enough to convince you it works even without them.

[kamechan]

nice.