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

[tepgn]

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

[/ QUOTE ]

You won't get that far, read the algorithm carefully, you form a groups when you get more spy answers than knights and put them aside.

Anyway I know it works because it's been verified by experts. If you say it doesn't work it's probably because it's hasn't been explained well enough (to you). But I seriously can't make it any clearer.

[Galwegian]

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

Yay - I think we have a winner. I'll ship the monies to tepgn if you want it - $5 on Tilt. Just give me a screen name.

PS Nice work [img]/images/graemlins/smile.gif[/img]

[LuckayLuck]

HOLY IT'S BEEN SOLVED
WOW

[ESKiMO-SiCKNE5S]

someone please give that guy a custom title

very nice work

[AlexM]

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

[/ QUOTE ]

You won't get that far, read the algorithm carefully, you form a groups when you get more spy answers than knights and put them aside.

Anyway I know it works because it's been verified by experts. If you say it doesn't work it's probably because it's hasn't been explained well enough (to you). But I seriously can't make it any clearer.

[/ QUOTE ]

I missed where you were setting the targetted person aside as part of the group. [img]/images/graemlins/smile.gif[/img]

[durron597]

I think I have a solution

I don't want to post it just yet but I'll put you guys on the right track (assuming my solution works which I'm pretty sure it does)

<font color="white">
Rather than solving for 100, I'm going to solve for the case "N", where there are 2N inhabitants and 3N allowable questions (so the original question is the case where N is 50). Note also that 2N &gt; 6 because we proved the case for 6 already (and that proof is important for case 2.

Choose inhabitant A. Start asking other inhabitants about A until one of the following two situations occur:

1) At least N people say that A is a knight.
2) More people say that A is a spy than say A is a knight (any number of people, so knight knight spy knight spy spy spy is 7 people, we've reached it and stop irregardless of what N is)

How to solve if we reach 1) first:

A must be a knight. At least N people have said he is a knight which means for him to be a spy, N people must be lying, which is impossible since there are fewer than N spies. Let's say it took us N + k questions to reach N "knight" answers. Thus we have k confirmed spies and A is a confirmed knight. There are 2N - k - 1 remaining unknown people. Asking A about each of these people we are done. This took us 2N - k - 1 + N + k total questions, which simplifies to 3N - 1 questions. Sweet!

I'll leave you guys to work on 2) for now, I'll post it later.</font>

edit: geeze beaten again, tepqn's answer is the same as mine just stated differently. BAH

[Shine]

I have a different solution that is guaranteed correct, and uses a different algorithm. The proof that it always works is mathematically very involved, however. The algorithm is to ask people in a circle, basically.

I am giving a math lecture soon and may use this problem. Anyone know where it is from?

[Galwegian]

[ QUOTE ]
I have a different solution that is guaranteed correct, and uses a different algorithm. The proof that it always works is mathematically very involved, however. The algorithm is to ask people in a circle, basically.

I am giving a math lecture soon and may use this problem. Anyone know where it is from?

[/ QUOTE ] I got the problem from Dr. Geoff Smith - a mathematician from the University of Bath in England. I don't think that he created the problem himself. I would be interested in seeing your alternative algorithm.