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$
1
  • $\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$ Mar 12, 2015 at 10:28

3 Answers 3

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$
11
  • 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, 2015 at 12:45
  • 8
    $\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, 2015 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, 2015 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, 2015 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$ Mar 11, 2015 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$
2
  • $\begingroup$ Can it be done in less than 5 mistakes ? $\endgroup$ Mar 11, 2015 at 5:41
  • $\begingroup$ It appears to me, no. $\endgroup$
    – Mohit Jain
    Mar 11, 2015 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$
1
  • $\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$ Mar 11, 2015 at 17:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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