Author |
Topic: NEW PROBLEM: 1000 Wires (Read 6563 times) |
|
Eric Yeh
Senior Riddler
Gender: 
Posts: 318
|
 |
NEW PROBLEM: 1000 Wires
« on: Aug 2nd, 2002, 2:33pm » |
 Quote  Modify
|
OK everyone, since I see that a lot of the regulars out there have apparently solved most of the riddles here already, I'm going to slowly post some of my own favorites in new threads, to keep things interesting!
(I was also motivated by seeing Frost do so with "Impatient Patients", which was a good problem! So a thank you to Frost.)
This one is one of my all time-faves:
A thousand wires hang on a very high tower, so high that you cannot see what tip belongs with what bottom. This is something you are interested in knowing. You have a battery and a light bulb which will light up if two wires connect it to the battery with appropriate polarity (i.e. the battery and bulb each have two contact points, and one of each is + and the other side is -). Wires may be tied together to form longer wires, and you can see the bulb light up even if you are on the opposite side of the tower. Since the tower is so high, you want to minimize the number of times you have to climb up and/or down the staircase, regardless of how much you have to do while you are at the top or bottom. What is the minimum number of traversals required?
Happy Puzzling,
Eric
|
| « Last Edit: Aug 2nd, 2002, 3:42pm by Eric Yeh » |
 IP Logged |
"It is better to have puzzled and failed than never to have puzzled at all."
|
|
|
Jonathan the Red
Guest
|
 |
Re: NEW PROBLEM: 1000 Wires
« Reply #1 on: Aug 2nd, 2002, 3:40pm » |
Quote Modify
 Remove
