Liars, Liars, Everywhere

Logic Level 5

Before you stands a panel of 100 identically appearing councilmen. These men have extremely valuable information that your nation requires, however, you must first overcome a small snag - it is known that 50 of the councilmen are consistent liars, never replying truthfully to a question, while the other 50 always speak the truth. However, we have no idea which of them are the liars, and which are the truth-tellers.

All of the councilmen know which of them are truth-tellers, and which are liars. Your task is to determine, with certainty, which are truth-tellers, and which are liars. You may ask any yes-or-no question, but only to one councilman at a time. What is the minimum number of questions you need to be allowed to ask to be certain that you can determine every councilman's alignment, for all cases?

Details:

  • For formality: Let \(S\) be the set of all questioning strategies, let \(C\) be the set of all entire councilmen alignments, and let \(f : S \times C \rightarrow \mathbb{Z}^+\) be the number of questions it takes a given strategy \(s \in S\) to unambiguously determine entire councilmen alignment \(c \in C\).

    • The answer we seek is \(\min\limits_{s \in S} \left( \max\limits_{c \in C} f(s,c) \right)\).

  • You may vary your questions based on the answers you've already received. For example, you may have two "Question #2"'s, one for if the answer to "Question #1" is 'yes', and the other if it's 'no'. You may also vary the councilmen you query in this manner.

  • The questions must be logically sound, and have a single, consistent 'yes' or 'no' answer. "Is this statement false?" is not a logically sound question.

Daniel Ploch by Daniel Ploch
×

Problem Loading...

Note Loading...

Set Loading...