11
$\begingroup$

There are 5 people. Each one can be lying or telling the truth, and they can't switch. Below, each person tells us how many liars exist in the group.

  1. There are at least 3 liars.
  2. There are at least 2 liars.
  3. There are at least 1 liars.
  4. There are at least 4 liars.
  5. There are at least 2 liars.

How many liars exist and who they are? Can you give an answer for N people? Explain your workflow.

$\endgroup$
5
  • 8
    $\begingroup$ As it stands, it's not clear how your question generalises for $N$ people. Can you clarify? $\endgroup$
    – hexomino
    Apr 27 at 14:34
  • 1
    $\begingroup$ Well the idea is the same but instead of 5 people you have an arbitary number and each one can argue that there are AT LEAST k liars. With k between 1 and N-1. $\endgroup$
    – Demokles
    Apr 27 at 14:37
  • 2
    $\begingroup$ @Demokles but what are each k for the general case of N people? $\endgroup$ Apr 28 at 11:53
  • 2
    $\begingroup$ I think the puzzle would be much clarified if person #1 said "There is at least 1 liar," person #2 said "There are at least 2 liars," and so on, up to person #k saying "There are at least k liars." Then the generalization would be clear. (...oops, wait, in the original/current puzzle we have two speakers saying there are 2 liars! So that can't be the right generalization.) $\endgroup$ Apr 28 at 15:52
  • $\begingroup$ Clearly grammar isn't the point yet why is acceptable to include "There are at least 1 liars"? More importantly, how are we to guess whether there are any liars? $\endgroup$ Apr 28 at 22:48
21
$\begingroup$

Here's how to approach it in general

If Person 1 says there at least $j$ liars and Person 2 says there are at least $i$ liars, with $i \leq j$ then Person 1 being a truthteller implies Person 2 is a truthteller and Person 2 being a liar implies Person 1 is a liar.

This means that if you can identify $k$ such that the number of people who say "there are at least $m$ liars" with $m>k$ is $k$, then there exists a solution and the number of liars is $k$. Notice that if a solution exists, it will be unique. If no such $k$ exists then the problem has no solution.

In the example given, there are 2 people who make a statement that "there are at least $m$ liars" with $m>2$. Hence there must be exactly two liars (which are Person 1 and Person 4 here).

$\endgroup$
2
  • $\begingroup$ What about the case of '2,4,4,5'? I think there's a unique answer for the number of liars, but in Your terminology 'k' is the answer given by a person and nobody gives the correct number. I think you might need a different variable to represent the number of people that say "there are at least m liars" or use a different variable in your first paragraph to avoid confusion, at least to avoid confusing me :) $\endgroup$ Apr 28 at 18:01
  • 1
    $\begingroup$ @JasonGoemaat I've used $k$ for two different things. I'll change the first one. Thanks. $\endgroup$
    – hexomino
    Apr 28 at 18:27
8
$\begingroup$

The logic is already explained in the other answers. So I will limit my answer to how I would get the answer.

Sort
Plot
Everyone above the diagonal is lying
Everyone below the line is telling the truth
If someone end on the line, there is no solution enter image description here

$\endgroup$
4
  • 3
    $\begingroup$ And how you choose where to put your diagonal line? $\endgroup$
    – Demokles
    Apr 27 at 20:47
  • 2
    $\begingroup$ @Demokles: You start at the bottom left corner and slowly move the line to the top right corner. You stop right before the highest number on the left side would exceed the number of items on the right side. It's basically hexomino's algorithm, just illustrated in an easy-to-understand graphical way. I like it! $\endgroup$
    – Heinzi
    Apr 28 at 7:09
  • $\begingroup$ @Demokles it's just the diagonal line, from the top left to bottom right positions in the $N\times N$ grid. You don't need to choose it based on the input. $\endgroup$ Apr 29 at 10:22
  • $\begingroup$ It is indeed the diagonal from cell {1, N} to {N, 1} of the grid. Note that in theory one of the 5 could have said "There are at least 100 liars" and end up way outside the N by N. (Way above the line, in accordance with being a liar) $\endgroup$
    – Retudin
    Apr 29 at 10:41
7
$\begingroup$

hexomino's answer is awesome and general. But let's do the brute force approach just for the fun of it.

case 1:

There is no liar... Then all the statements are false. So there are 5 liars. Contradiction.

case 2:

There is 1 liar. Again, not possible since all statements are true.

case 3:

There are 2 liars. This is possible. Statements 2, 3 and 5 are valid and 1 and 4 are false. So the liars are 1 and 4.

case 4:

There are 3 liars. This would make only statement 4 a lie so it results in a contradiction because we started from the assumption that there are 3 liars.

case 5:

There are 4 liars. Then all the statements are true, so contradiction.

Case 6:

everyone is a liar. This is not possible because everyone will be telling the truth. So contradiction

$\endgroup$
3
  • 2
    $\begingroup$ Where does "… all statements are true" come from? $\endgroup$ Apr 28 at 22:51
  • $\begingroup$ Not sure what you mean exactly. "All the statements are true" means that if you go through the 5 statements in the question, taking into account as true the assumption made in each specific case, you will see that each one of them evaluates as true. Just to make it clear, i am not talking about all the statements ever made in the history of humanity or the universe, or the multiverse or the marvel universe. $\endgroup$
    – Marius
    Apr 29 at 5:12
  • $\begingroup$ Thanks and where is it written that "All the statements are true"? $\endgroup$ May 1 at 0:51
3
$\begingroup$

This answer similar to Marius' answer, but instead of doing pure brute force I tried to deduce who were liars and who were truthers, here are my steps to find people who are 100% truthful/lying

Step 1:

I first ordered them just so it was easier for me to organize my thoughts
3) There are at least 1 liars.
2) There are at least 2 liars.
5) There are at least 2 liars.
1) There are at least 3 liars.
4) There are at least 4 liars.

Step 2:

Person (3) is telling the truth. If person (3) were lying, then there would be 0 liars, but having 0 liars would make all of them liars. This is a contradiction.
So there has to be at least 1 liar and (3) is 100% truthful.

Step 3

Person (4) is lying. Assuming there are at least 4 liars, then everyone is telling the truth, which means there are 0 liars. This is a contraction.
So (4) is 100% lying.

Step 4:

Person (1) is lying. Assuming there are at least 3 liars, then everyone is telling the truth besides person (4). This is a contradiction.
So (1) is 100% lying.

Step 5:

Persons (2) and (5) are telling the truth. I wasn't convinced that a simple contraction would suffice since there are two people, so I ran both scenarios of them lying and them being truthful. Note that they both have to be lying/truthful because their statements are the same.
Scenario 1: If persons (2) and (5) were lying and given who we have already deduced are liars, then we would have 4 liars which makes everyone's statements true. This is a contradiction.
Scenario 2: If persons (2) and (5) are telling the truth, then there would be 3 truth tellers and 2 liars. This scenario works for everyone's statements.
So 2 and 3 are 100% telling the truth.

Final:

The statements There are at least 1 liar and There are at least 2 liars are truthful and the statements There are at least 3 liars and There are at least 4 liars are falsehoods. So to answer the original question, there are two liars and they are persons (1) and (4).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.