#### “Impossible” Logic Puzzle – How Many Liars Are At The Party?

Hey, this is Presh Talwalkar A party has 100 people who are either liars or truth tellers Liars always lie And truth tellers always speak the truth After the party is over You ask each person “How many truth tellers did you shake hands with?” Each person gave a different answer Ranging from the numbers 0 to 99 The answers were the whole numbers from 0 to 99 How many liars were at the party? Give this problem a try and when you’re ready, keep watching the video for the solution This logic problem seems impossible Because you do not know Which people shook hands with each other However We can deduce from their answers How many people at the party were truth tellers And how many people are liars We’ll start by labeling each person We’ll say person 99 is the one who replied To have shaken hands with 99 truth tellers Similarly, person 98 said to have shaken hands with 98 truth tellers We’ll continue this labeling all the way down to person 0 Who shook hands with 0 truth tellers Let’s consider first person 99 Imagine person 99 was a truth teller What could we deduce from that? If person 99 is a truth teller That would mean person 99 must have shaken hands With everyone else All other 99 people at the party And Because that person said they shook hands with 99 truth tellers That means everyone else at the party Must also be a truth teller But person 99 would have then also have shook hands with person 0 Who is said to have shaken hands with 0 truth tellers How can person 0 have shaken hands with 0 truth tellers? and be a truth teller? One possibility is that 99 and 0 did not shake hands This would mean person 99 is a liar Or Person 0 shook hands only with liars Which would also mean person 99 is a liar It’s not logically possible for person 99 to be a truth teller Therefore, person 99 must be a liar We will identify person 99 accordingly Now that we know person 99 is a liar What else can we figure out? Let’s look at person 98 If person 98 is a truth teller That would mean person 98 shook hands with persons 0 to 97 And all of those people must be truth tellers We can make this deduction because we know 99 is a liar If you exclude person 99 We’re left with person 0 to 97 Which are only 98 people So the only way person 98 could be a truth teller And shake hands with 98 people Is that person 98 would have shaken hands with person 0 to 97 who must all be truth tellers But this would mean person 98 also shook hands with person 0 Who is said to have shaken hands with 0 truth tellers Once again this is possible only if 98 and 0 did not shake hands Which would make person 98 a liar Or Person 0 shook hands only with liars Which would once again mean that person 98 is a liar In either possibility We can conclude person 98 is not a truth teller And therefore, person 98 must be a liar We will label person 98 accordingly Now we can continue this process We can then inductively prove persons 97, 96, and so on, all the way down to person 1 must all be liars We’ll label each person accordingly What about person 0? We’ve already figured out that persons 1 to person 99 is a liar Everyone else at the party is a liar Therefore, person 0 necessarily shake hands with only liars There are 0 truth tellers that person 0 can shake hands with This means person 0 is telling the truth and is therefore a truth teller So the answer to this problem Is that there are 99 liars Persons 1 to 99 And exactly 1 truth teller Which is person 0 Did you figure out this problem? Thanks for watching this video Please subscribe to my channel I make videos on math and game theory You can catch me on my blog, MindYourDecisions Which you can follow on Facebook, Google+, and Patreon You can catch me at social media @preshtalwalkar And if you liked this video, please check out my books There are links in the video description

How would the people saying they shook hands with a truth teller know if that person is a truth teller even if the one saying they shook hands with truth tellers was a truth teller? A liar wouldn't say they were a liar and a liar can say they are a truth teller making when a truth teller says they are a truth teller useless. This would mean everyone would have asked a question about the person that they knew the answer to just to see if they told the truth. Example of a question would be " did you come over to my house" if they did and they said no they are a liar and if they said yes they are a truth teller.

I can't believe I got this right…

You cant figure this out unless you know exactly how many hands were shook. 99 could have not shaken a single hand and so on

if everyone shook hand with everyone, and everyone answered a different answer, then only 1 truth teller…

There's a simpler answer to this. You hinted that everyone's answer was different. If more than one person had the same answer then you can deduce that there were multiple truth tellers, because they would have shaken hands with each other. So since no answer was the same, the person who said they shook hands with no truth tellers would be the only truth there.

Person 1 shook hands with 98 people. We know 2-99 (98 people) are liars. Person 0 has to be a truth teller. 1 and 0 did not shake hands. Person 1 shook hands with only liars and is therefore a liar. So 0 is the only truth teller; there are 99 liars. It doesn't say everyone shook hands. If so, it would be a paradox and wouldn't work.

What if person 0 is a liar?

Was a bit easy

I just guessed 99 and got it right. Yay for me. They also gave the answer at the beginning

