A transatlantic cable contains N = 20 indistinguishable electrical wires. You have the job of figuring out which wire is which, that is, to create a consistent labelling of the wires at each end. Your only tools are the ability to connect wires to each other in groups of two or more, and to test for connectedness with a continuity tester. What is the smallest number of transatlantic trips you need to make, and how do you do it?
How would you solve the problem for larger N such as N = 1000? As an illustration, if N were 3 then the task can be solved in two steps by labelling one wire at one end a, connecting the other two together, crossing the Atlantic, measuring which two wires are connected, labelling them b and c and the unconnected one a, then connecting b to a and returning across the Atlantic, whereupon on disconnecting b from c, the identities of b and c can be deduced.
This problem can be solved by persistent search, but the reason it is posed in this chapter is that it can also be solved by a greedy approach based on maximizing the acquired information. Let the unknown permutation of wires be x. Having chosen a set of connections of wires C at one end, you can then make measurements at the other end, and these measurements y convey information about x. How much? And for what set of connections is the information that y conveys about x maximized?