Real math challenge

[marquee]

Seeing all the supposed math challenges here that are nothing more than algebra, here's a fun one to solve.

You have x processors. You know less than half of them are defective. Out of the batch, you want to find one good processor.

To determine if they're good or bad, you can use one to test another.
If the testing processor is good, it'll always correctly tell you if the processor being tested is good or bad.
If the testing processor is bad, it will give a random answer.

Show a foolproof method of locating a good processor in less than x tests.

and no, this is not homework, I already know the answer.

 

[Chiropteran]

Just throw out all the 1133mhz pentium 3s and take one of the remaining good processors.

 

[TuxDave]

Didn't I help you solve this one a while ago?

 

[marquee]

Originally posted by: TuxDave
Didn't I help you solve this one a while ago?

I solved it myself Maybe I explained it to you later on In that case, you can't answer!

 

[TuxDave]

I think I had a better solution than yours... just I couldn't prove that it would work. But it did by proof of "3 examples are good enough"

 

[marquee]

Originally posted by: TuxDave
I think I had a better solution than yours... just I couldn't prove that it would work. But it did by proof of "3 examples are good enough"

I doubt it. x-2 is the best possible answer I think, I'll prove it to you one of these days

 

[Yax]

1 ^ 0 => 0 In conclusion, only an idiot will spend time trying to figure out how to test for bad processors with potentially bad processors when they can simply use external equipment with known good states to do so.

 

[TuxDave]

Isn't have a log(n) solution or something odd like that...

Edit: Brain hurts... I leave this to ATOT.. I hate proofs.

 

[DrPizza]

Originally posted by: marquee
Seeing all the supposed math challenges here that are nothing more than algebra, here's a fun one to solve.

You have x processors. You know less than half of them are defective. Out of the batch, you want to find one good processor.

To determine if they're good or bad, you can use one to test another.
If the testing processor is good, it'll always correctly tell you if the processor being tested is good or bad.
If the testing processor is bad, it will give a random answer.

Show a foolproof method of locating a good processor in less than x tests.

and no, this is not homework, I already know the answer.

At first, I was leaning towards it is impossible to know 100.000000000000...% sure that you have a good processor. (because the bad processors give a random answer.) But that was because I simplified the problem too far to 1 good and 1 bad. There is a (albeit verrrrrrrry small) probability that they'd both say bad until the cows come home. Or, if 2 good, they would obviously both say "good" repeatedly. And if 2 bad, there is a probability > 0, that they could both say good for as many times as you'd want to test them on each other.

But, at the other end of the spectrum... if you tested every processor with all the other processors, then EVERY bad processor would automatically be labelled "bad" by a majority of processors. And every good processor would be labelled good by a majority of processors. Thus, they could be sorted completely.

I'll ponder this for a few minutes (or hours) or on the way home and see if I can come up with an exact answer somewhere less than 99*99.

 

[DrPizza]

I believe that I came up with a shorter solution (not necessarily the shortest yet though) based on pairing the processors. Only G-G or B-B pairs could possibly give the results "G-G" Since any G-B pairing would result in the good processor identifying the bad processor as B. I'll have to ponder this further on the way home, how to implement this idea.

 

[tom3]

If I take processor #1 to test processor #2, #1 would tell me whether #2 is good or bad, and #2 would tell me whether #1 is good or bad, correct? Does this count as one test or two?