I did a different approach. I started with assuming there is only one truth teller, which makes him/her person 0. All the rest of the members could pick a different number from 1 to 99 whichever they want. Make sense. But when there are two truth tellers, they would need one more truth teller to meet the requirements. When there are three truth tellers, they would need (at least two)more truth teller again etc… So to meet the requirements, the numbers of the truth tellers would go to infinity, which doesn't make any sense. So there can only be one case: there is only one truth teller and he/she replies "0".

But what if person 0 is the liar?

I understand nothing about person 1

I think this problem is a paradox.

Think about what person 1 said:"I shook hands with 1 truth teller." If person 0 is really a truth teller, then that makes person 1 a truth teller as well. Although by saying that we make person 0 a liar as we've said person 1 is a truth teller, whereas person 0 said he shook hands with no truth tellers. But that makes person 1 a liar because then he shook hands with no truth tellers and he's telling a lie. Yet again, we make person 0 a truth teller because if person 1 is a liar, then person 0 is telling the truth. You can repeat this process infinitely, so I think there's no solution

P.S. Shout out to Italy, I'm Italian!

I FREAKIN NAILED IT!!!!

They forgot to say that hand shaking was not mandatory. However you see that it eliminates a person until you get to person 1 and person 0. Still not sure? Let's simplify it at 4 people at the party. The key is person #0!

#3 says 3 truthers

#2 says 2 truthers

#1 says 1 truther

#0 says 0 truthers

3 is essentially saying he shook hands with EVERYONE at the party and they are all telling the truth. But the #0 guy is saying he never shook hands with any truthers. Person #3 had t shake his hand to reach the quota and if he did that means person #0 also shook hands back since it' mutual. If person #0 is telling the truth then that means person #3 is a liar since he shook with 0 truthers. If person #0 is lying then that means person #3 is also a liar because there aren't enough remaining truthers in the party to make his statement true.

Now person #2. He said it was 2 truthers. Well #3 was a proven liar so he is irrelevant. Person #2 now needs both remaining people #0 and #1 to be truthers but person #0 will contradict that. So #2 is a liar. So would any n amount of people that say they shook any amount of truther hands.

It works for 1 as well.

Person #1 said he shook hands with 1 truth teller. That could only be person #0 since the rest are proven liars. But #0 says he never shook hands with any truthers. So #1 is a liar for the same reason as explained above.

So if everyone but person #0 is a liar then that means person #0 has to be telling the truth!

But wait! You say there is a contradiction? You say if everyone above person #0 is truthful then that means that when person #1 shook his hand person 1 was truthful…but that means person #0 was lying and holy moley it's a paradox! Well no. While the people above need to shake everyone yet to be proven liar's hands to prove their case, person #0 could simply have never shaken person #1's hands.

There is no paradox as long as person #0 and person #1 never actually shook hands. Shaking hands was never a requirement.

Plot Twist:

What is person 97 shook hands with 1-98, excluding 97?

Likewise for everyone below 97.

Also, if 0 is a truth teller, and 1 shook hands with 0, then both 0 and 1 are truth tellers. But that means that 2 did shake hands with 2 truth tellers, so 2 is a truth teller.

Like wise for everyone above 2.

So I'll just assume 50/50.

Finally, who said that person n shook hands with person x, where x<n?

Are you in the party?

im ganna go with 98 liars

But all the time you assumed that person 0 is a truth teller. But what it he was a liar? He lied that he shook hands with zero truth tellers?

What if P0 is a liar

I finally realized that it's not stated that everyone shook hands with everyone else. Only way it can work.

Can people in the party identify each other Liar or Truth Teller?

in other words, if I don't know the guy I shaked hand with is a Liar or Truth Teller,

How can I count how many Truth Teller is there even if I want to tell the truth?

More than presh talwalkar videos i understand the problem by comment… Lol

I finally got one!

Got it

If, on the other hand, 99 shook hands with himself but not with 0, then everyone could be Truth-tellers.

Presh Talwalker is the liar

What if person 0 is a liar

I think 1

why can't it be the zero one who told the lie and thus be a liar, Thus this deduction has some fault!

As the problem does not state you cannot shake your own hand, if persons 50-99 all shake their own hand then everyone could be telling the truth.

Zero cannot be a liar. If zero is a liar, then 99 could not have shaken 99 tt hands, as there are only 99 other people and one is a liar. Therefor 99 lies. 98 is also a liar for the same reason. So is 97, and so on. What gets complicated is one and zero. We have established that 2-99 are liars. If 1 is a truth teller, that means he has to have shaken hands with zero, and it also means zero is a truth teller. But if zero is a truth teller, and he is saying the truth when he says he shook hands with zero truth tellers, then either he shook hands with nobody, or he shook hands with some liars. He could not have possibly shook hands with one. If he did, then one would be telling the truth, which he isn't. You don't need to assume that one and zero did not shake hands, as it is not even a possibility.

Preshrunk talwalkar

At 3:00 I don't understand why we don't take the possibility of person 0 being a liar

