Faulty computers

Question

You have $99$ computers in a LAN room, and you know that at least $50$ are working. The others can be faulty. The only thing you are allowed to do is to ask computer $i$ the question "Is computer $j$ working?" for any $i$ and $j$. If $i$ is working, it will tell the truth, otherwise if it is faulty, it can answer anything (maybe the truth maybe not).

Can you find a working computer, by asking the least number of questions possible?

Answer 1

I would repeat here a big part of answer on similar, but not identical question: https://puzzling.stackexchange.com/a/1666/28 . This algorithm guarantee to find one working computer in 97 questions, and if we are lucky it will need only 49 questions.

Let's call $M$ maximum number of faulty, which can be among Group of chosen $N$ computers according to our knowledge.
Our start group will include all comps, $N = 99$. Our knowledge is that $M=49$.

The goal is to find a chain from $L=(M+1)$ comps, such that each comp in the chain tells about the next one that he is a working one. The last comp in the chain will be a working for sure.
Indeed, there are only $M$ faulty, therefore at least one comp in the chain is working. If one comp is working, then he doesn't lie and comp next to him is working too. Therefore all comps after very first working in the chain are working.

So, how do we create this chain?
0. We work only with comps, which are in the Group. Ignore the others.
1. We take an arbitrary comp as a first in the chain.
2. Each time we ask last comp in the chain about arbitrary new comp: "Is it working?".
3. If "Yes" we add that new comp to the end of the chain.
4. If "No" we remove that new comp from the Group. Also we remove asked comp from the Group and the chain. [Note that at least one from the excluded once is faulty comp, so we decrease N by 2 and M by 1 here.]
5. We finish when the chain length is bigger than half of the Group size.

Now let's calculate number of questions required.
If the chain already exists after each answer "Yes" we need one less comp to finish the chain ($M+1-L$ is decreased by 1 since $L=L+1$, $M=M$); and after each "No" we would need the same number of comps to finish the chain ($L=L-1$, $M=M-1$). If the chain doesn't exist ($L=0$) then we can progress a bit faster: "Yes" gives us two steps forward and "No" gives us one step forward (because $M$ decreased). So the best scenarios are when we get always "yes" or always "no" and finish in 49 questions. In the worst scenario we create a chain getting "yes" as the first answer and then the chain is never distracted completely and meanwhile we get maximum number of "No"-s, which are 49. Each "No" removes a comp from the chain, that means that we need to add 49 comps (requires 48 questions) and remove 49 comps from the chain (requires 49 questions). In this case we will end with one comp in our group and we will know that this is working one. So in the worst case we need 97 questions.

That's it. Unfortunately I can not prove that this is optimal. Also you can check the best answer to that question: https://puzzling.stackexchange.com/a/1676/28 . I have not read it because it is spoiler for me, but possibly it includes better answer to this question too.

Answer 2

Edit: This is not a complete solution, see the comments below.

Here’s a strategy:

For $i=1,2,\ldots,49$, ask computer $i$ if computer $100-i$ is working. If computer $i$ answered ‘yes’, label computer $i$ ‘ok’ and label computer $100-i$ ‘good’. We also label computer 50 ‘good’. All of the other computers are labelled ‘bad’.

Claim: strictly greater than 50% of the computers labelled ‘good’ are working.

Proof: For each computer that answered ‘no’, two computers got labelled bad, at least one which was bad. This means more than 50% of the ‘ok’ or ‘good’ computers are working. Of those, it's not hard to check that at least as many working computers get labelled 'good' as get labelled 'ok'. This proves the claim.

Throw out the ‘bad’ and ‘ok’ computers, and iterate this process on the ‘good’ computers. Stop when only one computer is labelled ‘good’, and it must be working.

Each computer that is questioned results in at least one additional computer being thrown out, so we need at most 98 questions.

Answer 3

I suspect this isn't optimal, but this seems like the straightforward way to me.

Mark each computer by affixing a post-it note (or a piece of gum if you really like gum).

Select at random one marked computer. Ask all marked computers (including the one selected) whether the selected computer is faulty. If a majority answer that the computer is working, you have found your working computer.