|
This is one of my all-time faves as well  I'm not going to spoil it for those who haven't seen it.
|
|
IP Logged |
|
|
|
oliver
Newbie
Posts: 25
|
|
Re: NEW PROBLEM: 1000 Wires
« Reply #2 on: Aug 3rd, 2002, 12:24pm » |
Quote Modify
|
I think I got the solution, it came in my head while cooking for my girlfriend. Am I sick or what? 
Spoiler Space
You need two traversals (one up, one down)
1. At the bottom, connect the wires to pairs, which gets you 500 connected pairs. Go to the top.
2. At the top,
a) First we try to find corresponding pairs to the pairs we made at the bottom. For that, take two wires. Connect them to the light bulb. Nowm one after the other, take all possible pairs of the remaining wires and connect them to the poles of the battery (don't forget to check both polarities). If you get the light bulb to light up, try another combination of wires to the light bulb.
We repeat that until we found two wires so that light bulb, when connected to them, can't be made to light up with the above method. Now we have found a pair at the top which is also connected at the bottom of the building.
This we repeat until we found all correspondending pairs (i.e. 499 times, the last pair we get for free).
Now we give numbers to the cables, 1a, 1b, 2a, 2b, ..., where Na, Nb describe the one of the two wires in a connected pair, respectivly.
b) Now, starting at pair one, we disconnect 1a and 1b, 2a and 2b, and connect 1b to 2a. Then 2b gets connected to 3a, and so on, untill pair 500.
c) We now have loose ends at 1a and 500b, and connect them to the light bulb, - pole to 1a, + to 500b.
Now we go to the bottom.
Short explanation: We now have constructed a closed circuit going through all wires. It really helps here to paint a picture, unfortunately I am to lazy to do that  .
3. At the bottom, we now have to find 1a, which is connected to the - pole of the bulb at the top.
1a has the special property that it is the only wire which we can't bypass in order to get the bulb to light up. That is, if we disconnect 1a and 1b at the bottom, we won't be able to get electric current to the - pole of the bulb, without putting the battery to this wire. In contrast, let's say we disconnected the 5th pair (wires 5a, 5b), we would be able to get the bulb to light up if we disconnected pair 4 and 6 and connect 4a to the - and 6b to the + pole of the battery.
With the above, we could perhaps try to find a more clever algorith to follow at this state, but I'll continue "brute force" - the complexity is down the drain anyway.
Ok then, we disconnect a pair (let's call it X), disconnect two other pairs and connect the battery in all possible combinations to one wire from one and the other wire from the other pair, respectivly. We repeat this with all possible 8 combinations. If we don't get the bulb to light up, we have found either 1a or 500b. A polarity check tells us then when we found 1a.
After we have 1a (and therefore 1b), we repeat the above with the modification that we don't test against the wires we identified before. So we get 2a (and 2b) etc.
Hope this is understandable and right? If not, I blame that on the fact that english isn't my mother tongue .
|
|
IP Logged |
|
|
|
Eric Yeh
Senior Riddler
Gender:
Posts: 318
|
|
Re: NEW PROBLEM: 1000 Wires
« Reply #3 on: Aug 3rd, 2002, 9:21pm » |
Quote Modify
|
You definitely have the right idea -- I haven't looked through all the details, but sounds roughly right. Nice job!
Best,
Eric
|
|
IP Logged |
"It is better to have puzzled and failed than never to have puzzled at all."
|
|
|
mallen
Guest
|
|
Re: NEW PROBLEM: 1000 Wires
« Reply #4 on: Aug 29th, 2002, 7:31pm » |
Quote Modify
Remove
|
on Aug 3rd, 2002, 12:24pm, oliver wrote:
Hope this is understandable and right? If not, I blame that on the fact that english isn't my mother tongue .
|
|
Almost correct, but when you get back downstairs, you cannot tell which end is which. So, you might wind up with the labels reversed (ie pair 500 at the top labelled as 1 at the bottom).
With an even number (like 1000), you leave two wires unpaired at the bottom. Then, when you go to the top and chain up all the pairs, you connect one unpaired wire at the head of the chain (#1) and don't touch the other (#1000).
Then, when you go back downstairs, you can figure out which of the unpaired wires is the head (#1) and trace out 2-999 from there. The other unpaired wire is #1000.
With an odd number (like 999), you do the same thing, except that you don't have the second unpaired (#1000) wire.
- Mike
|
|
IP Logged |
|
|
|
Eric Yeh
Senior Riddler
Gender:
Posts: 318
|
|
Re: NEW PROBLEM: 1000 Wires
« Reply #5 on: Aug 29th, 2002, 8:14pm » |
Quote Modify
|
Agreed -- I still haven't had time to look closely at Ollie's answer, but there certainly is a parity check involved.
Best,
Eric
|
|
IP Logged |
"It is better to have puzzled and failed than never to have puzzled at all."
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: NEW PROBLEM: 1000 Wires
« Reply #6 on: Sep 4th, 2002, 11:08am » |
Quote Modify
|
I agree that with Oliver's solution, but you can't tell which end of the long wire is which. Maybe the following would help:
Instead of leaving 1a and 500b loose, connect 1a to the - terminal and 500b to the + terminal of the light.
Now you can figure out everything when you get to the bottom--read on:
1) Disconnect a pair of wires (pair x). Now test the battery on the pair and see which way lights up the LED. The positive terminal of the battery is attached to the 'xb' wire when the LED lights up. Keep the battery + terminal attached to the 'xb' wire.
2) Now test the battery - terminal on all the other wire pairs. Pairs with a higher number will not cause the bulb to light up, and pairs with a lower number will cause the bulb to light up. You can find out x, because you'll find x-1 pairs that light up the lightbulb.
3) Take the battery off of the 'xb' wire, and reconnect the 'xa' and 'xb' wires.
4) Now you know the number of one pair, and you have split the remaining 998 wires into 2 groups: junctions with lower numbers, and junctions with higher numbers.
5) Now recursively sort the lower-numbered and higher-numbered groups using the same method.
Notice that this is sort of like a quicksort!
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
oliver
Newbie
Posts: 25
|
|
Re: NEW PROBLEM: 1000 Wires
« Reply #7 on: Sep 5th, 2002, 7:31am » |
Quote Modify
|
Hmm,
mallen and James, I've not much time for riddles ATM, therefore I might miss something, but I don't get how we could confuse 500b and 1a.
Since we know 1a is connected to the - pole of the bulb, and 500b is connected to the + pole, we know which is 1a because of the polarity, don't we?
But it's right, I didn't explitly write that.
|
|
IP Logged |
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: NEW PROBLEM: 1000 Wires
« Reply #8 on: Sep 5th, 2002, 11:27am » |
Quote Modify
|
You're right. That's exactly what you said. I only wonder how I missed it the first time!
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
continuum
Newbie
 
