I recently came across this puzzle. The premise is there are N wires with ends at the top and bottom of an elevator shaft, but you don't know which ends are connected. You are able to tie (and untie) ends of wires together and test them with a bulb to see if they are connected, and you must figure out the minimum number of trips you must take to figure out which end connects to which end.
I understand the solution of 1 round trip if N is triangular; however, supposedly the solution can be generalized for any natural number.
I did some playing around on my own, starting with the simplest non-trivial case, N=2, but I don't see how it is possible. Let's say at the bottom of the shaft, the wires are labeled 1,2 and at the top they are labeled A,B. If you tie 1/2 together, both A,B light up at the top and you have gained no information. If you don't tie 1/2 together, Then A and B will light up separately and you also have gained no information. Similar logic applies for when you manipulate the wires from the top and walk back down to the bottom.
For the case N=4 (skipping 3 because it is triangular), I worked through the cases similarly and found that no matter how you manipulated the groupings, you would also have at least 2 wires you could not figure out. I came to the conclusion that for the solution to be possible for N wires, N must have the following properties:
- $N$ must be divisible into $k < N$ sets such that each set $k$ has at least $1$ element and is not the same size of any other set $k$.
- Let $k_i$ denote the set with $i$ elements in it. $N$ must also be divisible into $m < N$ sets such that each set $m_i$ has at least $1$ element, is not the same size as any of the other $m$ sets, and if $x \in k_i$ and $x \in m_j$, then $m_j \cap k_i = x$.
These properties do not hold for both N=2, N=4. If my logic fails, can anyone explain why I am wrong, and give an example of how to solve the N=2 case?