There's one in every crowd...

If your patch cord is truly unlimited, you _can_ tell two wires apart. You need 10 miles of patch cord, though.

Franklin T. Adams-Watters

I hadn't planned to get picky, but the buried cable runs through some pretty rough neighborhood: electrical vandals roam the streets at all hours, randomly pulling apart daisy-chained patch cords with reckless cruelty. That's why the cable had to be buried in the first place. --Michael Kleber

-----Original Message----- From: Michael Kleber <michael.kleber@gmail.com>

A week or two ago I heard for the first time the following enjoyable brain teaser:

--------- A company has just buried a 10-mile-long cable containing 120 individual wires. Unfortunately, the project was overseen by a summer intern, and the sad result is that the wires are entirely unlabelled. Your job is to fix this mess: label each wire with the same name on both ends.

The tools you have available are (1) a battery, (2) a lightbulb, and (3) an unlimited amount of patch cord. And (4) your feet, and no other form of transportation. You start at one end of the cable, and can do as much as you want there, but then you need to walk down to the other end and repeat.

In how few trips down the length of the cable can you label the wires? ---------

...

p.s.: An interesting observation is that with n=2 the problem is unsolvable; there is no way to tell the two wires apart.

-- It is very dark and after 2000. If you continue you are likely to be eaten by a bleen.

_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

-- It is very dark and after 2000. If you continue you are likely to be eaten by a bleen.

Sorry, this doesn't work when n is one less than a triangular number. I think a third trip is needed for this case. Franklin T. Adams-Watters -----Original Message----- From: franktaw@netscape.net Start at one end, and connect a group of 15 wires, a group of 14, ..., down to 1 single wire not connected to anything. Go to the other end, and you can determine which group each wire is in by how many other wires it is connected to. Now, take one wire from each group, and connect them in a group of 15. This exhausts the group of 1; take one from each remaining group for a group of 14, ..., with one final wire unconnected. Go back to start, and again identify the groups by size. Now each wire at each end is identified with a unique pair of numbers a,b in the range 1 to 15 (with a+b>=15).    This gives us a solution in 2 trips any time n is triangular. In general, n = k(k+1)/2 + r, with k>1 and 0<=r<=k, we can identify groups of 2 through k, plus a group of r+1 unconnected wires, and get a similar labelling in 2 trips. This leaves the cases n=1, which is already solved, and n=2, which as noted is unsolvable (unless we have 10 miles of patch wire and a team of attack dogs to keep off the electrical vandals).    (Actually, there is another potential solution for 2 wires: connect one of them to ground at one end. We should be able to get a small current though ground for this wire. Whether this will light the bulb sufficiently to be visible is another question.)    Franklin T. Adams-Watters    -----Original Message-----  From: Michael Kleber <michael.kleber@gmail.com>    A week or two ago I heard for the first time the following   enjoyable brain teaser:      ---------   A company has just buried a 10-mile-long cable containing   120 individual wires. Unfortunately, the project was overseen   by a summer intern, and the sad result is that the wires are   entirely unlabelled. Your job is to fix this mess: label each   wire with the same name on both ends.      The tools you have available are (1) a battery, (2) a lightbulb,   and (3) an unlimited amount of patch cord. And (4) your feet,   and no other form of transportation. You start at one end of   the cable, and can do as much as you want there, but then   you need to walk down to the other end and repeat.      In how few trips down the length of the cable can you label   the wires?   ---------      I have a second problem for follow-up, but I can only present   it to people who have solved the first problem (for general n,   of course, not just n=120). So tune in tomorrow for my tale of   the ups and downs in solving this one, and perhaps help me   out of my end state (down).      --Michael Kleber      p.s.: An interesting observation is that with n=2 the problem   is unsolvable; there is no way to tell the two wires apart.      -- It is very dark and after 2000.   If you continue you are likely to be eaten by a bleen.      _______________________________________________   math-fun mailing list   math-fun@mailman.xmission.com   http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun     _______________________________________________  math-fun mailing list  math-fun@mailman.xmission.com  http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun 

Much thanks to Franklin, who has been good enough to come up with *both* of the solutions to the cable problem. Now I can get on with my extended discussion. The executive summary of this longwinded message: The triangle number solution is really cool, but sadly, the much simpler daisy-chaining solution is better. I would dearly love to see a modification of the puzzle, for which the triangle number solution is the only one. Please please please. Okay, now for the details. When we first heard the problem, both (funster-lurker) Thomas Colthurst and then I independently arrived at the triangle-number solution, as did some colleagues at the Broad when I started to spread the problem around. The quick summary of that solution: say the number of wires is triangular, eg n=10: draw the triangle * * * * * * * * * * First patch together all wires in the same row; from the other end of the cable, you can tell the size of the equivalence class each wire is in. Now patch together all wires in the same column, and trek back to the beginning. The sizes of a wire's two equivalence classes act as unique coordinates. This can be generalized beyond triangle numbers, too. In the 10-wire version above, the coordinates given to the wires end up being 44; 43,34; 42,33,24; 41,32,23,14. All of these pairs sum to one of 8,7,6,5. So if we had, say, three more wires: * * * then we could simultaneously apply this technique to them, getting coordinates 22;12,21; there's no problem confusing the two triangles with each other. In general, then, we can use this method for n wires any time n can be written as a sum of triangular numbers such that if we use T(r) in the sum, we can't use any T(s) for r<s<=2r. Chewing on this last week, I was delighted to prove that this condition holds for all but finitely many n: there are only 39 numbers which cannot be so written; the largest is 720. (Yes, NJAS, I'll get the list to you eventually, but let this discussion play out first please!) So I was feeling pleased with my clever technique and my proof, and all was well until I shared the problem with Broad colleague Jade Vinson (another mathematician, of holyhedron fame). Jade promptly came up with a daisy-chaining method, as Franklin has already described; one construction works for all odd n, and a tiny variation works for all even n>2. This leaves the beautiful triangle number solution looking too clever by half: it's both harder and less universal. Thus my appeal to math-fun: please find a puzzle, of similarly elegant statement, to which the triangle solution is the only one. There certainly should be hope, because the daisy-chaining method queries the state of the system in a fundamentally different way from the triangle technique: for triangles, you need only figure out *how many* other wires each one is associated with, while you can only daisy-chain if you can learn the *identity* of an associated wire. Can anyone rescue "All but 39 values of n" from the dustbin of too-clever puzzle solution history? --Michael Kleber On 7/17/06, franktaw@netscape.net <franktaw@netscape.net> wrote:

