Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

For this question, suppose you are on the island of knights and knaves. Remember that knights always speak truth while knaves always tell a lie. (a) Suppose you come across two of the natives. You ask this question "whether the other one is a knight?" from each of them. Will you get the same answer in each case? Justify. (b) There are three natives A, B and C. Suppose A says "B and C are the same type". What can be inferred about the number of knights? (c) You would like to determine whether an odd number of A, B and C is a knight. You may ask one yes/no question to any one of them. What is the question you should ask? (d) There are two natives, A and B. Now A says, "B is a knight is the same as I am a knave". What can you determine about A and B?

i am facing problem. how to solve knight and knave problem............................... like i try to attempt (b) part i consider A= A is knight B and C is also same type like knight.... now i have to proof it. A is true only if and if B and C is knight so i make truth table like A bidirectional(A implies(B and C)) i found one row tRUE So i conclude that a,b and c are knight.... Now i don't the answer is correct or not

share|improve this question
3  
How much have you worked out so far and where are you stuck? –  Paresh Nov 23 '12 at 9:02
1  
Hint: Enumerate all possible combinations that A, B (and C) can take in each of the cases, and how they hold up to the given information. You should be able to eliminate impossible combinations. –  Paresh Nov 23 '12 at 9:06
    
If this is a homework question, you may mark it as such. Then you may post what you already know about the questions, so that you can be given a hint. –  tomglabst Nov 23 '12 at 9:07
    
yeah but i am facing problem. how to solve knight and knave problem............................... like i try to attempt (b) part –  shahida Nov 23 '12 at 9:18
add comment

3 Answers 3

For part (a), the answer is yes. If the natives are both knights or both knaves, they will both answer "yes" to the question. If one of the natives is a knight and the other one is a knave, they will both answer no to the question.

For part (b), there is always an odd number of knights. If A is a knight, then the other two are both knights or both knaves, because they are the same. If A is a knave, the other two are one knight and one knave, because the knave is lying. In both cases, there is an odd number of knights.

For part (c), you can use the question in part (b). "Are the other two the same type?" Using this question, if you get yes, no matter if the one you asked is a knight or a knave, there are an odd number of knights, which answers the question. If the person says no, then there are two knights.

For part (d), B is a knave, and A could either be a knight or a knave. The statement "B is a knight is the same as I am a knave" sounds confusing. Just split the statement into two parts: "B is a knight" and "I am a knave". The words "is the same as" tells you that the true/false component of each of these is the same. If one is false, the other is false. If one is true, the other is true. Therefore, if A is a knight, both parts of the statement are false, and the middle words "is the same as" makes the statement as a whole true. If A is a knave, the true/false component of each of the statements is different. "I am a knave" must be true and "B is a knight" must be false. Therefore, A can either be a knave or a knight, and B is always a knave.

share|improve this answer
    
Think about each part slowly, and you will get it. –  Jason Chen Apr 18 at 3:32
    
This is old enough that OP is probably long gone. For a new question, I would have stopped after your answer to (b). You have shown the approach for solving these questions, so let OP come back if s/he still has a problem. +1 for a good answer to an old problem. –  Ross Millikan Apr 18 at 4:40
    
@JasonChen Small correction: in (d), A can also be a knave. In that case the "I am a knave" part is true, and since A is lying the other part ("B is a knight") is false, and therefore also in this case B is a knave. –  Marnix Klooster Apr 18 at 5:33
    
Thanks. I changed the last parts to include the correction. –  Jason Chen Apr 18 at 22:40
add comment

You must be student of MSCS at VU, let me give you some hint, first two questions are possible by making their truth table, you should come up with all the possibilities of what A or B will answer for question a (it will be pretty amazing when you c results). b part can also be solved in the same way. For third and 4rth part you need to think a lot, as i am doing right now :)

share|improve this answer
1  
Not sure that an answer as vague as this takes us much further than the original question did... –  Simon Hayward Dec 1 '12 at 12:08
add comment

Now that there is another full answer, and the question is already fairly old, here is my approach. My favorite tool for logical problems is to use (equational) logic.

