32

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.

Gamow
  • 45,573
  • 10
  • 147
  • 381
tusharmakkar08
  • 499
  • 1
  • 5
  • 15

3 Answers3

26

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

Gamow
  • 45,573
  • 10
  • 147
  • 381
  • 2
    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? – Bowdzone Mar 11 '15 at 12:45
  • @Bowdzone, I was wondering this too. We are told nothing about the other 31 monks. They could always lie, randomly lie, or always tell the truth. If given this question in an interview, one should clarify this aspect. – user2023861 Mar 11 '15 at 12:56
  • 8
    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. – Gamow Mar 11 '15 at 12:58
  • So in an edge case, you will never figure out who tells the truth but are always correct as well. Makes sense – Bowdzone Mar 11 '15 at 13:01
  • 2
    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) – Arthur Rey Mar 11 '15 at 15:58
  • 3
    @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. – Gamow Mar 11 '15 at 16:59
  • @Gamow Few things I don't get: 1- Why half the pool? What if only 1 out of 32 is wrong? 2- Why say at most 5 days? It could takes months – Arthur Rey Mar 11 '15 at 17:09
  • 1- If only 1 out of 32 is wrong, then you make a correct prediction (good) and you simultaneously get rid of one monk from the pool (good). 2- It takes 5 days to get the pool down to a single monk. On all the other days, your prediction will be correct (since the majority of the pools predicts correctly). – Gamow Mar 11 '15 at 17:13
  • 3
    @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.

     – CynicallyNaive Mar 11 '15 at 17:37
  • 2
    Upon more careful review, I realize the question doesn't really tell us to minimize number of mistakes over any particular period (i.e., how long are we on the island?). I had interpreted it as, how many mistakes until we get at least one right answer. But even if we're there infinitely long, as @Gamow pointed out, once we have four wrong guesses then we're golden for the rest of infinity. Until the honest monk dies. :( – CynicallyNaive Mar 11 '15 at 17:47
  • "We let the 32 monks collude, so that each of them predicts the first five days in a different way." How do we know that in the worst case, each monk will have a permutation of predictions that is different to that of anybody else's ? Secondly, can you prove that 5 mistakes is the minimum using some other method? – Hemant Agarwal May 18 '21 at 20:36
6

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.

Mohit Jain
  • 3,628
  • 24
  • 43
0

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.

aslum
  • 168
  • 1
  • 8
  • 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.) – CynicallyNaive Mar 11 '15 at 17:49