A hard liar/truthteller type puzzle

[FCBLComish]

[ QUOTE ]
[ 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.

[/ QUOTE ]

You use 50 questions to get to this point, and then you ask your known knight about each of the 99 remaining participants. 1 question to spare should be

"Where are all the good looking women in this town"

Make sure you ask that one to a spy though....