wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> 1000 Wires
        
(Message started by: Barukh on Jun 26^th, 2006, 8:43am)

Title: 1000 Wires
Post by Barukh on Jun 26^th, 2006, 8:43am

Has this problem (http://www.ocf.berkeley.edu/~wwu/riddles/hard.shtml#1000wires) been discussed?

Title: Re: 1000 Wires
Post by BNC on Jun 26^th, 2006, 9:02am

Yes, it was (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1028323982).

Title: Re: 1000 Wires
Post by Barukh on Jun 26^th, 2006, 9:40am

OK. :D

Let's consider the following variation: instead of a battery and a bulb, you've got a simple tester, that will only indicate whether two ends are connected, or not. You can see the test result only if the tester is at the same side of the building.

What happens now?

Title: Re: 1000 Wires
Post by jollytall on Jun 27^th, 2006, 12:34am

Still one up, one down is sufficient. 1000 being even is making it more difficult, but still doable.

But first for an odd number:
[hide]Step 1: Connect the wires in pairs, one left
Move UP
Step 2: Find the pairs. The one without a pair is the last one. Number it. You can Also number all the others, where 1-2, 3-4, etc. are the pairs.
Step 3: Now connect 2-3, 4-5, etc.
Move DOWN
Step: The one without a pair is the last one. Open all connections, but remember them. The one connected to the last one, is n-1. What it used to be connected is n-2, etc.[/hide]

For even numbers it is a bit tricky [hide](the problem is that you have to differentiate the last and the first)[/hide], but still doable:

The modified tactics:
[hide]Step 1: Connect them in pairs, but leave 2 free.
Move UP
Step 2: Find the pairs and number them 1..n-2. You can also number the last two n-1 and n.
Step 3: Connect 2-3, 4-5 and even n-2 with n-1.
Move DOWN
Step 4: Open the connections, but remember them.
Step 5: Find the pairs (connected on the other side). There will be two without pair, the one that had never been connected on this end is n, the other 1.
Step 6: Now the original pair of 1, is 2, the new pair of 2 is 3, etc.[/hide]

Title: Re: 1000 Wires
Post by Grimbal on Jun 27^th, 2006, 1:02am

It doesn't work for n=2 ;D.

But besides that it looks perfectly correct to me.

Title: Re: 1000 Wires
Post by Barukh on Jun 27^th, 2006, 5:06am

Well done, jollytall! :D

Grimbal, your remark is also correct. ;)

Title: Re: 1000 Wires
Post by jollytall on Jun 29^th, 2006, 12:56am

You are right. For n=2 it does not work. But I do not think there is any solution under the given conditions for that.

Title: Re: 1000 Wires
Post by capricafox on Jul 20^th, 2006, 8:43pm

the problem mentions polarity. let's use it.
Take a smaller problem 16 wires.

At bottom, connect 1-2, 3-4, ... 15-16

go UP.

with battery and bulb, find pairs and label them A1, A2, .... A8
connect A1-A2, A3-A4 ... A7-A8 (that's right 4 wires).
Go DOWN.
Find pair of pair, ex: (1-2)-(5-6) label these
B1, B2, B3, B4.

Now this is the 4 fire problem that will repeat over and over:

Leave B1 and B2 dangling, connect B3-B4.
Go UP.
Isolate the dangling Bw, Bx and the equivalent pair By-Bz'. Open it and connect By-Bx'
Go DOWN.
Find the dangling pairs and equivalent pair Bx-By. You have enough to identify all 4 wires.

So in 2 trips you can resolve 4 'cables'.
Now, break those cables in 4 wires and attack 4 times a 4 wire problem concurrently as you go up and down. The next 2 trips should identify 16 wires.

So you would have now 16 puzzles if you could split them (which is true if you had assembled 1000 wires earlier).

So it looks like a log2(N) order.
I leave the exact answer to math guys.

Title: Re: 1000 Wires
Post by BNC on Jul 20^th, 2006, 10:08pm

capricafox, are you refereing to the original problem?
The original problem may be solved with way fewer trips (see the link before). The variant Barukh suggested has no polarity.