Play on a classic: computers

[BMAD]

Alright, I'll add a puzzle to the bunch...

You have N computers on a space station. An accident happens, and some of the computers are damaged, but you know the number of good (undamaged) computers is greater than the number of bad (damaged) ones.

Your goal is to find *one* computer that's still good.

Your only method of testing is the following: Use one computer (say, X) to test another (Y). If X is a good computer, it tells you correctly the status of Y. If X is bad, it may or may not give the correct status of Y; assume it will give whatever answer is least useful to your testing strategy.

In worst-case, how many tests must you use to find one computer that's still good? (in terms of N)

You're permitted any combination of tests, though keep in mind the bad machines may not be consistent in the results they give you.

[harey]

1) number the computers 1 to N

2) test by the computer i=max(1,last_tested) the computer (i+1)

3) if the answer is bad, discard both (and renumber)

4) go to 2 unless one of these cases occurs:

A) You discarded 2*k computers => as you always discarded a good one and a bad one, the remaining [one is /are] good.

B) You got k answers "GOOD", There cannot be a bad computer after a good one; there might well be a series a bad ones (even 0) followed by good ones (even 0). As there are at most k bad ones, (k+1)-th is good.

C) A mix of A and B... (Easy to deduct, hard to describe w/o loosing simplicity. Do not forget to adapt k.))

In any case, k tests are enough.

[phil1882]

i personally see a clear way to stratigize about all n cases.

take 6, with 2 bad cpu's

test a agianst b, b agianst c, c agianst d, d agianst e, e against f, and f against a.

if a reports good, b reports good, c reports bad, d reports bad, e reports good, and f reports good.

senarios: let 1 represent bad and 0 represent good.

abcdef

110000 then f's result makes no sense

101000 same

100100 same

100010 same

100001 here, c's report doesn't make sence

011000 here, a's report doesn't make sence

010100same

010010same

010001same

so a must be good.

so N tests will reveal at least 1 good cpu.

[Rainman]

i personally see a clear way to stratigize about all n cases.

take 6, with 2 bad cpu's

test a agianst b, b agianst c, c agianst d, d agianst e, e against f, and f against a.

if a reports good, b reports good, c reports bad, d reports bad, e reports good, and f reports good.

senarios: let 1 represent bad and 0 represent good.

abcdef

110000 then f's result makes no sense

101000 same

100100 same

100010 same

100001 here, c's report doesn't make sence

011000 here, a's report doesn't make sence

010100same

010010same

010001same

so a must be good.

so N tests will reveal at least 1 good cpu.

Let N = 13. The computers are A through M. A checks B, B checks C, ..., and M checks A. G means the computer received a good report, B means it received a bad report. 0 means the computer is good, 1 means it is bad.

ABCDEFGHIJKLM

Report: BGGGBGGBGGBGG

Status: 1111000100100

Status: 0000111000111

Status: 1000100111000

All three status suggestions are consistent with the report, and fulfill the requirement of having more good computers than bad ones. Also, every computer is bad in at least one of the status suggestions. Hence no computer can be safely considered good.

Edited March 15, 2014 by Rainman

[phil1882]

hmm interesting. ill have to think about it some more.

[harey]

near N*2.

Test A by B and B by A. One of the following happens:

a) bad/bad: at least one computer is bad, put them both aside;

b) good/bad (same as bad/good): idem;

c) good/good: both are good or both are bad; put one aside and keep one.

You never put aside 2 good computers, so you still have more good computers that bad computers. As the worst case is c), we put aside N/2 computers with N tests. (If the number is odd, keep one it for the next round.)

Proceed the same way with the computers you kept.

When you have only 3 or 4 computers, one (reciprocal) test is enough.

[bonanova]

After watching "I Robot," I want these to be good and evil robots.

You just find one with a blue light.

Problems that have a "straightforward" O(n²) complexity can often achieve O(n log n) complexity.

[phil1882]

let N be 13 with 5 bad cpus.

