8
$\begingroup$

Alice and Bob are telecommunicating in some way. When Alice speaks, it takes A seconds to reach Bob. When Bob speaks, it takes B seconds to reach Alice. Both Alice and Bob have clocks that tick at the same speed, but no guarantee that the clocks are set to the same time.

How can they determine A and B?

The algebraic solution to this puzzle is not very difficult, although I'd be interested to know if there are alternative approaches.

$\endgroup$
  • $\begingroup$ Are they allowed to use any common outside time reference? If so, things are trivial. If not, and if A and B are independent, then I don't see a solution. If both parties were on a token-ring network which took one second to make a full orbit, the situation where A and B were both 0.5 seconds and the clocks were in sync would be indistinguishable from the one where A was 100ms and B was 900bs, but Alice's clock was 400ms behind Bob's. $\endgroup$ – supercat Nov 15 '14 at 17:06
  • 1
    $\begingroup$ @supercat I'm afraid I'm going to have to state a warning that I'm no longer sure this puzzle has a solution. It's been a while since I last worked out the details - I thought I'd verified it with an example, and on top of that I remember somebody else coming up with a solution that seemed correct to me, so I was sure it had one. Until/unless I remember my solution, though, I can't be sure anymore. Sorry, I should have double checked right before posting instead of relying on my memory. $\endgroup$ – Jack M Nov 15 '14 at 18:01
  • $\begingroup$ Whether it has a solution will depend upon exactly what the parties are allowed to do; you may want to figure out a set of constraints that will make the puzzle solvable but interesting, rather than requiring people to guess. $\endgroup$ – supercat Nov 15 '14 at 18:04
  • $\begingroup$ @supercat I'd be interested in lateral-thinking methods, but like you said, if an outside reference is allowed, it becomes trivial, so that's not much fun. The solution I thought I had involved only the clocks - imagine Alice and Bob are in locked cells with no windows or communication with anyone but eachother. If you could flesh out your argument that that puzzle is impossible I think it would be a great answer, it would certainly put my mind to rest. $\endgroup$ – Jack M Nov 15 '14 at 18:14
  • $\begingroup$ Suppose that there are three people at distinct points on a sphere, and for each of the three pairings there is a great circle which connects them. Communications between each pair of people will go the same direction around the circle (so if it would take R seconds for a message to go around the circle and it would take A seconds for Alex to send a message to Betty, it would take R-A seconds for Betty to send a reply). Experiment and see if you can establish a communications protocol subject to those constraints; I think it should be possible, and might make a better puzzle. $\endgroup$ – supercat Nov 15 '14 at 20:06
5
$\begingroup$

Unfortunately there is no way for Alice or Bob to determine the individuals times A and B, without outside communication or knowledge. The best they can do is determine the value of A+B.

To illustrate why, let us first consider one approach one might take. One could allow Alice to send her time to Bob, and Bob to immediately send his time to Alice, and back and forth. In the following table I have assumed the clocks are out of synch by 8 units, and A = 2 and B = 5.

Table of Scenario 1:

enter image description here

A "Y(x)" in the diagram represents a signal was received, where "x" is the value of the signal received. The initial "Y" at time 0 is when Alice sends her first signal.

Now from the above table, Alice can easily deduce A+B = 7, and Bob can do the same. Now clearly there is no point in this process continuing further, because Bob can already now deduce what his next received signals will be and the times he will receive them. E.g. Y(14) at 24 seconds, then Y(21) at 31 seconds etc., and Alice can deduce what her received signals will and the times she will receive them. E.g. Y(17) at 14 seconds, then Y(24) and 21 seconds etc. So no more information can be exchanged between the pair.

Now consider the same scenario but where the clocks are out of synch by 7 units, and A = 3 and B = 4.

The following table shows the signals received and the times they are received.

Table of Scenario 2:

enter image description here

The important thing to notice here is that despite a difference in time synchronization and a difference in the values for A and B, the signals are all sent and received at identical times to previous example, with identical values. That is, if Alice and Bob receive signals in such a pattern, there is no way they can determine if they are in Scenario 1 or Scenario 2 or many other scenarios for that matter.

So while this isn't the only strategy Alice and Bob could attempt, it is clear that this strategy shares maximal knowledge between Alice and Bob - that is, Alice knows everything Bob knows and Bob knows everything Alice knows. Therefore no other strategy will be able to transfer additional information to derive the values of A and B individually.

$\endgroup$
2
$\begingroup$

@Mew already pointed out that you cannot solve this puzzle exactly as stated.

But for all practical purposes, we can assume that A~=B, and since we can determine A+B, we can approximate A and B as A~=B~=(A+B)/2.

Furthermore, it's only shown that you cannot solve the problem in-band. What if they could synchronize their clocks? Then it's trivial: At midnight, Alice announces "it's Midnight", and Bob can announce A. Vice versa for B.

So how could they sync their clocks? Unfortunately, because of the proof already shown, they cannot do this in-band. The best they can do is sync to an error of |A-B|. They need eighter some kind of signalling with known time to travel, or some kind of worldwide synchronous event as reference. They could shoot a laser at the mirrors on the moon, or something. When they decide that Alice's clock is the reference clock (e.g. the one that shows the "correct time" for the system), then Alice fires her laser when their clock shows midnight. When Bob observes Alice's signal, he sets his clock to Midnight+time_the_laser_signal_travelled. Now, their clocks are synchronized and they can trivially determine A and B.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.