20
$\begingroup$

A king goes to an island, where there are 5823 people who always tell the truth and 8723 who always lie.

The king is a special guest for the party celebrating the year 2053.

At the party, liars and truth tellers dance in couples (everyone can dance with everyone). Some people leave the dance, others join, and some don't even participate in the dances as they are not dance lovers.

After the party, the king asked everyone who had danced at the party how many truth tellers they danced with, and put the numbers into his diary. Surprisingly, when he checked his diary later on he found out he had all the numbers from 0 to 956 typed in uniquely.

How many truth tellers danced at the party, assuming everyone knows who is truth teller and who is liar?

$\endgroup$
4
  • 3
    $\begingroup$ Just to clarify a few things: 1. Do the liars have to put down a specific number, or can they just write down any number at all as long as it’s not the number of people they danced with? 2. Does the king participate in the dancing? Thanks! $\endgroup$
    – HTM
    Commented Mar 27, 2019 at 9:37
  • 1
    $\begingroup$ 1. Everyone can type whatever he/she wants as long as it's truth or lie. 2. Doesn't matter if king danced at all. $\endgroup$ Commented Mar 27, 2019 at 9:47
  • $\begingroup$ Is the King lying? What does a truth-teller say about dancing with the King? $\endgroup$ Commented Mar 27, 2019 at 9:52
  • $\begingroup$ Got the right answer, but even if the king was liar/truth teller it would still fit in, but no he didn't dance at all, he dislikes dancing. $\endgroup$ Commented Mar 27, 2019 at 9:57

3 Answers 3

17
$\begingroup$

I think that the answer is

Just $1$ truthteller danced.

Reasoning

Suppose more than one truthteller dances, say $N$. Now consider the graph of dancers just involving truthtellers, where an edge represents "danced with". Within this graph, either the lowest degree of a node is $0$, where then the highest possible is $N-2$, or the lowest degree is $1$, where the highest possible is $N-1$. In either case, by the Pigeonhole Principle, there will be at least two truthtellers who report the same number to the king. Of course, if there are zero truthtellers who danced then one of the liars would have to have told the truth - saying $0$.

Proof that this works

Suppose there is $1$ truthteller, he will report $0$. There just needs to be one liar who doesn't dance with the truthteller who reports $1$. Then everyone else is verifiably lying.

$\endgroup$
3
  • 1
    $\begingroup$ That's it, that was fast even with all the baits I put. $\endgroup$ Commented Mar 27, 2019 at 9:57
  • 1
    $\begingroup$ @Kradecnakysmet Thanks, I was thrown for a second by the numbers and thought there might be a large number of solutions. $\endgroup$
    – hexomino
    Commented Mar 27, 2019 at 9:59
  • 1
    $\begingroup$ I will admit I was laughing while typing all those random numbers :D $\endgroup$ Commented Mar 27, 2019 at 10:00
2
$\begingroup$

I wrongly interpreted the question. I thought that the king was asking everybody, "How many truthtellers danced?"

Therefore, had the king asked everyone individually , "How many truthtellers danced at the party?", then the following would have been the solution according to me:

Note one very important thing that has been mentioned, "he found out he had all the numbers from 0 to 956 typed in uniquely". This means that no two people said the same number. Also, since the king got 957 total replies then it means that exactly 957 people danced."

Now, let's look at the various possibilities.

Case 1: There were 0 truthtellers among these 957 people. This means that all the 957 were liars. But if this was the case, then the person saying 0 is saying the truth, which is a contradiction. So, all 957 people cannot be liars because then, the person who said 0 is telling the truth.

Case 2: There was one truthteller. This means that he would be the person who would have said 1. And all the others who danced were liars and lied. It is easy to see that this is a valid possibility. There can indeed be one truthteller and 956 liars and everything checks out.

So, we have found one valid solution namely, there was one truthteller and 956 liars who danced at the party. Could there be other valid possibilities? Let's explore further.

Case 3: There were 2 truthtellers. If this was the case then both these truthtellers would have said 2. But , there was only one person who said 2. So, this is not a possibility.

In fact, number of truthtellers cannot be >1 because if there were n truthtellers ( where n >1) then there would have been n people whose answer would have been "n". For instance,

if there were 3 truthtellers then exactly 3 people would have said 3 and the rest, who were all liars, would have said some other number.

If there were 4 truthtellers then exactly 4 people would have said 4 and the rest, who were all liars, would have said some other number, etc.

But everybody says a unique number and no two people say the same number.

So, in a nutshell, the only possibility is that there was one truthteller and 956 liars who danced at the party.

$\endgroup$
4
  • 3
    $\begingroup$ The king asks how many truthtellers each person danced with. They dance as couples, and may or may not change dance partners during the party. This means that truthtellers do not necessarily give the same answer since they may not have had the same dance partners. Also, nobody dances with themselves. $\endgroup$ Commented Feb 2, 2023 at 17:01
  • $\begingroup$ @JaapScherphuis The question is a bit ambiguous but i believe the intention is that the king asks everyone how many truth tellers the king himself danced with. $\endgroup$ Commented Feb 2, 2023 at 17:05
  • $\begingroup$ @GoblinGuide no, OP said in a comment that the king didn't dance at all. $\endgroup$
    – Rob Watts
    Commented Feb 2, 2023 at 17:25
  • 1
    $\begingroup$ One small nitpick about this answer - even if the king was asking about how many truth tellers he had personally danced with, there's nothing in the question that guarantees he danced with everyone who danced. So had there been multiple truth tellers who danced, he could have gotten two answers saying he danced with one truth teller. However, even though it is wrong this answer is still useful because it shows that the answer is the same (one truth teller) even with a different interpretation. $\endgroup$
    – Rob Watts
    Commented Feb 2, 2023 at 17:39
2
$\begingroup$

I don't understand that "directed graph" business in the accepted answer, nor why it's obvious that whatever is obvious, so in words:

the liars can say whatever they want, but given n truth tellers, no truth teller can say more than n-1 since at most they can dance with every other truth teller, but not themselves. And the only sequence of n numbers that goes no higher than n-1 is 0, 1, 2, ... n-1 which has n entries. But the person who says n-1 dances with every other truth teller, meaning that nobody can say 0 since they all danced with that person who says n-1. Contradiction! Unless n=1. Then the sequence is one element long: 0, and all the other numbers are provided by liars.

example: if there are 4 tt, one has to say 3, and none of the remaining three can say 0 since they all danced with at least the one who says 3.

And for the sake of completeness, there cannot be 0 tt because then no liar danced with a tt, meaning the liar who said 0 would be telling the truth.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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