For a more practical solution On one end link all the wires in pairs labeling them P1, P2, etc. (If there are an odd number of wires label the leftover uniquely) On the other end identify the pairs, them label the wires in the pairs P1a P1b, P2a P2b, etc. (and identify the odd guy if it exists.) Tie all the 'a' wires together, keeping the 'b' wires separate. March back over to the other side and separate and label a's and b's -----Original Message----- From: math-fun-bounces+mdtorge=sandia.gov@mailman.xmission.com [mailto:math-fun-bounces+mdtorge=sandia.gov@mailman.xmission.com] On Behalf Of Michael Kleber Sent: Monday, July 17, 2006 8:14 PM To: math-fun Subject: Re: Re: [math-fun] Buried Cable problem 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. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun