32
$\begingroup$

Suppose you are on an island with 32 monks and you are told that one of the monks is always honest. Every day the monks say whether it is going to rain. You are required to say whether it is going to rain or not. Find a strategy that would make the minimum number of mistakes and what would be the worst case number of mistakes with this strategy?

(We can consider monks can be either honest or dishonest. Honest monks always know and correctly predict true future weather while dishonest monks might or might not predict true future weather.)

It was asked to me during an interview and I came up with this approach :

I will start noting down the observations and the data collected from monks.We will select the answer which at least 51% of the monks agree to. If they collude and we make a mistake, on the next day prediction we can just remove those 51% monks. So basically it's either removal of 51% or continuing with the given monks. Hence worst case mistakes would be 5 (geometric progression with r = 1/2 last term = 1 and first term = 32)

Please also comment on whether this approach is correct and if any other better approach is available.

$\endgroup$
  • $\begingroup$ If you change it to 50% you have a well defined solution, which still works. (As there is no 51% if it is 50-50). $\endgroup$ – Dennis Jaheruddin Mar 12 '15 at 10:28
26
$\begingroup$

(1) Your approach and your analysis are correct, and with your strategy you will always make at most five wrong predictions. Every time you make a wrong prediction, this halves the number of candidates for the honest monk. The number $32$ can be halved at most five times before you are down to a single candidate.

(2) Your approach is also optimal in the following sense:

There is no strategy that would guarantee you at most four wrong predictions.

Proof: For the first five days, there are $2\cdot2\cdot2\cdot2\cdot2=32$ different ways of predicting rain/no rain.

  • We let the $32$ monks collude, so that each of them predicts the first five days in a different way.
  • We design the weather so that each of your first five predictions is incorrect.

After five days, you will have made five mistakes. Nevertheless, one of the monks has made five correct predictions; that guy is designated to be the honest monk.

$\endgroup$
  • 2
    $\begingroup$ I am probably missing something, but isn't this only working if the monks predict different things? What if everyone is always stating the correct outcome? $\endgroup$ – Bowdzone Mar 11 '15 at 12:45
  • 7
    $\begingroup$ The goal of the puzzle is that you yourself make as few wrong predictions as possible. If all monks make correct predictions all the time, then by following them you will perform very well. $\endgroup$ – Gamow Mar 11 '15 at 12:58
  • 2
    $\begingroup$ I am probably still missing something but what if the 32 monks predict the same good answer for let's say 6 days straight? You obviously can't find the good monk in 5 days, and you still don't know which monk to listen to on the 7th day. (Note that you don't know anything about the other 31 monks, they might just run out of luck after 6 days) $\endgroup$ – Arthur Rey Mar 11 '15 at 15:58
  • 3
    $\begingroup$ @Arthur Rey: It is not necessary to find the honest monk. You keep a pool of monks that you find trustworthy (since up to the current moment, all their predictions were correct). You always follow the majority opinion in your trustworthy pool. As long as this majority is right, your prediction is correct (perfect!). If the majority is wrong, then your prediction will be wrong (bad!), but you also get rid of at least half the current pool (good!). Hence: either you predict correctly, or you make a huge step towards identifying the honest monk. $\endgroup$ – Gamow Mar 11 '15 at 16:59
  • 3
    $\begingroup$ @ArthurRey I understand it to be a minimax problem. We're optimizing for the best possible worst case scenario, given our selected strategy. If all 32 monks collude and mimic the honest guy, we can't identify the honest monk. But our job isn't to identify him! Our job is to guess the weather. Therefore, our performance would be zero mistakes, which obviously isn't the worst case scenario given our strategy. $\endgroup$ – CynicallyNaive Mar 11 '15 at 17:37
6
$\begingroup$

Answer will be 5 (log N) with your approach of choosing max:

#include <iostream>
#include <algorithm>

using namespace std;

int memo[33];

