7
$\begingroup$

There are two kinds of people living in a village: those who always lie (liars) and those who always tell the truth (truth-tellers). Everybody knows each other in the village and therefore knows whether a particular villager is a liar or a truth-teller.

One day a foreigner came to the village, and saw $100$ villagers $V_1,V_2,\ldots,V_{100}$ standing lined up from left to right on the market square.

  • Villager $V_1$ pointed to some person $V_j$ to his right (with $j\ge2$) and either announced "This person is a liar" or "This person is a truth-teller".
  • Villager $V_2$ pointed to some person $V_k$ to his right (with $k\ge3$) and either announced "This person is a liar" or "This person is a truth-teller".
  • And so on, and so on, and so on
  • Finally villager $V_{99}$ pointed to person $V_{100}$ to his right and either announced "This person is a liar" or "This person is a truth-teller".

The foreigner had no idea what was going on and looked confused. Finally the village chief (who was a famous truth-teller) gave him a hint: "Among these $100$ villagers, there are at least N truth-tellers."

Question: For which values of N can we be sure that the foreigner was now able to deduce exactly which of the $100$ villagers were liars and which were truth-tellers?

Improve this question
$\endgroup$

3 Answers 3

Reset to default
7
$\begingroup$

It all boils down to the last villager. If you know what the last villager is you know what $V_{99}$ is and any other villager that pointed to him, therefore you know exactly what the villagers are that pointed to those villagers and so on. So, knowing what $V_{100}$ is has a unique state for all other villagers. So we only need to consider these two cases:

  • $V_{100}$ is a liar
  • $V_{100}$ is a truthteller

if $V_{99}$ was a liar in the first case he would be a truthteller in the second case. This is also true for all other villagers.

So ultimately there are two cases:

  • There are $X$ truthtellers
  • There are $100 - X$ truthtellers.

Only one of these cases can have more than 50 truthtellers, so if $N > 50$ we can exactly determine everyone.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ You can do better if there is a majority of truth tellers and if $N$ need not be constant. Then any $N > \min \{X, 100-X\}$ will do. E.g. with $X=1$ and $N>1$, the group containing only 1 person can't be the truth tellers. $\endgroup$
    – Lawrence
    Nov 9, 2015 at 11:28
  • 2
    $\begingroup$ @Lawrence That's true, but the question asked "For which values of N can we be sure that the foreigner was now able to deduce exactly which of the 100 villagers were liars and which were truth-tellers?" which suggests the OP was looking for an absolute limit on N, rather than a relationship between N and X. $\endgroup$
    – Gordon K
    Nov 9, 2015 at 11:53
  • $\begingroup$ @GordonK Agreed that it doesn't fit a natural reading of the question. That's the reason for the qualifier "if $N$ need not be constant" in my comment. It's still an interesting point, especially since for almost all values of $X$ with majority truth tellers, you can get away with $N \leq 50$ if $N$ could depend on $X$. $\endgroup$
    – Lawrence
    Nov 9, 2015 at 12:01
2
$\begingroup$

$N \gt 50$

All liars will be consistent with each other, and all truth tellers will be consistent with each other. This means we have two distinct groups, with at most one of size greater than 50.

If the chief tells us there are at least 51 truth tellers, the larger group must be truthful.

Improve this answer
$\endgroup$
1
$\begingroup$

Firstly, there is one trivial case where $N = 100$ and the foreigner can knows that everyone is a truth-teller.

Assuming for a minute that the village chief specified EXACTLY how many truth-tellers there were and looking at the case where $N = 50$, if we assume for a moment that every one of the villagers in the line points to the last villager, either there will be 49 liars and 50 truth-tellers pointing at a liar OR there will be 49 truth-tellers and 50 liars pointing at a truth-teller. In this case the set of responses will be identical (50 * L, 49 * T). So it is impossible to be sure for $N = 50$.

Now expanding this to the case where the chief is not specific, we have ruled out all cases where $N < 50$.

Continuing on to cases where there are more than 50 truth-tellers. Every villager forms part of a chain that links to $V_{100}$. Determining the nature of $V_{100}$ allows the foreigner to trace back each chain and determine the nature of each villager in the chain. If he makes an assumption about the nature of $V_{100}$ nature and determines how many truth-tellers there are based on that assumption, if it is greater than or equal to $N$ then his initial assumption is correct. If he adds up too few truth-tellers, he just needs to turn all his truth-teller flags to liar flags and vice versa.

Improve this answer
$\endgroup$
2
  • $\begingroup$ case N = 0 is not trivial I would say. because it means there are at least 0, not exactly 0 $\endgroup$
    – Ivo
    Nov 9, 2015 at 10:50
  • $\begingroup$ @IvoBeckers Pah - I really need to read the question more carefully! $\endgroup$
    – Gordon K
    Nov 9, 2015 at 10:51

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.