Here's an entirely different approach, which works for all n > 2.

The case where n is odd is simpler. Link all the wires in pairs, with 1 left over. At the other end, identify all the pairs. Now link the singleton to one of pair, link the other member of that pair to one of a different pair, etc., until the last pair will have one wire unlinked. Now identify these pairs at the other end. The originally isolated wire is already identified; the wire it is now linked to can be identified, which identifies the other member of that pair, etc.

For n even, link all but 2 wires in pairs. At the other end, link one of the previously unconnected wires to one of a pair, and chain through the remaining pairs as before. The other previously unconnected wire remains unconnected. First identify the wire which was never connected; the remaining wires then reduce to the previous case.

Note that this solves the problem never connecting more than 2 wires together, so we could solve the problem with switchboards instead of the patch cord.

Franklin T. Adams-Watters

-- It is very dark and after 2000. If you continue you are likely to be eaten by a bleen.

I don't see that this variation _allows_ the triangular numbers approach. I think all you can do is connect some subset of the cables to the shield, then see which ones they are. This will require ceiling(log_2(n)) walks. This does suggest a variant (which I don't know the answer to) - suppose there are n wires with a diode towards one end of the cable, and m oriented the other way (m, n both > 0). There are two variants here: in one, we can tell which wires have the diodes oriented in which direction; in the other, we can't. Now how many trips are required? I suspect that when n+m>3, more than 2 trips will be required. Franklin T. Adams-Watters -----Original Message----- From: Michael D Beeler <mbeeler@csc.com> ... Proposal: Would this variation require the triangular numbers approach, and not the pairs-and-pairs approach?: The n wires each have a diode in them. All diodes point in the same direction, say cathode toward end A of the cable and anode toward end B. This precludes current through loops of paired wires. To make the problem solvable, suppose there is a conductive shield on the cable, which acts as one additional wire with no diode. ...

I haven't followed this closely enough to know if it's been completely worked over, yet. I'm including an Email from my son, who is fairly good at problems like this. My apologies if this is now old material. --BC ---------------------------------------------------- Hi, Dad, Actually, this is very similar to a question at STS. For n > 2, it's possible to do it in two trips. The basic idea is that you can connect the cables into groups of different sizes with the patch cord on one end and, when you get to the other end, you use the battery and wire to check each pair of cables and see if it lights up. For example, with 11 cables, you might start on side A and patch 4 together, 3 together, pair 2 up, and leave 2 unconnected. When you get to side B, you use your battery & bulb, choose any cable, and try to form a circut with all of the other cables in turn and look at how many cause the bulb to light up. If 2 do, then you can say "oh, it looks like this cable must be connected to 2 others on the other end, therefore it's part of the group of 3" Then you patch the cables together on side B in the same manner and run back to side A and use you battery & bulb. Here, when you patch together your new groups, you want the cables that were in the same group on side A to be in distinguishable groups on side B. i.e. for the 4 cables which were connected on side A, and are therefore indistinguishable on side B, you want to put one in a new group of 4, one in a new group of 3, one in a new group of 2, and leave one unconnected. You want the cables to be in groups of different sizes, so that they can be easily distinguished from each other. The 'unconnected' cables also form a group--but, because they are unconnected, may be any size and still be distinguishable. For all values except for T-1 and T-2, where T is a triangular number, you can form your groups such that they are all easily distinguishable. For those two cases, however, you have to fudge things slightly--but it can still be done. For example, suppose that you are solving the nasty case of 14 cables. You may want to connect 4 cables into group A, 3 cables into group B, 3 cables into group C, 2 into group D, and leave two unconnected (E). Now, on the other side, using the battery and lightbulb, you can determine which cables are in A, which are in B or C, which are in D, and which are in E. Connect the cables into groups as follows: 1: A, B(C), C(B), D, E 2: A, B(C), D, E 3: A, B(C), C(B) 4: A, C(B) (unconnected) Now, when you get back, one of the cables from either B or C is going to be unconnected. This by itself is enough to tell you which group is B and which group is C. Hope that this makes sense.