Gender:
Posts: 14
|
|
Re: NEW PROBLEM: 1000 Wires
« Reply #9 on: Nov 12th, 2002, 4:32pm » |
Quote Modify
|
I got a different solution (that uses also two traversals for N wires) that doesn't take advantage of the polarity of the battery, nor of separating the light bulb and the battery. I used them as a single device that identifies if there can be current passing through two terminals. I assumed I was allowed to connect more than two wires together, since the problem doesn't specify otherwise.
So, I propose the modificated problem. The only difference is that you don't have a light bulb and a battery, but just a single device that has two terminals and beeps if you connect them. Like those that you can find in a multimeter.
|
|
IP Logged |
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: NEW PROBLEM: 1000 Wires
« Reply #10 on: Nov 12th, 2002, 7:18pm » |
Quote Modify
|
Here are a couple of unsupported statements. Sorry I don't have writeups of the details to support them.
1) The style of solution given earlier in this thread, where you only tie wires in pairs, works (or can be tweaked a little to work) without using polarity or separating the battery from the bulb.
2) There is also a style of solution where the wires are tied in groups of different sizes: 1, 2, 3, .... The general idea is that you can tell which group a wire is in by the number of other wires that have continuity with it. When I first thought of this solution, I thought it would work only for a triangular number of wires, but that's not the case -- it can be made to work for any number.
Continuum, is #2 the kind of solution you had in mind? It would be good to see a proper writeup of that solution. Unfortunately I don't see a natural way to constrain the problem so that only one of the two solutions works.
|
|
IP Logged |
http://tim-mann.org/
|
|
|
Eric Yeh
Senior Riddler
Gender:
Posts: 318
|
|
Re: NEW PROBLEM: 1000 Wires
« Reply #11 on: Nov 13th, 2002, 5:40am » |
Quote Modify
|
Well, the polarity never "helps"; it is only a minor hindrance if anything.
My original solution was also of the "multimeter" type. This can easily be constrained within the conext of the original statement bu saying the building is too tall to see a light bulb light on the far side. But after a little thought, I decided that the restriction is actually again a "helpful" kind that guides one towards a soln more than not. But I'm curious to hear opinions.
Best,
Eric
|
|
IP Logged |
"It is better to have puzzled and failed than never to have puzzled at all."
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: NEW PROBLEM: 1000 Wires
« Reply #12 on: Nov 13th, 2002, 6:15am » |
Quote Modify
|
Eric,
I certainly used the polarity in my solution. That way, you only need to disconnect one wire in a loop to break it in two. Also, you need fewer tests on average to determine which wires are still connected when you break a loop (otherwise, you break the loop in two places and you may have to do two tests to determine which ends are connected).
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Eric Yeh
Senior Riddler
Gender:
Posts: 318
|
|
Re: NEW PROBLEM: 1000 Wires
« Reply #13 on: Nov 13th, 2002, 6:37am » |
Quote Modify
|
Yeep! Well, I don't have time to think about it carefully, but it certainly sounds workable. I guess then I am guilty of exactly what I was just railing against -- overengineering the problem to the point of simplification. The "classical" problem does not contain any polarity provisions -- that was my own addition that was meant to add a level of complexity. But apparently I did not think it out rigorously enough. I suggest removing it again from the statement of the problem.
Best,
Eric
|
|
IP Logged |
"It is better to have puzzled and failed than never to have puzzled at all."
|
|
|
continuum
Newbie
Gender:
Posts: 14
|
|
Re: NEW PROBLEM: 1000 Wires
« Reply #14 on: Nov 13th, 2002, 6:48am » |
Quote Modify
|
Well, sorry... I think I misread (or better saying I only superficially read) the solution #1
Tim, my solution is almost exactly the #2:
You separate the wires in groups of 2,3,4,5,6, ..., m-1, m. (a group of 1 wire doesn't make a lot of sense). If there are wires left, they will be in a quantity not greater than m (otherwise, you connect m+1 of them...). Let them disconnected (or put all of them in groups of 1 wire, hehe) and call them group D.
Then you go up. You can discover each of the groups by fixing a wire and seeing to how many other wires it is connected. If it is connected to 1 wire, they form group 2. If it is connected to i wires, they (all of them) form group i+1. The rest is identified by not being connected to any other wire.
First of all, for each group i, let alone one wire. Let's call that wire i* (that is: 1*, 2*, et cetera)
Now you connect wires (let's call each of them group i') from the groups in the following way:
group 2': {2,3,4,...,m}
group 3': {3,4,...,m}
...
group i': {i,...,m}
...
group m': {m}
It can be made, since there'll be one wire from group 2 (the other is "free"), two from group 3, and so on.
Next, you take care of the wires from group G. Since there are at most m of them, connect the first to group 2', the second to group 3', and so on.
If there are m wires in group G, since there are m-1 groups i', one wire will rest disconnected. No problem. Call the set of the new disconnected D*.
Then you go down. Now you separate the groups downstairs.
Let's call the wire that was in group A and now is in group B "wire {A.B}". It can identify uniquely each wire.
You can easily identify wires {i.D*} and wire {D.D*}, by verifying which of the wires in group i (or D) are disconnected.
The wires {i.j'} can be identified by seeing to how many wires they are connected now (m-j+1) and remembering to how many it was connected before, since there is only one wire from group i in each group j'.
The wires {D.j'} can be identified by similarly.
So you identify each wire.
Geez, this is quite messy, but I guess it's understandable. Do you see any mistakes on it?
Oh, and sorry about the english, but I'm in a hurry now, so I can't check the text...
|
|
IP Logged |
|
|
|
Eric Yeh
Senior Riddler
Gender:
Posts: 318
|
|
Re: NEW PROBLEM: 1000 Wires
« Reply #15 on: Nov 13th, 2002, 7:03am » |
Quote Modify
|
Ye, that sounds fine -- I think its only messy when you try to label everything; the intuition is quite clear. Nevertheless, I still think the pairs soln is much more elegant and understandable...
Best,
Eric
|
|
IP Logged |
"It is better to have puzzled and failed than never to have puzzled at all."
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print