## Welcome to BrainDen.com - Brain Teasers Forum

 Welcome to BrainDen.com - Brain Teasers Forum. Like most online communities you must register to post in our community, but don't worry this is a simple free process. To be a part of BrainDen Forums you may create a new account or sign in if you already have an account. As a member you could start new topics, reply to others, subscribe to topics/forums to get automatic updates, get your own profile and make new friends. Of course, you can also enjoy our collection of amazing optical illusions and cool math games. If you like our site, you may support us by simply clicking Google "+1" or Facebook "Like" buttons at the top. If you have a website, we would appreciate a little link to BrainDen. Thanks and enjoy the Den :-)
Guest Message by DevFuse

# Play on a classic: computers

Best Answer harey, 10 May 2014 - 08:27 PM

Spoiler for Surprisingly, the answer does not depend so much on the total number of computers, but mainly on the number of suspicious computers. And even more surprisingly, there is no "worst case" neither "best case". An even more general solution working for k suspicious computer and at least (k+1) good computers:
Go to the full post

12 replies to this topic

Senior Member

• Members
• 1837 posts
• Gender:Female

Posted 14 March 2014 - 05:42 PM

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.

• -1

### #2 phil1882

phil1882

Senior Member

• Members
• 564 posts

Posted 15 March 2014 - 03:35 AM

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

Spoiler for

• 0

### #3 Rainman

Rainman

• Members
• 162 posts

Posted 15 March 2014 - 04:58 AM

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

Spoiler for
Spoiler for counterexample

Edited by Rainman, 15 March 2014 - 04:59 AM.

• 0

### #4 phil1882

phil1882

Senior Member

• Members
• 564 posts

Posted 15 March 2014 - 10:13 PM

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

• 0

### #5 harey

harey

Junior Member

• Members
• 92 posts
• Gender:Male

Posted 16 March 2014 - 08:59 PM

Spoiler for I cannot get better than

• 0

### #6 bonanova

bonanova

bonanova

• Moderator
• 6161 posts
• Gender:Male
• Location:New York

Posted 17 March 2014 - 01:26 AM

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

Spoiler for Then

Spoiler for BTW

• 0

Vidi vici veni.

### #7 phil1882

phil1882

Senior Member

• Members
• 564 posts

Posted 17 March 2014 - 07:00 AM

Spoiler for sort fashion

• 0

### #8 Rainman

Rainman

• Members
• 162 posts

Posted 17 March 2014 - 01:25 PM

Spoiler for

• 0

### #9 harey

harey

Junior Member

• Members
• 92 posts
• Gender:Male

Posted 18 March 2014 - 10:54 AM

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.

- 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:

b) both were tested

d) b+c imply 2*M tests.

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 by harey, 18 March 2014 - 11:03 AM.

• 0

### #10 Rainman

Rainman

• Members
• 162 posts

Posted 20 March 2014 - 04:18 PM

Spoiler for

Spoiler for correction

• 0

#### 0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users