99 people are liars

Wait, don't you attend the party?

why couldn't 0 have been a liar and lied about shaking hands with no-one? So then 0 is the only liar.

but, what if 0 is a liar?

I figured it out

You know what, I already knew the answer before the solution. I started with Person 0, and I thought "what if no one shook hands with everybody? therefore, it would make Person 0 a truth teller and the others liars." Problem solved

I think I figured this problem out. It was a political fund raiser and person 0 was the waiter.

Couldn’t person 0 be a liar because he/she might have lied about shaking hands with 0 and instead might have shakes hands with a truth teller

Politicians can answer this very well.

I approached the problem this way. First, I prove that there must be at least one truth teller. Consider Person 0. If he's a truth teller, then we're done (there is at least one truth teller, namely him). If he's a liar, then it's false that he shook hands with 0 truth tellers, so he must have shaken hands with at least one truth teller, so again there's at least one truth teller at the party. Now I prove that there is at most one truth teller. Suppose there are n truth tellers, where n > 1. Then each truth teller can have shaken hands with at most n-1 truth tellers, and so be one of Person 0, 1, …, n-1. (By definition Person x shakes hands with x truth tellers.) Hence the n truth tellers are precisely these n Persons 0, …, n-1. This would mean Person n-1 shook hands with with every other truth teller, including Person 0, which is impossible. Hence it's not the case that n > 1; i.e. there is at most 1 truth teller. Hence there's exactly 1 truth teller, i.e. 99 liars.

The way I solved it… if there would have at least two truth-tellers then at least two of them must answer the same number 1. since everyone is saying a different number hence there is just 1 truth-teller who's answering 0. I assumed everybody shook hands with everybody as a benifit of dubt.

Person 0 – Dr. House : Everybody lies

99

i finally got one out

Where is the person 100 in a 100 persons' party ?

It also shows that person 0 and person 1 didn't shake hands. How rude?

Insert politician joke hereHow would you know from a handshake?

Ive only just come across this and the logic to this is interresting. I love these predicaments where a sensible answer is seemed to be impossible, it just takes some thinking is all.

What if I shook hands with the party goers too

I also successfully got the answer which is only one truth teller. However, I just feel a bit confuse because the explanation was using Person 0 to Person 99 instead of Person 1 to Person 100.

You're right Presh. Or this entire scenario can be turned upside down by saying 0 is the only liar and 99 shook hands with themselves.

Or presh talwalker is one of the liars and this entire question is a lie

it is also be possible that person 0 is a liar

I got this one!

I had a bit of a different reasoning.

I tried starting with 2 people. If they wet eboth liars, then the guy who said he shook hands with 0 people must be tell g the truth. So then if that guy is telling the truth, anyone else could shake hands with nobody and say any number as their lie. So a so gld truth tells will produce a valid answer for any number.

And since this puzzle is being asked, there is a unique solution, so this solution is unique. :p

bad party!!

If preson 0 lie while said his shake hands with 0 liar?

What if 0 is a liar

If 0 is a truth teller than 1 must also be the truth teller but if 1 is truth teller than 0 must be a liar

This falls apart without the stipulation in the setup that all 100 people are aware of the nature of the other 99 people. In other words it's not just that Person One IS or IS NOT a liar, it's that all other Persons, 2 through 100, KNOW that Person One is or is not a liar.

I do understand the logic of this and I do agree with it, but there's no reason to make it 100 people. It could be three people, couldn't it? There is no extension of logical complexity by having it be 100 people.

I figured it out

You assumed that person 0 is a truth teller.

This is FALSE! There is NO person (Zero)! There is ONLY person's (1-100) Zero is NOT a person… So how can you "Logically" make this assumption??

i think it could be any one at one time means he/she tells the truth. Because he/she shake hands with all other liars.

Another way you can reverse the process from 0 to 99 or you can replace 0 by 99,1 by 98 …. 49 by 50.

if 0 is a truth teller

then 1 is a truth teller because he said that he shakes hand with only one truth teller that is 0. So they contradicts each other. And therefore they all contradicts to each other.

I think they all are liars.

Are you serious? A five minute video explaining what my brain figured out in 5 seconds? As soon as I saw someone was labeled person 0 I knew the answer was 99. When you mention there are 100 people, but label them as person 0-99, you've given away the answer. I guess we'll say my Logic Level is Vulcan.

Obvious possibility I see is, the person claiming to have shaken hands with 0 truth tellers is a truth teller, and all the other people are liars. The person claiming to have shaken hands with 1 truth teller did not shake hands with the actual truth teller, and is therefore lying. Everyone else either could have shaken hands with the truth teller or not, it doesn't matter

But 1 is telling the truth.

What if person 1 shook hands with person 0 then person 1 is telling the truth. Then how will you solve this?

Yes!! I did it!! But I guessed…

