Jump to content


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
 

Photo
- - - - -

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


  • Please log in to reply
12 replies to this topic

#1 BMAD

BMAD

    Senior Member

  • Members
  • PipPipPipPip
  • 1658 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
  • PipPipPipPip
  • 507 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

    Advanced Member

  • Members
  • PipPipPip
  • 143 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
  • PipPipPipPip
  • 507 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
  • PipPip
  • 80 posts
  • Gender:Male

Posted 16 March 2014 - 08:59 PM

Spoiler for I cannot get better than


  • 0

#6 bonanova

bonanova

    bonanova

  • Moderator
  • PipPipPipPip
  • 5563 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
The greatest challenge to any thinker is stating the problem in a way that will allow a solution.
- Bertrand Russell

#7 phil1882

phil1882

    Senior Member

  • Members
  • PipPipPipPip
  • 507 posts

Posted 17 March 2014 - 07:00 AM

Spoiler for sort fashion

  • 0

#8 Rainman

Rainman

    Advanced Member

  • Members
  • PipPipPip
  • 143 posts

Posted 17 March 2014 - 01:25 PM

Spoiler for


  • 0

#9 harey

harey

    Junior Member

  • Members
  • PipPip
  • 80 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.

 

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

  • 0

#10 Rainman

Rainman

    Advanced Member

  • Members
  • PipPipPip
  • 143 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