Imagine you are an electrician with the following problem. Someone has installed a cable from the basement to the top floor of a 15 floor building. The cable contains ten separate wires. There was a splice at some unknown place, and two such cables were joined together. Unfortunately, whoever did this was new to the job, and they ignore the color coding! So now you don't know which strands in the basement correspond to which strands in the top floor.
The only thing you have to fix this mess is a circuit continuity tester. This is just a thing with two probes that lights up if you touch the wires to each other -- or if you touch them to any wires that have been connected to each other. This is a small thing, so you can't connect it from the basement all the way to the top floor! However, it is big enough to check any two wires in the cable at one end.
Also (so there is a puzzle to solve!), you can't have help from anyone else. For example, this would be easy if you had a friend on the top floor with a cell phone, as you could join various wires and have them test to find out which ones were joined, using the circuit tester. So, it's just you. Oh yes, did I mention that the elevator's aren't working? They are out of commission until you correctly hook up the cable... So each time you want to get to the other end of the cable you have to climb up a lot of stairs.
And no, you can't just pull the cable out and find the join -- and you can't forget it and run a new cable in its place. This would be expensive, but more seriously it would take all the fun out of it.
So, here is the question: What is the smallest number of times you have to hit the stairs before you can get all ten strands correctly identified, both in the basement any at the top floor? And how do you actually do it?
You can assume you can join and unjoin two or more wires, and also that you can stick paper labels on the wires. The labels can be whatever you like as long as they are all different in the basement, and the same set is used on the top floor. Whenever you make some pattern of connections at one end, you may assume that you can use the circuit detector at the other end to discover the same pattern at that end. The trick is to use that as a clue to the identity of the wires.
When you solve that, could you also solve the same question for a cable containing nine separate wires? How about other numbers? Can it always be done?
For those who like to think abstractly, you can translate this into a question which asks for the minimum number of partitions on an n-set which will characterize each element. For those who don't like to think this way, please don't read the previous sentence.
We will discuss this at the next meeting, where there will be an opportunity to share partial or complete solutions.
Send comments to Math Club Puzzlemaster