Puzzle
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.
posted by metamerist at
3:04 PM
1 Comments:
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.
Post a Comment
Subscribe to Post Comments [Atom]
<< Home