A hard liar/truthteller type puzzle

[JaredL]

This thread has shown me that despite not liking current trends in werewolf play, I still very much [img]/images/graemlins/heart.gif[/img] POG.

[dvsfun1]

There is an accurate method for determining like pairs. Take any random pair and ask each one if the other is the same as him. The only time you will get a yes-yes answer is if they are both knights, or both lying spies.
The problem I'm having is although the knights will readily pair off, the spies will most likely opt to conceal themselves by giving no-no or yes-no answers; in an attempt to make you waste your questions.
Maybe someone can come up with a way to either isolate the pairs outright, or by remixing and cross referencing a sampling of isolated pairs.
I think there is a way here to positively identify a knight.

[kokiri]

[ QUOTE ]
[ QUOTE ]
[ QUOTE ]
Extending this idea, we see that after 51 questions we might end up with a bunch of spy pairs and a knight chain of length 0..... busto

[/ QUOTE ]

But when you have 49 spy pairs, the two remaining would have to be knights, right?

[/ QUOTE ]

I don't think that you must necessarily end up with enough spy pairs after 51 questions. Example, using my earlier notation

1k2,2k3,3k4..........24k25,25k26,26s27,25s28,24s29 ......
....2s51,1s52. Now you have asked 51 questions and you have only 26 spy pairs (namely (1,52),(2,51),...,(26,27) ) and you have no knight chain

[/ QUOTE ]

hmm looks like i made a mistake in my maths.

crap

[kokiri]

the problem is whilst you have a chain of knight answers, it's not outside the spy pairs, as i thought.

back to the drawing board.

i still think this type of method is the way to go, though.

[tepgn]

[ QUOTE ]
[ QUOTE ]
[ QUOTE ]
Extending this idea, we see that after 51 questions we might end up with a bunch of spy pairs and a knight chain of length 0..... busto

[/ QUOTE ]

But when you have 49 spy pairs, the two remaining would have to be knights, right?

[/ QUOTE ]

I don't think that you must necessarily end up with enough spy pairs after 51 questions. Example, using my earlier notation

1k2,2k3,3k4..........24k25,25k26,26s27,25s28,24s29 ......
....2s51,1s52. Now you have asked 51 questions and you have only 26 spy pairs (namely (1,52),(2,51),...,(26,27) ) and you have no knight chain

[/ QUOTE ]
This still looks like the way to go. Continue on till the end of the line and even with only 50 questions left you have a lot of information already. Notice that some people have been asked twice (or more) about someone else's nature. If you can identify them as a Knight then you know the identity of everyone they were asked about.

In fact you can make a tree diagram with person#1 at the root and work from there. All the leaf nodes will be people you've been told were a spy.

If a leaf is in fact identified as a Knight then all the nodes above him right back to the root are spies. If a 'k' is identified as a Knight then the whole tree below him is correct.

You can also complete the puzzle when you know the rest must all be Knights since there are more Knights than Spies. I've done a few smaller puzzles by hand like this.

[Galwegian]

I had an idea that might be useful. It extends the spy pair notion.

Example, suppose we have have the following information.
1k2, 3k4, 2s4. Then we can set the quadruple (1,2,3,4) aside as a spy quadruple. It must contain at least 2 spies. So the remaining people (apart from the quadruple) still have more knights than spies. Also once we have somehow determined a knight (hope springs eternal [img]/images/graemlins/smile.gif[/img] ) you will need at most 3 more questions to determine the nature of everyone in the quadruple (1,2,3,4). So you will have used only 6 questions total to determine the nature of the quadruple. You can probably extend this idea even further to spy octuples and so on. It might be useful.....?

[tepgn]

[ QUOTE ]
I had an idea that might be useful. It extends the spy pair notion.

Example, suppose we have have the following information.
1k2, 3k4, 2s4. Then we can set the quadruple (1,2,3,4) aside as a spy quadruple. It must contain at least 2 spies. So the remaining people (apart from the quadruple) still have more knights than spies. Also once we have somehow determined a knight (hope springs eternal [img]/images/graemlins/smile.gif[/img] ) you will need at most 3 more questions to determine the nature of everyone in the quadruple (1,2,3,4). So you will have used only 6 questions total to determine the nature of the quadruple. You can probably extend this idea even further to spy octuples and so on. It might be useful.....?

[/ QUOTE ]

It's obvious, this is a P=NP complete problem! It seems that most problems can be solved by hand but there's nothing that can be fomulated into an 'algorithm' that solves them all.

Was there a hint of this when you put 'hard' in the subject? [img]/images/graemlins/wink.gif[/img].

