Author |
Topic: CHECKING ROBOTS (Read 5386 times) |
|
karlpa
Newbie
Posts: 2
|
 |
CHECKING ROBOTS
« on: May 23rd, 2012, 2:13am » |
 Quote  Modify
|
A robots manufacturer made 101 identical robots but right after they were completed, he discovered that some of them were faulty.
They therefore appointed an engineer to identify the faulty ones and destroy them.
The following instructions were given to him:
"Every robot has a diagnostic system by which it can diagnose the status of another robot. You must connect this cable of the diagnosing robot to this socket of the tested robot, and if the led on the first robot lights up red, it means that the tested robot is working OK. Otherwise, it is faulty and must be
destroyed. Each robot can be tested maximum twice. Unfortunately, all robots are equiped with a self-control system, which means that when the faulty robots are used as diagnostic robots, they will try to mislead you by giving either correct or wrong diagnoses, so that you cannot identify them as faulty and destroy them! The normal robots have no reason of doing this, and they will always give you the correct diagnose. Obviously we could destroy all of them, but this would not be wise from a business point of you, since we know that most of them are working properly."
What is the best method for the technician to identify all the faulty ones?
|
| « Last Edit: May 23rd, 2012, 2:23am by karlpa » |
 IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender: 
Posts: 7526
|
|
Re: CHECKING ROBOTS
« Reply #1 on: May 23rd, 2012, 5:24am » |
Quote Modify
|
| hidden: |
If you put them all in a circle and robot n checks robot n+1 then you should see 1 or 2 robots signalling a defect. The first one is OK, the second, whatever it signals, is faulty.
|
|
| « Last Edit: May 23rd, 2012, 5:25am by Grimbal » |
IP Logged |
|
|
|
karlpa
Newbie
Posts: 2
|
|
Re: CHECKING ROBOTS
« Reply #2 on: May 23rd, 2012, 5:53am » |
Quote Modify
|
on May 23rd, 2012, 5:24am, Grimbal wrote:| hidden: |
If you put them all in a circle and robot n checks robot n+1 then you should see 1 or 2 robots signalling a defect. The first one is OK, the second, whatever it signals, is faulty.
|
|
|
Sorry, am a novice and not very familiar with riddles, so you may need to explain this a bit further...
Why only 1 or 2 robots signaling a defect? And why is the first OK and the second faulty?
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2872
|
|
Re: CHECKING ROBOTS
« Reply #3 on: May 23rd, 2012, 1:14pm » |
Quote Modify
|
on May 23rd, 2012, 5:53am, karlpa wrote:
Sorry, am a novice and not very familiar with riddles, so you may need to explain this a bit further...
Why only 1 or 2 robots signaling a defect? And why is the first OK and the second faulty? |
|
Grimbal's solution is for the case where there's only one faulty robot. In that situation, one robot scans the faulty robot and (correctly) signals a defect, and the faulty robot might or might not signal a defect.
In general, when a robot reports a fault, that tells you that at least one of that robot and the robot it scanned are faulty.
In another general case, with an unknown number of faulty robots, in any chain of robots where A scans B scans C scans D, etc, if the first to report a fault is G scanning H, then if G is faulty, so are F, E, D, C, B and A. In a loop, if only one reports a fault, then the reported fault must be genuine (either the robot reporting the fault is reliable, or all the robots are faulty) but any number of the robots could be faulty, starting at the faulty one and continuing round.
One strategy that works for any (known or unknown) number of faulty robots provided you know it's fewer than 19 of the 101 is to hook them all up in a big circle, find the longest run of robots which don't report a fault, take the robot scanned by the last of them (which does report a fault) and use that one to scan every other robot. With 19 fault robots, that fails when the 82 good robots are in 9 runs of up to ten each, with 8 faulty robots each separating two runs, and a run of 11 faulty robots filling the final gap - the good robots come in runs of up to 9 reported good, while the 11 bad robots put together a run of 10 reported good...
I don't know what the maximum number of bad robots you can isolate with no robot tested more than twice is, nor how many you can isolate with more tests, but I do know that no number of tests can isolate all the bad robots when more than half could be bad - if the faulty robots all agree to pretend that a given group of bad robots are good, and all the rest of the robots are bad, then if every robot tests every other robot, you end up with two cliques where every robot in the clique reports every other robot in the same clique to be good, and no way of picking which clique is the right one.
With the condition that fewer than half the robots are faulty, if you could have every robot test every other, then the good robots would be obvious - they'd be the largest clique. The question is whether you can isolate them without testing any robot a third time (which means avoiding having any robot tested by two faulty robots... unless both testers turning out to be faulty means there are 50 faulty robots without the unreliably tested one)
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7526
|
|
Re: CHECKING ROBOTS
« Reply #4 on: May 24th, 2012, 1:30am » |
Quote Modify
|
on May 23rd, 2012, 1:14pm, rmsgrey wrote:| Grimbal's solution is for the case where there's only one faulty robot. |
|
Sorry, yes. Once again I read the problem too fast.
There must have been interference with the "truckload of pills" problem where only one pill is poisonous.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7526
|
|
Re: CHECKING ROBOTS
« Reply #5 on: May 24th, 2012, 11:22pm » |
Quote Modify
|
OK, I have a solution when less than half are defective.
But not much time right now. Here is a summary.
| hidden: | - Pair the bots, make them test each other, discard pairs that show a defect.
- Pair the groups and repeat the process. At every stage you have groups of robots with the same status, and the group has 2 robots that still can be tested.
- Always put aside the unpaired group if any, when the number is odd.
- You end up with groups of 2^k robots, all different. The largest group has only good robots.
- Use one good robots to test the remaining groups. One test per group.
|
|
| « Last Edit: May 24th, 2012, 11:25pm by Grimbal » |
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7526
|
|
Re: CHECKING ROBOTS
« Reply #6 on: May 25th, 2012, 3:12pm » |
Quote Modify
|
OK, here is a more complete solution:
| hidden: | Let's assume that less than half of the robots are defective
Take a pair of robots, let them test each other. if one is good and one is defective, at least one will signal a defect. So, if no defect is signaled, they are either both good or both defective.
If one or two defects are signaled, at least one is defective, possibly both.
If you pair all robots and test them in this way, you will get a number of pairs with same status, and some that show a defect. If you discard the robots in a pair that shows a defect, you discard at least as many defective robots as good ones. So, if you started with a majority of good robots, the remaining robots still have a majority of good robots.
The last unpaired robot is put aside. It still counts for the majority.
Each pair is homogenous (it has robots with the same status). Each robot has been tested only once, so the pair can be tested twice. Considering a pair as a unit, you can do with the pairs as you did with the robots. You take one robot from each pair and test them against each other. If one shows a defect, one whole group is defective, maybe both. Discard both groups and you discard at least as many defective as good robots. If there is no defect, you get a homogenous group of 4 robots, all good or all defective. Again, each group still has 2 robots free to be tested. Again, a last unpaired group can remain, that you need to put aside.
You continue like that until you discarded or put aside all groups.
Let us call everything so far phase A
In summary, you have groups of 2^k robots, k starting with 1. Each group is homogenous and can be tested twice. You make a number of rounds for k=1, 2, 3, ... to pair the groups and make larger ones. You test two groups against each other. If no defect shows, you merge them. if a defect is shown, you discard them.
At the end of the round you get homogenous groups of size 2^(k+1). You discarded some of the groups of size 2^k, and maybe you put aside a single group of size 2^k. You know that the majority of robots is good, not counting the discarded groups.
Phase B
Take all the groups that were put aside. Among them a majority or robots is good. Since the groups all have size 2^k for some k and all sizes are different, the largest group must be than all the smaller groups together. That means the largest group can not be defective.
You now have at least one good robot. Use it to test the smaller groups that were put aside. They are still free to be tested twice. Testing one robot in the group gives the status of the whole group.
Phase C
Take all the groups that were discarded in phase A. When 2 groups were tested against each other and they showed a defect, the 2 groups were discarded. They where free to be tested twice. One test was used in the pairing, so now each group has exactly one robot free to be tested. Use the good robot you found in phase B to test the last free robot in each group. Again, testing one robot in the group determines the status of the whole group.
After this, you should know exactly the status of each robot.
Destroy them!
|
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2872
|
|
Re: CHECKING ROBOTS
« Reply #7 on: May 26th, 2012, 4:02am » |
Quote Modify
|
Nicely done 
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print