Island of Liars












10












$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 special guest for the party celebrating 2053 year.



On 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 on the party, how many truth tellers did he dance 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 on the party, assuming everyone knows who is truth teller and who is liar?











share|improve this question











$endgroup$








  • 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$
    – PiIsNot3
    2 days ago






  • 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$
    – Kradec na kysmet
    2 days ago












  • $begingroup$
    Is the King lying? What does a truth-teller say about dancing with the King?
    $endgroup$
    – Weather Vane
    2 days ago












  • $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$
    – Kradec na kysmet
    2 days ago
















10












$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 special guest for the party celebrating 2053 year.



On 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 on the party, how many truth tellers did he dance 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 on the party, assuming everyone knows who is truth teller and who is liar?











share|improve this question











$endgroup$








  • 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$
    – PiIsNot3
    2 days ago






  • 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$
    – Kradec na kysmet
    2 days ago












  • $begingroup$
    Is the King lying? What does a truth-teller say about dancing with the King?
    $endgroup$
    – Weather Vane
    2 days ago












  • $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$
    – Kradec na kysmet
    2 days ago














10












10








10


2



$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 special guest for the party celebrating 2053 year.



On 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 on the party, how many truth tellers did he dance 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 on the party, assuming everyone knows who is truth teller and who is liar?











share|improve this question











$endgroup$




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



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



On 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 on the party, how many truth tellers did he dance 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 on the party, assuming everyone knows who is truth teller and who is liar?








mathematics liars






share|improve this question















share|improve this question













share|improve this question




share|improve this question








edited 2 days ago









jafe

24.6k472246




24.6k472246










asked 2 days ago









Kradec na kysmetKradec na kysmet

797




797








  • 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$
    – PiIsNot3
    2 days ago






  • 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$
    – Kradec na kysmet
    2 days ago












  • $begingroup$
    Is the King lying? What does a truth-teller say about dancing with the King?
    $endgroup$
    – Weather Vane
    2 days ago












  • $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$
    – Kradec na kysmet
    2 days ago














  • 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$
    – PiIsNot3
    2 days ago






  • 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$
    – Kradec na kysmet
    2 days ago












  • $begingroup$
    Is the King lying? What does a truth-teller say about dancing with the King?
    $endgroup$
    – Weather Vane
    2 days ago












  • $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$
    – Kradec na kysmet
    2 days ago








3




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$
– PiIsNot3
2 days ago




$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$
– PiIsNot3
2 days ago




1




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$
– Kradec na kysmet
2 days ago






$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$
– Kradec na kysmet
2 days ago














$begingroup$
Is the King lying? What does a truth-teller say about dancing with the King?
$endgroup$
– Weather Vane
2 days ago






$begingroup$
Is the King lying? What does a truth-teller say about dancing with the King?
$endgroup$
– Weather Vane
2 days ago














$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$
– Kradec na kysmet
2 days ago




$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$
– Kradec na kysmet
2 days ago










1 Answer
1






active

oldest

votes


















10












$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.







share|improve this answer









$endgroup$













  • $begingroup$
    That's it, that was fast even with all the baits I put.
    $endgroup$
    – Kradec na kysmet
    2 days ago










  • $begingroup$
    @Kradecnakysmet Thanks, I was thrown for a second by the numbers and thought there might be a large number of solutions.
    $endgroup$
    – hexomino
    2 days ago










  • $begingroup$
    I will admit I was laughing while typing all those random numbers :D
    $endgroup$
    – Kradec na kysmet
    2 days ago












Your Answer





StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "559"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});


}
});














draft saved

draft discarded


















StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fpuzzling.stackexchange.com%2fquestions%2f81070%2fisland-of-liars%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown

























1 Answer
1






active

oldest

votes








1 Answer
1






active

oldest

votes









active

oldest

votes






active

oldest

votes









10












$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.







share|improve this answer









$endgroup$













  • $begingroup$
    That's it, that was fast even with all the baits I put.
    $endgroup$
    – Kradec na kysmet
    2 days ago










  • $begingroup$
    @Kradecnakysmet Thanks, I was thrown for a second by the numbers and thought there might be a large number of solutions.
    $endgroup$
    – hexomino
    2 days ago










  • $begingroup$
    I will admit I was laughing while typing all those random numbers :D
    $endgroup$
    – Kradec na kysmet
    2 days ago
















10












$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.







share|improve this answer









$endgroup$













  • $begingroup$
    That's it, that was fast even with all the baits I put.
    $endgroup$
    – Kradec na kysmet
    2 days ago










  • $begingroup$
    @Kradecnakysmet Thanks, I was thrown for a second by the numbers and thought there might be a large number of solutions.
    $endgroup$
    – hexomino
    2 days ago










  • $begingroup$
    I will admit I was laughing while typing all those random numbers :D
    $endgroup$
    – Kradec na kysmet
    2 days ago














10












10








10





$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.







share|improve this answer









$endgroup$



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.








share|improve this answer












share|improve this answer



share|improve this answer










answered 2 days ago









hexominohexomino

45k4139218




45k4139218












  • $begingroup$
    That's it, that was fast even with all the baits I put.
    $endgroup$
    – Kradec na kysmet
    2 days ago










  • $begingroup$
    @Kradecnakysmet Thanks, I was thrown for a second by the numbers and thought there might be a large number of solutions.
    $endgroup$
    – hexomino
    2 days ago










  • $begingroup$
    I will admit I was laughing while typing all those random numbers :D
    $endgroup$
    – Kradec na kysmet
    2 days ago


















  • $begingroup$
    That's it, that was fast even with all the baits I put.
    $endgroup$
    – Kradec na kysmet
    2 days ago










  • $begingroup$
    @Kradecnakysmet Thanks, I was thrown for a second by the numbers and thought there might be a large number of solutions.
    $endgroup$
    – hexomino
    2 days ago










  • $begingroup$
    I will admit I was laughing while typing all those random numbers :D
    $endgroup$
    – Kradec na kysmet
    2 days ago
















$begingroup$
That's it, that was fast even with all the baits I put.
$endgroup$
– Kradec na kysmet
2 days ago




$begingroup$
That's it, that was fast even with all the baits I put.
$endgroup$
– Kradec na kysmet
2 days ago












$begingroup$
@Kradecnakysmet Thanks, I was thrown for a second by the numbers and thought there might be a large number of solutions.
$endgroup$
– hexomino
2 days ago




$begingroup$
@Kradecnakysmet Thanks, I was thrown for a second by the numbers and thought there might be a large number of solutions.
$endgroup$
– hexomino
2 days ago












$begingroup$
I will admit I was laughing while typing all those random numbers :D
$endgroup$
– Kradec na kysmet
2 days ago




$begingroup$
I will admit I was laughing while typing all those random numbers :D
$endgroup$
– Kradec na kysmet
2 days ago


















draft saved

draft discarded




















































Thanks for contributing an answer to Puzzling Stack Exchange!


  • Please be sure to answer the question. Provide details and share your research!

But avoid



  • Asking for help, clarification, or responding to other answers.

  • Making statements based on opinion; back them up with references or personal experience.


Use MathJax to format equations. MathJax reference.


To learn more, see our tips on writing great answers.




draft saved


draft discarded














StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fpuzzling.stackexchange.com%2fquestions%2f81070%2fisland-of-liars%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown





















































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown

































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown







Popular posts from this blog

數位音樂下載

When can things happen in Etherscan, such as the picture below?

格利澤436b