Honest Monk Puzzle

Question

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.

Answer 1

(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.

Answer 2

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.

Answer 3

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.