Arthur and Bert each writes down a positive integer on a piece of paper and then shows it to Charles. Charles then writes two numbers on a blackboard, visible to Arthur and Bert: one of them is the sum of Arthur's and Bert's numbers, and the other is a random number.

After this Charles asks Arthur if he knows Bert's number. If Arthur says he doesn't know, then he asks Bert if he knows Arthur's number. If Bert says he doesn't know, Charles continues with Arthur, then if necessary with Bert and so on... until he gets a positive answer.

When will Charles get a positive answer?

Let's first consider a simple case.  The two numbers written on the board are x and y, and let's say x = y+1.

The following is a chart of possibilities.  I find that such a chart is a useful tool in solving this type of information puzzle.  If it's not clear, each row represents a possibility.  The first two columns are numbers A and B (Arthur and Bert's numbers).  Each column afterwards represents the response of Arthur or Bert (x means "I don't know" and o means "I know").

1   x-1  xo
1   x-2  xxo
2   x-2  xxxo
2   x-3  xxxxo
3   x-3  xxxxxo
3   x-4  xxxxxxo
...
x-3 3    xxxxo
x-3 2    xxxo
x-2 2    xxo
x-2 1    xo
x-1 1    o

We can see a general trend here, but before I describe it mathematically, I will consider a more complicated case.  Namely, x = y+2

1   x-1  xo
1   x-3  xxo
2   x-2  xo
2   x-4  xxo
3   x-3  xxxo
3   x-5  xxxxo
4   x-4  xxxo
4   x-6  xxxxo
...
x-6 6    xxxxo
x-6 4    xxxo
x-5 5    xxxxo
x-5 3    xxxo
x-4 4    xxo
x-4 2    xo
x-3 3    xxo
x-3 1    xo
x-2 2    o
x-1 1    o

Now, x = y+3

1   x-1  xo
1   x-4  xxo
2   x-2  xo
2   x-5  xxo
3   x-3  xo
3   x-6  xxo
4   x-4  xxxo
4   x-7  xxxxo
5   x-5  xxxo
5   x-8  xxxxo
6   x-6  xxxo
6   x-9  xxxxo
...
x-6 6    xxo
x-6 3    xo
x-5 5    xxo
x-5 2    xo
x-4 4    xxo
x-4 1    xo
x-3 3    o
x-2 2    o
x-1 1    o

The general pattern has become very clear by now.  Let N be the number of rounds it takes for Charles to get a positive response.  Here is the general pattern of N, in mathematical form. Assume x>y

If A+B=x
N =
   MIN(
   2 * ceil( A / (x-y) ),
   2 * ceil( B / (x-y) ) - 1
   )

If A+B=y
N =
   MIN(
   2 * ceil( A / (x-y) ) + 1,
   2 * ceil( B / (x-y) )
   )

Not the cleanest function, but it works.

Posted by Tristan on 2005-10-31 19:53:21