Knights and Spies

mathsyperson · 2009-03-22 11:45:03

I came across this puzzle recently, and I think it's the kind that's best solved with a large group of people sharing and collaborating ideas. I urge you to prove me right!

You visit an island inhabited by 100 people. These people come in two types - knights and spies.
Knights always tell the truth, but spies answer questions however they like.
Every resident of the island knows the status of every other resident.

You want to find out the type of every person on the island, but the only thing you can do is ask Person A: "Is Person B a knight or a spy?"

The pamphlet you read on the way over was largely useless, but it did say that there are more knights on the island than spies.

Given this, what is the minimum number of questions you need to accomplish your task?

MathsIsFun · 2009-03-22 18:11:01

So at least 51 Knights.

And if you find a Knight, they can tell you everyone's status.

Hmmm ... if you chose a random person, say that cute redhead under the palm tree, and asked everyone else (99 people) what the redhead's status was, you would get at least 50 truthful answers. If you were *lucky* the readhead would be a Knight, and the rest would be easy. If not ....

Is this heading in a good direction?

JaneFairfax · 2009-03-22 23:15:16

Ask each fellow whether he himself is a knight or a spy. If the answer is spy, he must be a spy.

When you have identified a person as a spy, you can also ask an unidentified person the question about the identified spy. If the answer is knight, you have another spy.

mathsyperson · 2009-03-23 00:40:04

MathsIsFun has got off to a good start.
If you ask all the residents a single question, then the most common answer you get is definitely the correct one. It's this fact that makes the task possible at all.
And like you said, identifying a knight would also be a very useful thing to do.

Jane is correct on both counts, but her methods only work some of the time.
A spy might identify himself as a knight, in which case you've learnt nothing, and similarly a spy might answer questions in a way that agrees with information you know.
Since we're dealing with the worst case scenario, we can assume that a spy will never reveal himself that easily.

johaneshalim · 2009-03-23 00:48:27

150 questions!!!
by asking them to be in pair. so we have 50 pairs.
then asking each of them same question about the type of man in front of them.
the worst case is when we had 98 answers of KK (from 49 pairs) and (one group* consists of K and S )1 answer of SS ( already 100 "Questions"), otherwise is easy.
Then ask the other groups about each of the man in the *, again the worst case is if the answer is KK( of course , these answers from the 24 groups of 2 spies), ( already 48 "questions").
Then ask the next group ( must be consists of 2 knights) , then we get the answer : K and S. ( 2 "questions") .
So the total question needed is 150 questions....and that is the maximum questions needed. the minimum is depend on the pair that we could get.
" hope that am right....hehehehe, peace"

JaneFairfax · 2009-03-23 01:30:03

Er, I was interpreting this word differently.

mathsyperson wrote:

Given this, what is the minimum number of questions you need to accomplish your task?

I took it to mean the minimum possible. In that case, that would be when the island had exactly 49 spies and the first 49 people you asked all said they were spies.

mathsyperson · 2009-03-23 03:36:27

Ah. Well, sorry for any ambiguity in the question. The challenge is to minimise the the number of questions you need so that you're guaranteed to be able to identify everyone.

jonanes, I'm not sure that your method works. If every pair you make contains the same type of person, it's possible that you'll get KK answers everywhere.

Math Is Fun Forum

#1 2009-03-22 11:45:03

Knights and Spies

#2 2009-03-22 18:11:01

Re: Knights and Spies

#3 2009-03-22 23:15:16

Re: Knights and Spies

#4 2009-03-23 00:40:04

Re: Knights and Spies

#5 2009-03-23 00:48:27

Re: Knights and Spies

#6 2009-03-23 01:30:03

Re: Knights and Spies

#7 2009-03-23 03:36:27

Re: Knights and Spies

Board footer