Sunday, August 12, 2007


I was introduced to interesting puzzle this past week. I think I've faithfully rendered it below, but if I haven't, it still captures the spirit of the problem.

Given the graph above, A and B each represent 1 gigabyte of data to be sent through the network represented by the graph. Each arrow indicates a possible data transfer at a maximum rate of 1 GB/s, with the restriction that nodes cannot send and receive at the same time. In terms of time, calculations are free.
The question: How can you transfer A to A' and B to B' in 3 seconds?
I'll post the answer in the comments later.


Blogger metamerist said...

The answer involves sending the exclusive or of A and B down the center.

If you've never had to twiddle with bits or play with boolean logic and you figured this out, you probably qualify for genius points.

A = B xor (A xor B)
B = A xor (A xor B)

After receiving A and B, the top middle node sends A xor B down, which is ultimately sent to the bottommost nodes.

If you send A down the left side, you'll have the information you'll need to reconstruct B using exclusive or. Likewise for A on the right side.

6:44 PM  

Post a Comment

Subscribe to Post Comments [Atom]

<< Home