[Galwegian]

[ QUOTE ]
[ QUOTE ]
I had an idea that might be useful. It extends the spy pair notion.

Example, suppose we have have the following information.
1k2, 3k4, 2s4. Then we can set the quadruple (1,2,3,4) aside as a spy quadruple. It must contain at least 2 spies. So the remaining people (apart from the quadruple) still have more knights than spies. Also once we have somehow determined a knight (hope springs eternal [img]/images/graemlins/smile.gif[/img] ) you will need at most 3 more questions to determine the nature of everyone in the quadruple (1,2,3,4). So you will have used only 6 questions total to determine the nature of the quadruple. You can probably extend this idea even further to spy octuples and so on. It might be useful.....?

[/ QUOTE ]

It's obvious, this is a P=NP complete problem! It seems that most problems can be solved by hand but there's nothing that can be fomulated into an 'algorithm' that solves them all.

Was there a hint of this when you put 'hard' in the subject? [img]/images/graemlins/wink.gif[/img].

[/ QUOTE ]

Well, as I said somewhere in the thread before now, the person from whom I got the puzzle has claimed to have a complete solution. I have no reason to doubt this claim. This person is a brilliant puzzle solver (much better than I am, for sure) and does not tend to claim solutions unless he is completely sure of his claim. He did say that it is difficult and no one that I have given the puzzle to over the last year has been able to solve it - hence the "hard" in the title.

BTW, it cannot be NP complete since it is a finite problem (but I presume you were joking).

[tepgn]

If anyone still has the energy, here is an algorithm that solves this puzzle.


Spoiler space...







Ask a sequence of people about the guy at the end (#100) and keep going until you get more spy answers than knight answers.

Eg. 1k100, 2s100, 3k100, 4s100, 5s100 will form a seqence.

Put these people aside (1,2,3,4,5,100) and start again asking people at the start of the line about the person at the end.

6s99, put (6,99) aside.

7k98, 8s98, 9s98, put these people aside (7,8,9,98) you get the idea.

Each time you put a group aside you know it MUST have at least as many spies in than knights, since if the last person was a spy then both him and all the people who said he was a knight are spies, and if the last person is a knight then all people who said he was a spy are spies. Now the rest of the line must still have more knights than spies.

Continue in this fashion until either you have more than half of the rest of the line saying knight, in which case you know they are telling the truth because there are more knights left than spies, or until you've made so many groups and there are only 2 people left who must both be knights. In either case you have found a knight.

Now get the knight to identify the people whom were asked of their nature in each group. If knight then all the people who called him a spy are spies, if spy then all the people who call him a knight are spies. Identify the rest of the group one by one. Do this for all the groups and for any ungrouped people left over, that's it.

This always takes less than 150 questions overall since each group of n people has not taken more than 3n/2 questions each to identify.

Cheers.

[AlexM]

[ QUOTE ]
If anyone still has the energy, here is an algorithm that solves this puzzle.


Spoiler space...







Ask a sequence of people about the guy at the end (#100) and keep going until you get more spy answers than knight answers.

Eg. 1k100, 2s100, 3k100, 4s100, 5s100 will form a seqence.

Put these people aside (1,2,3,4,5,100) and start again asking people at the start of the line about the person at the end.

6s99, put (6,99) aside.

7k98, 8s98, 9s98, put these people aside (7,8,9,98) you get the idea.

Each time you put a group aside you know it MUST have at least as many spies in than knights, since if the last person was a spy then both him and all the people who said he was a knight are spies, and if the last person is a knight then all people who said he was a spy are spies. Now the rest of the line must still have more knights than spies.

Continue in this fashion until either you have more than half of the rest of the line saying knight, in which case you know they are telling the truth because there are more knights left than spies, or until you've made so many groups and there are only 2 people left who must both be knights. In either case you have found a knight.

Now get the knight to identify the people whom were asked of their nature in each group. If knight then all the people who called him a spy are spies, if spy then all the people who call him a knight are spies. Identify the rest of the group one by one. Do this for all the groups and for any ungrouped people left over, that's it.

This always takes less than 150 questions overall since each group of n people has not taken more than 3n/2 questions each to identify.

Cheers.

[/ QUOTE ]

Person 100 is a spy. Everyone you ask says "spy." You waste 50 questions getting to the point where a knight has definitely called this man a spy... and now you don't have enough questions to do anything else. Sorry, but your plan only works if the person being asked about is a knight, so it looks like your solution isn't valid. [img]/images/graemlins/frown.gif[/img]