0 1 2 3 4 5 6 7 8 9 10 11 12 13

A B C D E F G H I J K L M N

let A test B, if good, swap.

let position 0 test C if good swap.

let position 1 test D. swap if good.

let position 1 test E. you know what to do.

position 1 test position 0.

position 2 test position 5.

position 2 test position 6.

p2 -> p0

p3 -> p7

p3 -> p8

p3 -> p1 if swap, p1->p0

p4 -> p9

p4 -> p10

p4 -> p1 if swap, p1->p0

p5 -> p10

p5 -> p11

p5 -> p2 if swap, p2 -> p0

p6 -> p12

p6 -> p13

p6 -> p2 if swap p2 -> p0

now p0 should be a good cpu.

[Rainman]

For N = 3, it can be done in one test. For N > 3, it can be done in N-3 tests.

Proof by mathematical induction: Name the computers C₁ through C_N. For N = 3 or N = 4, only one computer can be bad. Let C₁ test C₂. If the test says good, we know C₂ is good. If the test says bad, we know C₃ is good. So the statement holds for N = 3 and N = 4.

Assume the statement holds for all N < p. Then for N = p, starting with i = 1, let C_i test C_i+1 until you get a test that says bad or i > (p-1)/2, whichever happens first.

If a test says bad, you have wasted at most 2 tests on these two computers, and at least half of them are bad. Pretend they never existed. You would be in the case of N = p-2 computers, which we know can be done in at most p-5 tests. Add the two tests you wasted on the non-existent computers and you end up with at most p-3 tests total.

If you have run floor((p-1)/2) chained tests, and all those tests say good, the last computer to be tested must be good or all floor((p+1)/2) computers involved would be bad, which contradicts that more than half of the computers are good. All that remains is to show that we haven't run more than p-3 tests. For p = 5, floor((p-1)/2) = 2 = p-3. For p > 5, floor((p-1)/2) < p/2 = p - p/2 </= p - 6/2 = p-3. So for N = p, we can finish in at most p-3 tests. So if the statement holds for all N < p, it also holds for N = p. Since it holds for the trivial cases, it must hold for all N.

[harey]

N-1 (except for N=3 or 4 where you can do better).

Let's put M=(N-1)/2.

If we ask all i to test all i+1, the most unlucky case occurs when all answers are GOOD. Consider that all bad computers are followed by all good ones. We only can be sure the last one is good - there is no bad computer after a good one.

If the answer is BAD:

- discard both (you never discard two good computers)

- substract 1 from i (if i=0, take anyone)

- renumber...

Now, each computer said the next one is GOOD, so we are in the case (B)(B)(B)..GGGG.

In the worst case:

a) we always discarded a good computer and a bad one

b) both were tested

c) there were M bad computers and therefore M discardments

d) b+c imply 2*M tests.

If a bad computer says BAD, the above still applies.

I just hope I did not forget something...

@Rainman

Suppose:

a) BGBXX
b) BBGXX

c) GGBXX

The results of the tests can be GOOD and BAD in each case. 3 and 4 are special cases, so you cannot use them for induction.

Edited March 18, 2014 by harey

[Rainman]

For N = 3, it can be done in one test. For N > 3, it can be done in N-3 tests.

Proof by mathematical induction: Name the computers C₁ through C_N. For N = 3 or N = 4, only one computer can be bad. Let C₁ test C₂. If the test says good, we know C₂ is good. If the test says bad, we know C₃ is good. So the statement holds for N = 3 and N = 4.

Assume the statement holds for all N < p. Then for N = p, starting with i = 1, let C_i test C_i+1 until you get a test that says bad or i > (p-1)/2, whichever happens first.

If a test says bad, you have wasted at most 2 tests on these two computers, and at least half of them are bad. Pretend they never existed. You would be in the case of N = p-2 computers, which we know can be done in at most p-5 tests. Add the two tests you wasted on the non-existent computers and you end up with at most p-3 tests total.

