Ken's Puzzle of the Week
Wires and Rooms
- The original problem of wires and rooms is this: You are in one room and
have nine identical wires going into the wall. In another room, the
other ends of these same wires are accessible. You may twist together
the ends of any wires in one room, and you have a tester that will identify
any closed loop. How can you correctly label both ends of all wires in
the smallest number of trips between rooms? How would you do this with
eight wires?
- Now there are three rooms, with eight wires in each room (24 wire ends means
12 wires in the walls.) The wires in one room could go to either of the
other two rooms. How can you correctly label both ends of all wires with
the smallest number of trips among rooms? How would you do this with one
additional wire (nine ends in two rooms and eight ends in one)?
- Four rooms with eight wires in each room? Nine wires in each room?
Source: Extended from rec.puzzles's
Wire Labels, most recently seen as Problem #268 at
Dan's Math (#1a
copied from there.)
Solutions were received from Mark Rickert, Denis Borris, Joseph DeVincentis,
K Sengupta.The 2-room problem requires 2 trips. The 3-room problem
takes 6 trips, and the 4-room problem takes 13 trips.
For problem 1, the rec.puzzles
solution is quite adequate. I summarize here: In room A, perform Job 1: twist the wires into
pairs (A-B, C-D, Ux, [Uy]...), leaving one (or two) wires unconnected. Move to
room B and perform Job 2: detect all connected pairs and one (or two)
unconnected wires (1-2, 3-4, U1, [U2]) Then reconnect them in new
pairs: U1-1, 2-3, 4-5, ... . Return to room A and perform Job 3:
detect which previously unconnected wires are now connected, and match the
pairs in sequence. For example, previously unconnected Ux is the now
connected U1 [or the still unconnected U2]; the wire (say B) connected to Ux
is wire "1", and "A" is thus wire "2"'; the wire now connected to "A" (say
E) is wire "3", etc.
In problem 2 (three rooms), since all wires go from one room to another,
there must be 4 wires running between each pair of rooms.
In problem 3 (four rooms), Denis pointed out that if a single or pair of
wires runs between 2 rooms, we cannot uniquely identify them. In the
case of a single wire, there is likely another single wire in the network,
and the two cannot be uniquely determined. In the case of a pair of
wires, they can only be identified as a pair, but not down to a single wire.
So Denis appropriately decided to only analyze the case with 9 wires in each
room, three each going to each of the other rooms.
Denis' solutions follow.
Problem 2 (three rooms):
R1 = room1, R2 = room2, R3 = room3.
And the three "2-room jobs" are : J1, J2 and J3.
Connect ALL 8 wires together in R1
Trip1(R1 to R2)
identify the 4 wires that go to R1: label 'em "12"
since the other 4 go to R3, label 'em "23"
Trip2 (R2 to R3)
identify the 4 wires that go to R1: label 'em "13"
since the other 4 go to R2, label 'em "23"
do J1 on the "23"'s
connect ALL "13"'s
Trip3(R3 to R1)
disconnect the wires in R1
identify the 4 that are the ends of the "13"'s; label 'em same
the other 4 will be ends of "12"'s; label 'em same
do J1 on the "12"'s and on the "13"'s
Trip4(R1 to R2)
do J2 on the "23"'s
do J2 on the "12"'s
Trip5(R2 to R3)
do J3 on the "23"'s : FINISHED
do J2 on the "13"'s
Trip6(R3 to R1)
do J3 on the "12"'s : FINISHED
do J3 on the "13"'s : FINISHED
Problem 3 (four rooms):
My solution has 13 trips.
Setup: 9 wire ends in each room, so total of 18 wires; a bit like (A =
room A, ...):
A w1 w2 w3 w4 w5 w6 w7 w8 w9 | B w1 w2 w3 w10 w11 w12 w13 w14
w15
===========================================================
D w16 w17 w18 w13 w14 w15 w7 w8 w9 | C w4 w5 w6 w10 w11 w12 w16 w17 w18
Again, J1, J2 and J3 used as the 3 Jobs to complete a 2-room process.
AB means wires to/fro rooms A and B.
"Label" means label the wires after they're located using the loop
tester.
Start in A: connect ALL wires together.
Trip#1: to B
Label the ABs
Do J1 on the ABs
Trip#2: to C
Label the ACs
Connect the ACs
Trip#3: to D
Label the ADs
Connect the ADs
Trip#4: to A
Disconnect the wires
Label the ACs and ADs
Label the ABs (default)
Do J2 on ABs
Do J1 on ACs and ADs
Trip#5: to B
Do J3 on ABs : FINISHED
Connect ALL other 6 wires together
Trip#6: to C
Label the BCs
Label the CDs (default)
Connect the BCs
Trip#7 : back to B
Disconnect the 6 wires
Label the BCs
Label the BDs (default)
Do J1 on BCs and BDs
Trip#8 : to C
Do J2 on ACs and BCs
Connect the CDs
Trip#9 : to D
Label the CDs
Label the BDs (default)
Do J1 on CDs
Do J2 on ADs and BDs
Trip#10 : to A
Do J3 on ACs : FINISHED
Do J3 on ADs : FINISHED
Trip#11 : to B
Do J3 on BCs : FINISHED
Do J3 on BDs : FINISHED
Trip#12 : to C
Do J2 on CDs
Trip#13 : to D
Do J3 on CDs : FINISHED
Probably possible to do in 12 trips, but I'm too "wired" to try !
Mail to Ken