Yeah!!! I DID THAT THE SAME WAY IN LASS THAN 10 SECONDS. I AM. A TRUTH TELLER

If person 0 is truth teller then person 1 must be truth teller.Because he said that he shook hands with 1 truth tellers.It is true

There is a loophole here now

You said person 0 is a truth teller that means person 1 is a truth teller meaning person 0 is a liar then meaning person 1 is a liar then having person 0 be a truth teller and then a loophole

Why was Person 0 named so?

But if person 0 is a truth teller then person 1 is telling the truth the person 2 then person 3 then so on so the question is verified paradoxical

Consider the largest group of truth-tellers such that (a) nobody in the group shook hands with a truth-teller not in the group and (b) you can't divide the group further and follow (a). Say this group includes k people. The answers from the members of this group cannot be greater than or equal to k, because they are telling the truth and didn't shake hands with more than the other k-1 people in the group. Since all the answers are different, they must be 0..k. This means that someone in the group shook hands with 0 people in the group. But since the group can't be divided to separate out this person, the group can't contain any other people. Since the largest group is either empty or just contains the person who said 0, everyone else is lying. Since the person who said 0 couldn't have shaken hands with any other truth-tellers, this person is telling the truth.

Easier solution: it’s not possible that two or more truth tellers are present. Proof: if there were n>1 present, they require n different truthful answers. Max shakes for anyone is n-1. So their n different answers must be 0, 1… n-1. The guy saying 0 contradicts guy saying n-1. QED. So 0 or 1 truth-tellers present. 0 present gives contradiction

99 liars out of 100. Was this the party of a political party?

In this problem, it is considered that 0 is telling truth all the time , for example :

In person 99

If 99 didn't shake hands with 0 (according to person 0's statement 99 is a liar )

If 0 shook hands only with liars (according to 0's statement 99 is a liar)

In both case 0 is already considered to be telling the truth !

How come we can assume like that?🙄🙄🙄

Paradox 1 must then be right making him wrong

I love it! 😊 NOT being sarcastic. 😍

This can be deduced in a simpler way. Let's stick to the group of truth tellers (TT). Denote their number by N. Assume N>1. I state that there have to be two TT that shook hands with the same number of TT. Otherwise, these numbers have to be: 0,1,…,N-1. Therefore the TT with N-1 shakings shook a TT with 0 shakings. Contradiction. [This part is the same as in the video]. This proves that there at least two TT that shook hands with the same number of TT. This is, according to the problem, not true. Contradiction. This shows that N=0 or N=1. Therefore the one who told that he shook hands zero times told the truth, so he is a TT. Therefore N=1.

Can't person0 be a liar huh??

Why are you considering 0 as the over lord?

0 can be a liar and that would mean everyone else is a truth teller!

I have (what I think is) a cuter way of solving this:

Assume that k people were truth tellers, out of a total n people at the party. The cute part:

We note that each truth teller could have shaken hands with a maximum of k-1 truth tellers, so then all the truth tellers must say that they shook hands with some number of people between 0 and k-1. There are k numbers in this span, so the truth tellers must be exactly the people saying they shook hands with 0, 1, …, k-1 people.

Then we proceed essentially as before. Person k-1, a truth teller, says he shook hands with k-1 truth tellers, which is all the other truth tellers. The claim of person k-1 means that he shook hands with person 0, if they are different people. And this leads to a contradiction, since person 0 shook hands with no truth tellers.

So person k-1 and person 0 are the same person, i.e. k-1 = 0, i.e. k = 1, i.e. there is only one truth teller, i.e. there are n-1 liars.

Finally, we check this is actually possible, i.e. that the problem has a solution:

We've established that person 0 is a truth teller, and people 1 to n-1 are liars. Whomever shook hands with whomever, person 0 did not shake hands with any truth tellers, so is telling the truth. There is only one truth teller, so people 2 to n-1 must also be telling the truth. And now, person 1 is lying if and only if he did not shake hands with person 0.

There is no contradiction in this, so we do have a valid solution, and the only requirement on it is that person 1, a liar, did not shake hands with person 0, the only truth teller

It's not a solution man. This riddle is a paradox.

Hey! If person0 is a truthteller, then person1 answered truthfully. Therefore, person1 is also a truthteller! Please clarify me about how the solution given is self-consistent?

But what about person 1: who said i shook hands with one truth teller and that is the truth as well.

I guess that was a party of politicians

My question is, how do they know they shook hands with a liar/truth teller?

How do they know they shook hands with al liar as they always lye and would say that they are truth tellers

The question arises a lot of confusion

Anyways good video pressure locker

This is way too easy

Because all the answers were different only one guy must say it right

That's it

Why did I exactly figure out what the solution is just by looking at the question before he showed the solution???

What about person 1 who shook hand with person 0 and says true..