If you have run floor((p-1)/2) chained tests, and all those tests say good, the last computer to be tested must be good or all floor((p+1)/2) computers involved would be bad, which contradicts that more than half of the computers are good. All that remains is to show that we haven't run more than p-3 tests. For p = 5, floor((p-1)/2) = 2 = p-3. For p > 5, floor((p-1)/2) < p/2 = p - p/2 </= p - 6/2 = p-3. So for N = p, we can finish in at most p-3 tests. So if the statement holds for all N < p, it also holds for N = p. Since it holds for the trivial cases, it must hold for all N.

It can be done in 2*ceiling(N/2)-3 tests. That is N-2 if N is odd and N-3 if N is even.

I put the flaw of my earlier post in bold. For p = 5, it is not true that the case of N = p-2 can be solved in p-5 tests, but rather in p-4 tests.

Rather than posting a new induction proof, I will post and explain the algorithm. We call a computer incognito if it has not yet been involved in a test.

1. Select a computer and label it "1". Set t = 1.

2. Set C = number of computers. If C < 3, stop.

3. Take the computer with the largest label, and use it to test one of the incognito computers.

4. If the test says GOOD, increase t by 1 and then label the tested computer with the current value of t. Else destroy both computers involved in the test and decrease t by 1.

5. If C > 2t > 0, go to 2. Else, if t = 0, go to 1. Else stop.

Note that we never destroy more good computers than bad ones, so there will always be a majority of good ones left. The number t keeps track of the largest label among labeled computers. There are two ways for the algorithm to terminate:

• if C < 3. Then only good computers are left undestroyed and we are done.
• if C is not larger than 2t. Then the computer labeled with the value of t must good, for else all t labeled computers are bad which would contradict a good majority.

So the algorithm always finds a good computer, now to show that it terminates in at most 2*ceiling(N/2)-3 tests.

No computer is tested more than once, since the algorithm only ever tests incognito computers. Hence it terminates in at most N tests.

A computer labeled "1" will remain untested, and there is at least one such computer during the course of the algorithm. Hence it terminates in at most N-1 tests.

There will always be at least one incognito computer left at the end of the test. Hence it terminates in at most N-2 tests.

If N is even, there will always be at least two incognito computers left at the end of the test because computers are destroyed in pairs. Hence it terminates in at most N-3 tests.

[LVan Toren]

The goal is to find a series of computers that say of each other that they are good.

Let's take for example 3 computers A, B and C so that

A says that B is good, while B says that A is good.

A says that C is good and C says that A is good.

That means that A, B and C are either all three good or all three are bad.

It is not possible that in that case one or two are good and two or one are bad.

Indeed suppose A and B are good.

Then C must be good too because A, being good, has said that C is good.

We have then to find a computer D so that A says that D is good and D says that A is good;

Then we have a series of four computers that are all four good or all four bad.

If we can make the series as long as half the number of computers then it is finished.

If for example there are 7 computers, A, B,... ,G and we have found a series of four

computers that are either good or bad then they must be all four good, because there

are more good computers left than bad computers, so 4 bad computers on 7 is impossible.

If there are n computers, the number of tests we have to do is
at least, when we are lucky: 2* INT((n-1)/2)
at most, when we have bad luck : 3* INT((N-1)/2)

Edited March 21, 2014 by bonanova
spoiler

[m00li]

1) number the computers 1 to N

2) test by the computer i=max(1,last_tested) the computer (i+1)

3) if the answer is bad, discard both (and renumber)

4) go to 2 unless one of these cases occurs:

A) You discarded 2*k computers => as you always discarded a good one and a bad one, the remaining [one is /are] good.

B) You got k answers "GOOD", There cannot be a bad computer after a good one; there might well be a series a bad ones (even 0) followed by good ones (even 0). As there are at most k bad ones, (k+1)-th is good.

C) A mix of A and B... (Easy to deduct, hard to describe w/o loosing simplicity. Do not forget to adapt k.))

In any case, k tests are enough.

this answer assumes that we know the number of bad computers, but we don't. what is the actual answer?