For knight/knave puzzles, we have the following axiom: $ \newcommand{\says}[2]{#1\text{ says }\unicode{x201C}#2\unicode{x201D}} \newcommand{\cansay}[2]{#1\text{ can say }\unicode{x201C}#2\unicode{x201D}} $\begin{align} \tag{0} & \says{x}{P} \;\Rightarrow\; (T(x) \equiv P) \\ \end{align} Here $\;T(x)\;$ stands for "$\;x\;$ speaks the truth" or "$\;x\;$ is a knight", and similarly $\;\lnot T(x)\;$ stands for "$\;x\;$ lies" or "$\;x\;$ is a knave".

I will be spelling out the logical part quite a bit; hope that isn't a problem.

Note that $\;\equiv\;$ is associative, and we will use that below to make logical formulas simpler to read: so below, $\;P \equiv Q \equiv R\;$ stands for either $\;(P \equiv Q) \equiv R\;$ or $\;P \equiv (Q \equiv R)\;$, which are equivalent. Do not confuse this with $\;(P \equiv Q) \;\land\; (Q \equiv R)\;$.

(a) Suppose you come across two of the natives. You ask this question "whether the other one is a knight?" from each of them. Will you get the same answer in each case?

So calling them $\;x\;$ and $\;y\;$, and calling their respective answers $\;r\;$ and $\;s\;$, we are given that $\;\says{x}{T(y) \equiv r}\;$ and $\;\says{y}{T(x) \equiv s}\;$. What can we say about $\;r\;$ and $\;s\;$? Let's simply calculate: \begin{align} & \says{x}{T(y) \equiv r} \;\land\;\says{y}{T(x) \equiv s} \\ \Rightarrow & \qquad \text{"by (0), twice -- the only thing we can do"} \\ & (T(x) \equiv T(y) \equiv r) \;\land\; (T(y) \equiv T(x) \equiv s) \\ \equiv & \qquad \text{"logic: $\;\equiv\;$ is symmetrical"} \\ & (T(x) \equiv T(y) \equiv r) \;\land\; (T(x) \equiv T(y) \equiv s) \\ \Rightarrow & \qquad \text{"logic: $\;\equiv\;$ is transitive"} \\ & r \equiv s \\ \end{align} So yes, the answers will always be the same.

(b) There are three natives A, B and C. Suppose A says "B and C are the same type". What can be inferred about the number of knights?

So we know $\;\says{A}{T(B) \equiv T(C)}\;$, in other words \begin{align} & \says{A}{T(B) \equiv T(C)} \\ \Rightarrow & \qquad \text{"by (0) -- the only thing we can do"} \\ & T(A) \equiv T(B) \equiv T(C) \\ (*) \;\;\; \equiv & \qquad \text{"logic: property of any 'chain' of $\;\equiv\;$"} \\ & \text{an even number of }T(A), T(B), T(C)\text{ is false} \\ \end{align} In other words, there is an even number of knaves among $\;A,B,C\;$, and or equivalently an odd number of knights.

The property of $\;\equiv\;$ used in step $(*)$ can be shown in this case using a truth table, and in general by an induction argument.

(c) You would like to determine whether an odd number of A, B and C is a knight. You may ask one yes/no question to any one of them. What is the question you should ask?

Ah, that's a coincidence! We just discovered in (b) that "there is an odd number of knights among $\;A,B,C\;$" can be formalized as $\;T(A) \equiv T(B) \equiv T(C)\;$.

Therefore we want to find out a question $\;Q\;$ such that the reply is always yes (true) if there is an odd number, and no (false) if there is an even number. In other words, we want to find $\;Q\;$ such that (for any $\;x,r\;$) $$ \says{x}{Q \equiv r} \;\Rightarrow\; T(A) \equiv T(B) \equiv T(C) \equiv r $$ However, since there is nothing to indicate how $\;A,B,C\;$ can affect our solution, let's be bold and try to find such a $\;Q\;$ to determine the truth of any statement $\;P\;$: $$ \says{x}{Q \equiv r} \;\Rightarrow\; P \equiv r $$ Let's try to transform that last expression into one of the form $\;Q \equiv \ldots\;$: \begin{align} & \says{x}{Q \equiv r} \;\Rightarrow\; P \equiv r \\ \Leftarrow & \qquad \text{"by (0), using transitivity of $\;\Rightarrow\;$} \\ & \qquad \phantom{\text{"}}\text{-- the only thing we know about $\;\says{\cdot}{\cdot}\;$"} \\ & (T(x) \equiv Q \equiv r) \;\Rightarrow\; P \equiv r \\ \Leftarrow & \qquad \text{"weaken -- the simplest way I see to make progress"} \\ & T(x) \equiv Q \equiv r \equiv P \equiv r \\ \equiv & \qquad \text{"logic: $\;\equiv\;$ is symmetric, twice -- to achieve $\;Q \equiv \ldots\;$"} \\ & Q \equiv T(x) \equiv P \equiv r \equiv r \\ \equiv & \qquad \text{"logic: $\;\phi \equiv \phi \;\equiv\; \text{true}\;$; simplify"} \\ & Q \equiv T(x) \equiv P \\ \equiv & \qquad \text{"introduce abbreviation (1), see below"} \\ & Q \equiv \cansay{x}{P} \\ \end{align} In the last step I introduced the abbreviation $$ \tag{1} \cansay{x}{P} \;\equiv\; T(x) \equiv P $$ that I could have used from the start, but it only becomes necessary here.

So to know anything $\;P\;$ in this world, including whether $\;A,B,C\;$ have an odd number of knights, you just ask, "Can you say $\;P\;$?", and "Yes" means that $\;P\;$ is true, "No" means it is not.

Now, can you say that's easy?

(d) There are two natives, A and B. Now A says, "B is a knight is the same as I am a knave". What can you determine about A and B?

The difficult thing here it to get the correct formalization, which is $\;\says{A}{T(B) \equiv \lnot T(A)}\;$. Now the answer is an easy calculation: \begin{align} & \says{A}{T(B) \equiv \lnot T(A)} \\ \Rightarrow & \qquad \text{"by (0) -- the only thing we can do"} \\ & T(A) \equiv T(B) \equiv \lnot T(A) \\ \equiv & \qquad \text{"logic: $\;\equiv\;$ is symmetrical"} \\ & T(A) \equiv \lnot T(A) \equiv T(B) \\ \equiv & \qquad \text{"logic: contradiction"} \\ & \text{false} \equiv T(B) \\ \equiv & \qquad \text{"logic: simplify"} \\ & \lnot T(B) \\ \end{align} So the only thing we can say is that $\;B\;$ is a knave: we know nothing about $\;A\;$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.