Otherwise, if a majority of computers say the selected computer is faulty, then unmark the selected computer by removing the post-it note. Also unmark one other randomly selected computer. Proceeding this way, each round should end with either the answer (yay) or two fewer marked computers. Because at least one of the two computers you eliminate on each round is known to be faulty, you are guaranteed to maintain a majority of working computers.

In the worst case you have 49 faulty computers that always answer "working." And you unluckily select a faulty computer to evaluate every round. And you unluckily randomly eliminate a working computer on every round (along with the faulty computer discovered).

In the last (49th) round of this worst case scenario, you have three computers of which one is faulty and two are working, so once you determine the faulty one, both the remaining computers are working and you have your answer.

In this worst case, you will ask 99 + 97 + 95 + ... + 3 = 2,499 questions.

This worst case is pretty bad, but typically you would have to be quite unlucky to go more than a few rounds before randomly choosing a working computer to evaluate. The average case is probably more like 200 questions.

Edit: Hmm, should have thought more about this one before answering. As the above answers (or googling for "engineers and managers puzzle") demonstrate, this approach is indeed embarrassingly far from optimal... Oops.

For anyone interested in this question that is ready for a spoiler, there is an excellent discussion about how to use a tree to do considerably better than N-2 for many values of N at

http://groups.google.com/forum/#!topic/rec.puzzles/RcwwU_0EP0o

Answer 4

I’m sure there has to be a way to do it involving fewer questions, but this is the best I can come up with for now. Implemented in Python in the spirit of the question:

import itertools

def get_working_computer():    
    potential_working_computers = [get_computer(n) for n in range(0, 100)]

    for i in itertools.count():
        count = len(potential_working_computers)
        ask_about = potential_working_computers[i % count]
        positive_responses = 0
        negative_responders = []

        for j, c in enumerate(potential_working_computers):
            if 50 - positive_responses > count - j:
                negative_responders.extend(potential_working_computers[j:])
                break

            if c.ask_if_working(ask_about):
                positive_responses += 1

                if positive_responses > 49:
                    return ask_about
            else:
                negative_responders.append(c)

        potential_working_computers = negative_responders

In the best case (at least the first 50 computers are working), this takes 50 questions. In the worst case (only the last 50 computers are working and all the faulty computers answer correctly every time [except when each one’s turn comes around]), this takes 3675 questions.

Answer 5

Here is another solution that may be worth adding. Assume you have $N$ computers, $N$ odd, and at least half are working. Start by asking computer $C_2$ if computer $C_1$ is working.

1. If computer $C_2$ says no, then you know one of computers $C_1$ or $C_2$ is not working, so ignore these two computers, and start over focusing only on computers $C_{3, 4, 5, \ldots, N}$.

2. If yes, then ask computers $C_{3, 4, 5, \ldots, N}$ etc. about $C_1$, and keep going until you either have $\lceil N/2 \rceil$ yes answers, or you have an equal number of yes and no answers among computers $C_{2, 3, 4, \ldots, k}$. If you have $\lceil N/2 \rceil$ yes answers, you know computer $C_1$ is working. If you have an equal number of yes and no answers, ignore computers $C_{2\ldots k}$ and continue with computers $C_{1, k+1, k+2, \ldots N}$.

In either case one or two above, you can identify an equal number of working and non-working computers to ignore, and hence you can apply induction on the remaining computers. No computer gets asked more than one question, and once you're down to the last three you can do it in one question. Hence the total number of questions is $N-2$.

Answer 6

otherwise if it is faulty, it can answer anything.

You might have slightly mis-typed the question, but if you haven't, then you could use a SQL injection attack to get a different question in there, and abuse the fact that broken computers can answer anything.

Keep trying all the different computers, until you get one which will answer this:

Is computer J working"; Which computers are broken?--

...maybe? :-)

Answer 7

Slow, but guaranteed to work. Ask each computer if it is working. If it says no, then it is broken. If it says yes, then it is working. Keep this up until you find all broken computers. This works since a working computer can never say it isn't working.

Yes, this is not the most efficient strategy, but figured I would point out a base case that is at least guaranteed to work. :)