int mistakes_count(int n)
{
    if (memo[n] == -1) {
        int mx = 0;
        for(int i = 1; i < n; ++i) { // 1 must be honest
            int catr = i, catw = n - i; // If all are honest, repeat
            if(catr > catw) { // Category right is the majority
                mx = std::max(mx, mistakes_count(catr));
            } else {  // Category wrong is the majority, 1 mistake done
                mx = std::max(mx, 1 + mistakes_count(catr));
            }
        }
        memo[n] = mx;
    }
    return memo[n];
}

int main() {
    for(int i = 1; i <= 32; ++i) memo[i] = -1;
    cout << mistakes_count(32);
    return 0;
}

Only way to make you wrong is that honest monk fall in minority. Now to make sure that minority consists of maxumum monks (to make the process long and more mistakes) is, there are (almost or exactly) equal votes casted for both.

R = W or R + 1 = W

So in worst case, you would be eliminating one of the monks with 1 mistake in five iterations.

$\endgroup$
  • $\begingroup$ Can it be done in less than 5 mistakes ? $\endgroup$ – tusharmakkar08 Mar 11 '15 at 5:41
  • $\begingroup$ It appears to me, no. $\endgroup$ – Mohit Jain Mar 11 '15 at 5:43
0
$\begingroup$

I am assuming that by "honest" you mean can accurately predict the weather. If not this question is kind of meaningless. An 'honest' guess with 50% accuracy is indistinguishable from a 'dishonest' guess with 50% accuracy.

Do we know the other 31 monks are dishonest? If they are then it doesn't take any tries at all. One monk will have a different answer from the other 32.

If some of the other monks are dishonest, and some are honest, it's more difficult, and will take a maximum of 5 tries to figure out, depending on how many are honest and how many are dishonest.

$\endgroup$
  • $\begingroup$ Dishonest monks might often give a right answer just to complicate our mission. However, you're right that the question should state that at least the honest monk knows whether it's going to rain. (We can infer that the dishonest ones would ask the honest one if they really cared to know the right answer and knew him to be both honest and knowledgeable.) $\endgroup$ – CynicallyNaive Mar 11 '15 at 17:49
-1
$\begingroup$

This question is poorly formed, and you're making a mistake if you assume you need a mathematical or algorithmic answer. This is especially true in an interview, where they're trying to see how you think.

Here are a list of perfectly valid strategies (and partial strategies) to minimize the number of mistakes:

  1. Ask friends and relatives of each monk whether they've ever lied.
  2. Waterboard each monk, and tell them you'll stop when they tell a lie. The last monk who hasn't lied is your guy.
  3. Look at their historical prediction record to see who's always right.
  4. Commit suicide immediately, leaving a perfect 0 for 0 record.
  5. Define the word mistake such that giving the wrong answer doesn't count as a mistake.
  6. Instead of predicting the weather, simply say whether it is going to rain or not.

These are all based on strategies used by real people faced with real problems. In order they are the detectives solution, the bad cops solution, the historians solution, the prisoners solution, the lawyers solution, and the linguists solution.

These solutions exhibit valuable skills in their profession. Your profession is probably CS. While the algorithmic/mathematical solutions are valuable skills in CS, you should first demonstrate your less common skills. If the interviewer really wants the CS solution he'll ask for it.

$\endgroup$
  • 7
    $\begingroup$ Welcome to Puzzling Stack Exchange! As this is a puzzle in logic, it is not designed for people to come up with unintended solutions to the problem, and is instead seeking answers logically deducible from the question. Hopefully this clears up any potential misconceptions! Thanks for understanding. $\endgroup$ – Aza Mar 12 '15 at 0:14
  • $\begingroup$ The interview was mentioned in the question. Why are moderators and power users so consistently bad on these sites? $\endgroup$ – Sophit Mar 12 '15 at 0:17
  • 2
    $\begingroup$ @Sophit He was asking if his solution was optimal or not... The power users aren't bad just because you disagree with them. $\endgroup$ – QuyNguyen2013 Mar 12 '15 at 15:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.