Not exactly wireless
- Do you see this cable?
- That’s a very long cable if ever there was one!
- The cable has one thousand wires in it. I would like to know which wire at this end corresponds to which wire at the other end.
- Seems like a reasonable request.
- I have a battery and a light bulb to help me.
- No wonder I could not find them this morning!
- The bulb will lit up if I make a closed circuit with the wires.
- Can you connect the wires at each end?
- Yes, as much as I please.
- Let’s get to work then.
- Not so fast. I want to minimise the number of times I have to go from one end of the cable to the other.
- Can you see if the bulb is lit from the other end of the cable?
- Sure can.
- Are the wires coloured?
- Unfortunately no.
- I think I know the solution if there are two wires!
- There are one thousand wires.
- Just making conversation.
Problem source: wu:riddles.
June 18th, 2009 at 2:00 am
Partial solution: Here’s how to do 15. The method will generalise to any triangular number of wires.
Strip some insulation of the ends of the wires, and connect the wires into groups of different sizes like so:
a-b-d-g-k
c-e-h-l
f-i-m
j-n
o
Go to the other end of the cable, and identify the groups. Then strip some insulation of the ends of the wires, and connect the wires into groups of different sizes like so:
a-c-f-j-o
b-e-i-n
d-h-m
g-l
k
(This is just the transpose of the 1st diagram.) Label the individual wires accordingly. For example, the wire which is now on its own is labelled k; among the 5 wires grouped together, the one that used to be alone is labelled o and the one that used to be in a group of 5 is a.
Return to the first end of the cable. Mark how the wires are connected (rat belts, temporary labels, or something), undo all the connections, then use your battery and light to identify how the wires were grouped at the far end. For example, the wire on its own is o; among the 5 wires grouped together, the only wire in the group of 5 that doesn’t connect to any other is k, the one that connects to only one other wire is g, and that other wire that g connects to is l, and so on.
So you could do 1035 wires this way with groups of size 1,…,45 and you could make some progress with 1000 wires by just omitting the group of 35, but what do you do at the far end?
How do you handle 7 or 8 wires for instance?
I don’t see how you can do it if there are 2.
June 19th, 2009 at 2:12 pm
Second thought: My earlier method (call it the triangular method) handles N wires if and only if N is a triangular number. I can see how you can do N wires if N is the sum of distinct triangular numbers. This would handle N = 1000 = 990 + 10 = (1 + … + 44) + (1 + 2 + 3 + 4), and also one of the cases I mentioned earlier, N = 7 = 6 + 1 = (1 + 2 + 3) + 1.
Here’s how to do 1000. At the near end, group 990 of the wires into groups of sizes 1, …, 44, and also the other 10 into groups of sizes 1, 2, 3, 4.
At the far end, identify the groups by size as before. Apply the triangular method separately to:
megagroup 1 (990 wires): 1 group each of sizes 1, … 44
megagroup 2 (10 wires): one loose wire, one pair, one triple and one group of 4
There is no way to distinguish between groups of the same size. It doesn’t matter which of the 2 loose wires you put into megagroup 1 and which into megagroup 2.
Back at the near end, set about identifying the wires in the larger groups first. These connect only within megagroup 1. Thus you will identify, among others, the groups of sizes 1, 2, 3, 4 within megagroup 1. After you’ve completed that task, you have only megagroup 2 to deal with, which you handle by the triangular method.
If that was too abstract for you, here’s how I propose to handle 4 wires. Note that 4 = 3 + 1 = (1 + 2) + 1.
Connect 2 of the wires, thus making a pair and 2 loose wires.
At the far end, identify the 2 wires that are connected. Label them A and B; label the loose wires C and D. Regard the 4 wires as being grouped and megagrouped as follows:
megagroup 1 (3 wires):
A-B
C
megagroup 2 (1 wire)
D
Thus, applying the triangular method to megagroup 1, connect A with C, leaving B and D loose.
Back at the near end, mark which are the 2 wires X, Y you connected. Disconnect them. Start by identifying X and Y: one of them connects to another wire; the former is A and the latter is C. Whichever of X and Y isn’t A is B. You have now applied the triangular method to megagroup 1. The remaining wire is D.
This method does not, however, handle N if N is not the sum of distinct triangular numbers, i.e. N=2, 5, 8, 12, 23 or 33. (OEIS: A053614). All N above 2 can be handled, however; just not by this method. For example, 5 can be handled by grouping into 2 pairs and a loose wire, first as
(A B)(C D) E
then as
A (B C)(D E)
This method generalises in an obvious way to any odd number of wires. Handle N = 8, 12 or indeed any even number above 2 by leaving one wire loose and applying this method to the other N-1.
There is no way to identify the wires when there are only two of them.