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.