Problem 1179. Knights and Knaves (part 1)

Created by Alfonso Nieto-Castanon

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>This is a Matlab adaptation of the</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://en.wikipedia.org/wiki/Knights_and_Knaves\"><w:r><w:t>Knights and Knaves</w:t></w:r></w:hyperlink><w:r><w:t> logical puzzles.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>You are in an island where all inhabitants are either</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>Knights</w:t></w:r><w:r><w:t>, who always tell the truth, or</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>Knaves</w:t></w:r><w:r><w:t>, who always lie. The island inhabitants can always tell Knights and Knaves apart by their appearance, but to you, as an outsider, they look exactly the same.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Upon arriving to this island you encounter two inhabitants standing at a fork in the road. One of them is a Knight, and the other is a Knave, but you do not know which. One of the roads will lead you to the castle, where you wish to go. Your job is to ask one or several yes/no questions that will allow you to know which one is the correct road.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Implementation</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>You function will take two function handles as inputs (one per inhabitant), and must return a single scalar indicating the correct road (1 for the first road or 2 for the second road):</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ function correct_road = solver(fA, fB)]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>You may ask one inhabitant a question by evaluating his associated function handle on a char string (the 'question'). Strings must be a valid matlab commands that when evaluated return a scalar logical value (yes/no questions, where</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>true</w:t></w:r><w:r><w:t> is a yes, and</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>false</w:t></w:r><w:r><w:t> is a no). Strings may refer to the following variables:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>A: true if the first inhabitant is a Knight, false if he is a Knave</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>B: true if the second inhabitant is a Knight, false if he is a Knave</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>X: 1 if the first road leads to the castle, 2 if the second road leads to the castle</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Asking questions, examples</w:t></w:r><w:r><w:t>:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ x=fA('A==true');]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>asks the first inhabitant whether he is a Knight (note: this returns always</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>true</w:t></w:r><w:r><w:t>, since both Knights and Knaves would tell you they are Knights; remember, Knaves always lie)</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ x=fB('X==1');]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>asks the second inhabitant whether the first road leads to the castle (not particularly useful by itself since we do not know whether he is going to respond truthfully or not)</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Next problem in this series:</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://www.mathworks.com/matlabcentral/cody/problems/1180-knights-and-knaves-part-2\"><w:r><w:t>Knights and Knaves (part 2)</w:t></w:r></w:hyperlink></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

This is a Matlab adaptation of the <a href = "http://en.wikipedia.org/wiki/Knights_and_Knaves">Knights and Knaves</a> logical puzzles.You are in an island where all inhabitants are either Knights, who always tell the truth, or Knaves, who always lie. The island inhabitants can always tell Knights and Knaves apart by their appearance, but to you, as an outsider, they look exactly the same.Upon arriving to this island you encounter two inhabitants standing at a fork in the road. One of them is a Knight, and the other is a Knave, but you do not know which. One of the roads will lead you to the castle, where you wish to go. Your job is to ask one or several yes/no questions that will allow you to know which one is the correct road.ImplementationYou function will take two function handles as inputs (one per inhabitant), and must return a single scalar indicating the correct road (1 for the first road or 2 for the second road):<pre> function correct_road = solver(fA, fB)</pre>You may ask one inhabitant a question by evaluating his associated function handle on a char string (the 'question'). Strings must be a valid matlab commands that when evaluated return a scalar logical value (yes/no questions, where true is a yes, and false is a no). Strings may refer to the following variables:<ul><li>A: true if the first inhabitant is a Knight, false if he is a Knave</li><li></li><li>B: true if the second inhabitant is a Knight, false if he is a Knave</li><li></li><li>X: 1 if the first road leads to the castle, 2 if the second road leads to the castle</li></ul>Asking questions, examples:<pre> x=fA('A==true');</pre>asks the first inhabitant whether he is a Knight (note: this returns always true, since both Knights and Knaves would tell you they are Knights; remember, Knaves always lie)<pre> x=fB('X==1');</pre>asks the second inhabitant whether the first road leads to the castle (not particularly useful by itself since we do not know whether he is going to respond truthfully or not)Next problem in this series: <a href = "http://www.mathworks.com/matlabcentral/cody/problems/1180-knights-and-knaves-part-2">Knights and Knaves (part 2)</a>

Solve

Solution Stats

207 Solutions
42 Solvers

Last Solution submitted on Jan 08, 2021

Last 200 Solutions

Problem Comments

2 Comments

2 Comments

J.R.! Menzinger on 7 Jan 2013

I remembered this cartoon by reading the problem:
http://xkcd.com/246/

Alfonso Nieto-Castanon on 8 Jan 2013

I'll have to think how to incorporate the stabbing in the problem... :)

Solution Comments

Solution 863726

1 Comment

1 Comment

Jean-Marie Sainthillier on 3 Apr 2016

I have the feeling it's a cheat no ? We don't stay in the problem's definitions.

Solution 187976

1 Comment

1 Comment

Alfonso Nieto-Castanon on 8 Jan 2013

textbook solution, nice!

Problem Recent Solvers42

Problem Tags

logic puzzles

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!