Some tricky logic puzzles.

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

tomtom2357
Posts: 563
Joined: Tue Jul 27, 2010 8:48 am UTC

Some tricky logic puzzles.

Postby tomtom2357 » Mon Dec 26, 2011 10:48 am UTC

Okay, I have some puzzles for everyone to try to solve.

1. Some aliens come and abduct 10 people. The aliens line them in a line so that each person can see the next person's head, they then paint the people's heads either blue or green and tell them that they have to guess the color of their head, and if they get it wrong they will die. Assuming that the people are told beforehand that this is going to happen, what is the best strategy? (Also no cheating i.e. saying it differently, waiting a certain amount of time before saying etc, if the aliens suspect that you are cheating they will zap everyone! :twisted: )

2. There are three people, a knight, a knave, and a spy. The knight only tells the truth, the knave always lies, and the spy can either lie or tell the truth. You have three questions to determine what each person is.
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.

mfb
Posts: 950
Joined: Thu Jan 08, 2009 7:48 pm UTC

Re: Some tricky logic puzzles.

Postby mfb » Mon Dec 26, 2011 3:18 pm UTC

#1 appears in every second thread here, usually with prisoners and hats.
Try to solve it with 10 (or any other number) different head/hat colors ;).

#2: What would be defined as "lie" if the question is not a yes/no-question?
Anyway, solution with yes/no-questions:
Spoiler:
Question 1 to A: "If I would ask you whether you are the knight, what would you answer?"
"Yes" -> knight or spy
"No" -> knave or spy

Question 2 to B: "Is A the spy?"
(Yes at Q1,Yes at Q2) -> (A,B,C) is (spy,knight,knave) or (knight,knave,spy) -> ask B "If I would ask you whether you are the knight, what would you answer?"
(Yes,No) -> (knight,spy,knave) or (spy,knave,knight) -> ask C "If I would ask you whether you are the knight, what would you answer?"
(No,Yes) -> (spy,knight,knave) or (knave,spy,knight) -> ask C "If I would ask you whether you are the knight, what would you answer?"
(No,No) -> (spy,knave,knight) or (knave,knight,spy) -> ask B "If I would ask you whether you are the knight, what would you answer?"
In any case, you can determine the identity of the person you asked the third question, and take the appropriate case from the 4*2 cases.

User avatar
jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: Some tricky logic puzzles.

Postby jestingrabbit » Mon Dec 26, 2011 3:30 pm UTC

Number 2 is far from new here

viewtopic.php?p=3602#p3602

1 is actually a little different from the usual presentation with it specified that you can see only the next person's head, rather than everyone ahead of you, and there is no information about the order in which people are asked the colour of their head, though we might assume that they are in a "last in line asked first" order I think.

There's clearly a method that saves five people, but I'm not sure that there aren't probabilistic methods that have a better expected outcome.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

User avatar
Qaanol
The Cheshirest Catamount
Posts: 3069
Joined: Sat May 09, 2009 11:55 pm UTC

Re: Some tricky logic puzzles.

Postby Qaanol » Mon Dec 26, 2011 3:50 pm UTC

mfb, your response to the knight-knave-spy puzzle is not a solution.

tomtom2357 wrote:Okay, I have some puzzles for everyone to try to solve.

1. Some aliens come and abduct 10 people. The aliens line them in a line so that each person can see the next person's head, they then paint the people's heads either blue or green and tell them that they have to guess the color of their head, and if they get it wrong they will die. Assuming that the people are told beforehand that this is going to happen, what is the best strategy? (Also no cheating i.e. saying it differently, waiting a certain amount of time before saying etc, if the aliens suspect that you are cheating they will zap everyone! :twisted: )

I assume the people are made to guess in order starting at the back of the line, and take “each person can see the next person’s head” to mean each person can only see the head of the one person immediately in front of him or here, and the person at the front of the line cannot see any other person’s head. Another way of reading that would have the people in a circle.
Spoiler:
Each person knows one bit of information, namely the color of the head in front of them. Each person needs one bit of information, namely the color of their own head. Each person conveys one bit of information by speaking a color.
However, since no one can see all the other people, no one can give the standard parity guess at the start. There is a trivial strategy that saves half the people at minimum, and three fourths on average if the colors are randomly assigned. That is for each person with no information to guess the color in front of them, and that next person to guess the color that was just communicated.

tomtom2357 wrote:2. There are three people, a knight, a knave, and a spy. The knight only tells the truth, the knave always lies, and the spy can either lie or tell the truth. You have three questions to determine what each person is.

Spoiler:
Referring to the three people as A, B, and C, approach person A and ask Q1:
“If I were to ask you ‘Is person B the spy?’ and you were to answer, would your answer be in the affirmative?”

If answer to Q1 is in the affirmative, then approach person C. If the answer to Q1 is in the negative, then approach person B. Either way, then ask Q2:
“If I were to ask you ‘Are you the knight?’ and you were to answer, would your answer be in the affirmative?”

Regardless of answer to Q2, stay where you are and ask Q3:
“If I were to ask you ‘Is person A the spy?’ and you were to answer, would your answer be in the affirmative?”

Analysis of answers:
YYY: A=Spy, B=Knave
YYN: A=Knave, B=Spy
YNY: A=Spy, B=Knight
YNN: A=Knight, B=Spy
NYY: damn Yankees A=Spy, B=Knight
NYN: A=Knave, B=Knight
NNY: A=Spy, B=Knave
NNN: A=Knight, B=Knave

Unfortunately this does not leave room for the most important question, which is Q4:
“If I were to ask you ‘Is tomtom2357 the same person as scratch123?’ and you were to answer, would your answer be in the affirmative?”

Anyway, here’s a follow-up puzzle: you meet another (knight, knave, spy) trio, but this time you only get to ask 2 yes-or-no questions. However, all three of the people will answer both questions. How can you determine their identities? Can you do it without using any meta-questions (ie. no questions about what someone would answer to a question)?
wee free kings

mfb
Posts: 950
Joined: Thu Jan 08, 2009 7:48 pm UTC

Re: Some tricky logic puzzles.

Postby mfb » Mon Dec 26, 2011 9:37 pm UTC

Qaanol wrote:mfb, your response to the knight-knave-spy puzzle is not a solution.

What is wrong? If it is just the level of detail: Who cares.

The follow-up puzzle is interesting.

User avatar
Qaanol
The Cheshirest Catamount
Posts: 3069
Joined: Sat May 09, 2009 11:55 pm UTC

Re: Some tricky logic puzzles.

Postby Qaanol » Mon Dec 26, 2011 9:48 pm UTC

mfb wrote:
Spoiler:
Question 1 to A: "If I would ask you whether you are the knight, what would you answer?"
"Yes" -> knight or spy
"No" -> knave or spy

Question 2 to B: "Is A the spy?"
(Yes at Q1,Yes at Q2) -> (A,B,C) is (spy,knight,knave) or (knight,knave,spy) -> ask B "If I would ask you whether you are the knight, what would you answer?"

Spoiler:
In fact, (Yes at Q1,Yes at Q2) -> (A,B,C) is (spy,knight,knave) or (knight,knave,spy) or (knight, spy, knave)


mfb wrote:
Spoiler:
(No,No) -> (spy,knave,knight) or (knave,knight,spy) -> ask B "If I would ask you whether you are the knight, what would you answer?"

Spoiler:
In fact, (No,No) -> (A,B,C) is (spy,knave,knight) or (knave,knight,spy) or (knave,spy,knight)
wee free kings

mfb
Posts: 950
Joined: Thu Jan 08, 2009 7:48 pm UTC

Re: Some tricky logic puzzles.

Postby mfb » Mon Dec 26, 2011 10:03 pm UTC

Oh, you are right.
Spoiler:
And you have a nice idea to avoid the spy


My ideas for your puzzle are along the lines of
Spoiler:
arrange the three in a circular way, ask "is the person in front of you X"
, but so far there were some cases left without a certain way to separate them.

User avatar
Qaanol
The Cheshirest Catamount
Posts: 3069
Joined: Sat May 09, 2009 11:55 pm UTC

Re: Some tricky logic puzzles.

Postby Qaanol » Tue Dec 27, 2011 9:36 pm UTC

There is a particularly elegant solution to my follow-up puzzle.
wee free kings

Nitrodon
Posts: 497
Joined: Wed Dec 19, 2007 5:11 pm UTC

Re: Some tricky logic puzzles.

Postby Nitrodon » Tue Dec 27, 2011 11:47 pm UTC

Qaanol wrote:Anyway, here’s a follow-up puzzle: you meet another (knight, knave, spy) trio, but this time you only get to ask 2 yes-or-no questions. However, all three of the people will answer both questions. How can you determine their identities? Can you do it without using any meta-questions (ie. no questions about what someone would answer to a question)?

Spoiler:
First, ask something with an obvious answer (e.g., "Does 1 plus 1 equal 2?"), or more generally something for which the knight and knave would answer differently in a known manner (e.g., "Are you the spy?"). The person who answered differently from the other two is either the knight or the knave: which one it is depends on his answer.

Next, point to one of the two you haven't identified, and ask whether that person is the spy. Ignore the answers from everyone except the knight or knave you've already identified. Now, you know who everyone is.

User avatar
Qaanol
The Cheshirest Catamount
Posts: 3069
Joined: Sat May 09, 2009 11:55 pm UTC

Re: Some tricky logic puzzles.

Postby Qaanol » Wed Dec 28, 2011 12:21 am UTC

Nitrodon wrote:
Spoiler:
First, ask something with an obvious answer (e.g., "Does 1 plus 1 equal 2?"), or more generally something for which the knight and knave would answer differently in a known manner (e.g., "Are you the spy?"). The person who answered differently from the other two is either the knight or the knave: which one it is depends on his answer.

Next, point to one of the two you haven't identified, and ask whether that person is the spy. Ignore the answers from everyone except the knight or knave you've already identified. Now, you know who everyone is.

Nicely done.

Here are the questions I had come up with:
Spoiler:
1. Are you the spy?
2. Is the person to your left the spy?

(“Leftness” wrapping around in a circle of course.)
wee free kings

tomtom2357
Posts: 563
Joined: Tue Jul 27, 2010 8:48 am UTC

Re: Some tricky logic puzzles.

Postby tomtom2357 » Wed Dec 28, 2011 7:12 am UTC

Okay, I have some puzzles for everyone to try to solve.

1. Some aliens come and abduct 10 people. The aliens line them in a line so that each person can see the next person's head, they then paint the people's heads either blue or green and tell them that they have to guess the color of their head, and if they get it wrong they will die. Assuming that the people are told beforehand that this is going to happen, what is the best strategy? (Also no cheating i.e. saying it differently, waiting a certain amount of time before saying etc, if the aliens suspect that you are cheating they will zap everyone! )

For this question, there is a deterministic method which saves at least 9 people.
Also, my definition of a lie is anything that can't be considered even remotely truthful (e.x. "What color is the sky?" "yellow." would obviously be false)

Unfortunately this does not leave room for the most important question, which is Q4:
“If I were to ask you ‘Is tomtom2357 the same person as scratch123?’ and you were to answer, would your answer be in the affirmative?”

P.S. Who is scratch123?
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.

Trebla
Posts: 387
Joined: Fri Apr 02, 2010 1:51 pm UTC

Re: Some tricky logic puzzles.

Postby Trebla » Wed Dec 28, 2011 1:52 pm UTC

tomtom2357 wrote:
Some aliens come and abduct 10 people.


For this question, there is a deterministic method which saves at least 9 people.


As has been pointed out, your restriction of being able to see only the person in front of you and not the entire set of people in front of you removes the parity solution which is common for this riddle (e.g. last person counts the number of green hats and gives a specific answer if it's odd). It would help if you clarified if this was an intentional variation of the riddle or an oversight.

As for #2, though it's assumed, you may want to explicitly state that each one knows the identities of the other two (or explicitly state that they don't) since many solutions seem to hinge on that knowledge. Also, a fun variation is to posit that they answer in a language which is foreign to you and you don't know the words for 'yes' and 'no'.

tomtom2357
Posts: 563
Joined: Tue Jul 27, 2010 8:48 am UTC

Re: Some tricky logic puzzles.

Postby tomtom2357 » Thu Dec 29, 2011 3:40 am UTC

Oops, sorry everybody can see all of the people in front of them. And yes, the knight, knave, and spy know who each other are.

Ok I have two other puzzles:

1. You meet five people, a knight, a knave, a spy, an anti-knight (always answers the opposite of what a knight would answer), and an anti-knave (always answers the opposite of what a knave would answer), you have 5 questions to determine who is who.

2. This is based on the foreign language idea that trebla came up with. As my first idea was taken by this: viewtopic.php?p=3602#p3602 I have come up with an even more devious problem (so devious in fact, that I don't know if it has a solution). You meet another triplet, but this time it is knight, knave, random (random just randomly answers, his answers do not have to be true or false, also they all know who each other are), but they speak in a foreign language. Their language has four words, Ja, da, ka, and la, two words for yes and two words for no. However, none of them like repeating the previous answer (e.x. If one of them says Ja, then the next answer will have to be either da, ka, or la).
Easy: You have 9 questions to determine who is who.
Medium: You have 6 questions to determine who is who.
Hard: You have 4 questions to determine who is who.
Extreme: You have an assistant who without thinking uses one of your four questions and asks one of them "Is the sky blue" to which he answers "Ja", can you still determine who is who with your remaining 3 questions?
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.

mfb
Posts: 950
Joined: Thu Jan 08, 2009 7:48 pm UTC

Re: Some tricky logic puzzles.

Postby mfb » Thu Dec 29, 2011 11:29 pm UTC

I think the hard and extreme versions have more cases than you can distinguish with the questions, but I did not calculate it.

What is the difference between an anti-knight and a knave, and the difference between an anti-knave and a knight, for yes/no-questions?
If they are different, there are 5!=120 possible layouts, so you need at least 7 (edited, my mistake) yes/no-questions or you have to define what the reaction to other questions is (e.g. what happens if I ask the knight "who is who"? ;)).
If they are not different, there are still 30 possible layouts, as you can hit the spy (at least with the first question) I doubt that it is possible.
Last edited by mfb on Fri Dec 30, 2011 11:31 am UTC, edited 1 time in total.

User avatar
Qaanol
The Cheshirest Catamount
Posts: 3069
Joined: Sat May 09, 2009 11:55 pm UTC

Re: Some tricky logic puzzles.

Postby Qaanol » Fri Dec 30, 2011 3:53 am UTC

mfb wrote:What is the difference between an anti-knight and a knave, and the difference between an anti-knave and a knight, for yes/no-questions?

Q: Are you a knight?
Knight: Yes
Knave: Yes
Anti-Knight: No
Anti-Knave: No

Q: Are you a spy?
Knight: No
Knave: Yes
Anti-Knight: Yes
Anti-Knave: No
wee free kings

tomtom2357
Posts: 563
Joined: Tue Jul 27, 2010 8:48 am UTC

Re: Some tricky logic puzzles.

Postby tomtom2357 » Fri Dec 30, 2011 6:48 am UTC

Actually for my first question 2^7=128>120=5! so in theory you only need 7 questions.
1. Easy: You have 10 questions to determine who is who.
Medium: You have 8 questions to determine who is who.
Hard: You have 7 questions to determine who is who
For my second question you still only have to decide between six options so in theory 3 questions should be enough.
2. Bonus question 1: This time, paradox questions are allowed, but if a person cannot answer without violating their personality they will stay silent. You are allowed three questions to decide who is who.
Bonus question 2: Paradox questions are allowed, but this time instead of staying silent their head will explode, they die, and you cannot ask them any more questions (because they are dead), you are allowed three questions to decide who is who.
Bonus question 3: paradoxes are banned again, only 3 questions allowed to decide who is who.
Last edited by tomtom2357 on Sat Dec 31, 2011 6:15 am UTC, edited 1 time in total.
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.

mfb
Posts: 950
Joined: Thu Jan 08, 2009 7:48 pm UTC

Re: Some tricky logic puzzles.

Postby mfb » Fri Dec 30, 2011 11:36 am UTC

That you don't know the language increases the different cases instead of helping. For each of the 6 layouts, you have additional combinations of the answers. The point that you don't have to learn the full language makes the analysis tricky, but at least you have to distinguish between two different words, which gives you 12 cases.
There are 6 possible languages, so maybe you need the full 36 combinations of language and positions.

@Qaanol: Thanks. So you have to be careful with references to the asked person. Well, should not harm.

tomtom2357
Posts: 563
Joined: Tue Jul 27, 2010 8:48 am UTC

Re: Some tricky logic puzzles.

Postby tomtom2357 » Sat Dec 31, 2011 6:14 am UTC

Okay then, I shall edit my other post, but are my first three bonus puzzles still valid for that problem? The reason why I added more words is that for only two words all your statements change from Q into "If I asked you Q, would you answer ja?" which eliminates the language difference.
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.

tomtom2357
Posts: 563
Joined: Tue Jul 27, 2010 8:48 am UTC

Re: Some tricky logic puzzles.

Postby tomtom2357 » Fri Jan 06, 2012 5:22 am UTC

Have I finally stumped everyone on the forum?
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.

tomtom2357
Posts: 563
Joined: Tue Jul 27, 2010 8:48 am UTC

Re: Some tricky logic puzzles.

Postby tomtom2357 » Fri Jan 13, 2012 8:42 am UTC

I will post here every week to keep this on the 1st page of the fora until somebody solves my problem. :D
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.

curtis95112
Posts: 638
Joined: Thu Jan 27, 2011 5:23 pm UTC

Re: Some tricky logic puzzles.

Postby curtis95112 » Fri Jan 13, 2012 1:35 pm UTC

That wouldn't be nice.
I hope we don't get another twenty people thinking the same thing about their pet puzzles
Mighty Jalapeno wrote:
Tyndmyr wrote:
Роберт wrote:Sure, but at least they hit the intended target that time.

Well, if you shoot enough people, you're bound to get the right one eventually.

Thats the best description of the USA ever.

tomtom2357
Posts: 563
Joined: Tue Jul 27, 2010 8:48 am UTC

Re: Some tricky logic puzzles.

Postby tomtom2357 » Sat Jan 14, 2012 4:26 am UTC

Well, somebody will eventually solve my problem, and then I will stop posting. This will just provide the incentive for them to solve it. :D
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.

mfb
Posts: 950
Joined: Thu Jan 08, 2009 7:48 pm UTC

Re: Some tricky logic puzzles.

Postby mfb » Sat Jan 14, 2012 3:31 pm UTC

Maybe you want to show that they are solvable at all first? ;)

tomtom2357
Posts: 563
Joined: Tue Jul 27, 2010 8:48 am UTC

Re: Some tricky logic puzzles.

Postby tomtom2357 » Sun Jan 15, 2012 9:38 am UTC

Okay then, I will stop posting for this one, but can someone do my turing complexity problem, that has solutions! :D
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.

curtis95112
Posts: 638
Joined: Thu Jan 27, 2011 5:23 pm UTC

Re: Some tricky logic puzzles.

Postby curtis95112 » Tue Jan 17, 2012 2:21 am UTC

tomtom2357 wrote:Well, somebody will eventually solve my problem, and then I will stop posting. This will just provide the incentive for them to solve it. :D


Uh no. That's called coercion. It just makes people hate you.

It's also considered bad manners.
Mighty Jalapeno wrote:
Tyndmyr wrote:
Роберт wrote:Sure, but at least they hit the intended target that time.

Well, if you shoot enough people, you're bound to get the right one eventually.

Thats the best description of the USA ever.

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 26766
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: Some tricky logic puzzles.

Postby gmalivuk » Tue Jan 17, 2012 3:03 pm UTC

curtis95112 wrote:It's also considered bad manners.
Also against the rules for pretty much everywhere except Forum Games.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

sfwc
Posts: 225
Joined: Tue Mar 29, 2011 1:41 pm UTC

Re: Some tricky logic puzzles.

Postby sfwc » Sat Jan 21, 2012 4:20 pm UTC

tomtom2357 wrote:Actually for my first question 2^7=128>120=5! so in theory you only need 7 questions.
1. Easy: You have 10 questions to determine who is who.
Medium: You have 8 questions to determine who is who.
This is possible.
Spoiler:
We shall not make much use of the cunning distinction between the knight and the anti-knave. We shall just treat them as distinguishable truth-tellers. Of course, the anti-knave won't answer just any question truthfully, but they will tell the truth provided that we only ask questions not referring to their own identity. We will be careful to only ask such questions. Similarly, this will allow us to treat the knave and the anti-knight as distinguishable lie-tellers.

Let's label the 5 people A, B, C, D and E. First question, to A: `Is grass green?'. Let's say the answer is yes (the procedure if the answer is no is similar). So now we know A is either the spy, the knight or the anti-knave. Second question, also to A: `Is either B or C the spy?'. Let's say the answer is no (once more, the procedure if the answer is yes is similar). So now we know that neither B nor C can be the spy. Third question, to B (or to D if the answer to the second question was yes): `Is grass green?'.

Case 1: The answer to the third question is yes. Then B is either the knight or the anti-knave, and will truthfully answer questions not referring to his own identity. We now use the remaining 5 questions to ask about the identities of the other 4 people, and having determined who they are we can deduce who B is. We have 5 questions, so we can distinguish up to 32 possibilities. On the other hand, the number of possible arrangements consistent with the answers given so far is 20 (12 if A is the spy, and 8 if he isn't), so we can distinguish them.

Case 2: The answer to the third question is no. Then B is either the knave or the anti-knight, and will always lie when asked about the other 4 people. As before, we can distinguish up to 32 possibilities with the remaining 5 questions, and now the number of possible arrangements is 28 (12 if A is the spy, and 16 if he isn't), so we can distinguish them.
tomtom2357 wrote:Hard: You have 7 questions to determine who is who
This is not possible.
Spoiler:
Again, let's label the people A, B, C, D and E. We may as well assume that the first question, which we'll call Q1, is addressed to A. Now think about the 120 - 24 = 96 possible arrangements in which A isn't the spy. Each such arrangement determines the answer to Q1. Either there are at least 96/2 = 48 of these arrangements for which A will answer yes, or else at least 48 for which A will answer no. Lets say the first of these possibilities occurs (the argument in the other case is similar). Since, if A is the spy, it is always possible for him to answer yes, if A does say yes then with the remaining 6 questions we have to distinguish at least 48 + 24 = 72 possibilities. That can't be done.
I have an extra question, which explores what can be done with anti-knights and anti-knaves. You are a prisoner. You are taken to a room containing 4 people, who you know are a knight, a knave, an anti-knight and an anti-knave, though you don't know who is who. You must ask a single question to one of these 4 people. If they answer yes, you will be released, and otherwise you will be shot. What question should you ask? Logically complex questions are permitted.

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: Some tricky logic puzzles.

Postby skeptical scientist » Sat Jan 21, 2012 6:57 pm UTC

sfwc wrote:I have an extra question, which explores what can be done with anti-knights and anti-knaves. You are a prisoner. You are taken to a room containing 4 people, who you know are a knight, a knave, an anti-knight and an anti-knave, though you don't know who is who. You must ask a single question to one of these 4 people. If they answer yes, you will be released, and otherwise you will be shot. What question should you ask? Logically complex questions are permitted.

Spoiler:
It makes absolutely no difference (as long as you ask a non-paradoxical question), since whatever question you ask, at most one of the knight/anti-knight will answer yes, and at most one of the knave/anti-knave will answer yes, so you have at best a 50% chance of getting a yes answer. (It could possibly be worse if you answer paradoxical questions which can't be answered by the knight or knave, but it can't be better.)

Edit: This is, of course, all false.
Last edited by skeptical scientist on Sun Jan 22, 2012 6:13 am UTC, edited 1 time in total.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

User avatar
Gwydion
Posts: 336
Joined: Sat Jun 02, 2007 7:31 pm UTC
Location: Chicago, IL

Re: Some tricky logic puzzles.

Postby Gwydion » Sat Jan 21, 2012 7:16 pm UTC

sfwc wrote:I have an extra question, which explores what can be done with anti-knights and anti-knaves. You are a prisoner. You are taken to a room containing 4 people, who you know are a knight, a knave, an anti-knight and an anti-knave, though you don't know who is who. You must ask a single question to one of these 4 people. If they answer yes, you will be released, and otherwise you will be shot. What question should you ask? Logically complex questions are permitted.

This seemed tough at first, and I'm not sure if this is the answer you're looking for.
Spoiler:
Ask the following question: "If I asked the other three 'Is the grass green?', would there be more "no" answers than "yes" answers?" The knave and anti-knight would both see two yes answers, and thus lie and say yes. The knight and anti-knave would see two no answers, and also say yes.
I don't think my answer is any more logically complex than the majority of the self-referential solutions throughout the thread - did you mean for something else?

User avatar
t1mm01994
Posts: 299
Joined: Mon Feb 15, 2010 7:16 pm UTC
Location: San Francisco.. Wait up, I'll tell you some tales!

Re: Some tricky logic puzzles.

Postby t1mm01994 » Sat Jan 21, 2012 11:38 pm UTC

Spoiler:
Since the anti's are defined by saying the opposite of what a usual person would say, that's impossible.

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: Some tricky logic puzzles.

Postby skeptical scientist » Sun Jan 22, 2012 6:13 am UTC

t1mm01994 wrote:
Spoiler:
Since the anti's are defined by saying the opposite of what a usual person would say, that's impossible.

You gave the same flawed proof that I gave.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

tomtom2357
Posts: 563
Joined: Tue Jul 27, 2010 8:48 am UTC

Re: Some tricky logic puzzles.

Postby tomtom2357 » Sun Jan 22, 2012 8:27 am UTC

Gwydion wrote:
sfwc wrote:I have an extra question, which explores what can be done with anti-knights and anti-knaves. You are a prisoner. You are taken to a room containing 4 people, who you know are a knight, a knave, an anti-knight and an anti-knave, though you don't know who is who. You must ask a single question to one of these 4 people. If they answer yes, you will be released, and otherwise you will be shot. What question should you ask? Logically complex questions are permitted.

This seemed tough at first, and I'm not sure if this is the answer you're looking for.
Spoiler:
Ask the following question: "If I asked the other three 'Is the grass green?', would there be more "no" answers than "yes" answers?" The knave and anti-knight would both see two yes answers, and thus lie and say yes. The knight and anti-knave would see two no answers, and also say yes.
I don't think my answer is any more logically complex than the majority of the self-referential solutions throughout the thread - did you mean for something else?

I have another question of this type: you are taken to a room with a knight and a knave, they speak in a different language to you and they have 4 words ja, da, ka, and la two words for yes and no. You get two question to one of them, and if they answer ja on one of the questions, you will be freed, if not, then you will be shot.
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.

User avatar
t1mm01994
Posts: 299
Joined: Mon Feb 15, 2010 7:16 pm UTC
Location: San Francisco.. Wait up, I'll tell you some tales!

Re: Some tricky logic puzzles.

Postby t1mm01994 » Sun Jan 22, 2012 12:04 pm UTC

skeptical scientist wrote:
t1mm01994 wrote:
Spoiler:
Since the anti's are defined by saying the opposite of what a usual person would say, that's impossible.

You gave the same flawed proof that I gave.

Excuse me, I did not actually read your spoiler. But yeah, it's the same already. I just fail to see what's wrong with it.

User avatar
jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: Some tricky logic puzzles.

Postby jestingrabbit » Sun Jan 22, 2012 12:44 pm UTC

Well,

Spoiler:
if you ask a question about the people in the room, and make a partition between the questioned and the others, the symmetry breaks, that is what is wrong with it. Its certainly an accurate argument about any question regarding things outside the room, but, just like the old "one guard always lies, and one always tells the truth", if you ask about how the other would answer, you escape the bind that you're in.


Of course, this depends on a particular interpretation of what an anti person is. If they put themselves in the shoes of the person they're related to, work out what their answer would be and then reverse it, then your argument is right. But, if they answer from their own shoes, as it were, and then it breaks down.

So, we kinda need a more clearly delineated notion of anti people. For instance, what is the anti person interpretation of this post?

Qaanol wrote:
mfb wrote:What is the difference between an anti-knight and a knave, and the difference between an anti-knave and a knight, for yes/no-questions?

Q: Are you a knight?
Knight: Yes
Knave: Yes
Anti-Knight: No
Anti-Knave: No

Q: Are you a spy?
Knight: No
Knave: Yes
Anti-Knight: Yes
Anti-Knave: No
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

sfwc
Posts: 225
Joined: Tue Mar 29, 2011 1:41 pm UTC

Re: Some tricky logic puzzles.

Postby sfwc » Sun Jan 22, 2012 3:36 pm UTC

Gwydion wrote:This seemed tough at first, and I'm not sure if this is the answer you're looking for.
Spoiler:
Ask the following question: "If I asked the other three 'Is the grass green?', would there be more "no" answers than "yes" answers?" The knave and anti-knight would both see two yes answers, and thus lie and say yes. The knight and anti-knave would see two no answers, and also say yes.
I don't think my answer is any more logically complex than the majority of the self-referential solutions throughout the thread - did you mean for something else?

Your solution has the same basic idea as mine (ask about the other people in the room), but the question you give is logically simpler than mine, which was complex enough that I felt I ought to explicitly allow complexity.

Congratulations!

tomtom2357 wrote:You are taken to a room with a knight and a knave, they speak in a different language to you and they have 4 words ja, da, ka, and la two words for yes and no. You get two question to one of them, and if they answer ja on one of the questions, you will be freed, if not, then you will be shot.

I assume that you intended to include the extra condition that, simply out of cultural preference, nobody will ever give the same answer that was just given. Without this extra condition, there is no way to guarantee your survival, but with this condition you can survive.
Spoiler:
Ask the question `If I asked if you were a knight, would it be correct for you to answer `ja'?' twice. The two answers must mean the same thing, and both must mean the same as `ja', so one of them must in fact be `ja'.
[Edited to add solution]

User avatar
t1mm01994
Posts: 299
Joined: Mon Feb 15, 2010 7:16 pm UTC
Location: San Francisco.. Wait up, I'll tell you some tales!

Re: Some tricky logic puzzles.

Postby t1mm01994 » Sun Jan 22, 2012 5:13 pm UTC

@JR:

Spoiler:
Well, yeah, in that case it's just a matter of definition. I used the strictly symmetrical one, else a solution was given in another spoiler :)

User avatar
Gwydion
Posts: 336
Joined: Sat Jun 02, 2007 7:31 pm UTC
Location: Chicago, IL

Re: Some tricky logic puzzles.

Postby Gwydion » Sun Jan 22, 2012 6:16 pm UTC

jestingrabbit wrote:Of course, this depends on a particular interpretation of what an anti person is. If they put themselves in the shoes of the person they're related to, work out what their answer would be and then reverse it, then your argument is right. But, if they answer from their own shoes, as it were, and then it breaks down.

So, we kinda need a more clearly delineated notion of anti people.

I assumed the anti-people were capable of standing alone as individuals. In other words, even if there were no knights or knaves in the room, anti-knights and anti-knaves could give logically consistent answers to questions. The anti-knight will answer the opposite of whatever a knight would answer to a question - thus, will process the question as if he were a knight, then bit-flip the answer, as opposed to simply telling lies. If the anti-knight pretends he is "the knight standing next to me" rather than just "a knight", I figure there isn't much point to defining them as separate individuals. One could, then, restate this last problem in a more tricky way (not actually sure if this can be solved):

You are taken to a room with an anti-knight and an anti-knave (as defined above), they speak in a different language to you and they have 4 words: ja, da, ka, and la (two words each for yes and no). You get to ask two questions to one of them, and if they answer ja on one of the questions, you will be freed, if not, then you will be shot. By convention, two consecutive questions will never have the same answer.

sfwc
Posts: 225
Joined: Tue Mar 29, 2011 1:41 pm UTC

Re: Some tricky logic puzzles.

Postby sfwc » Sun Jan 22, 2012 10:14 pm UTC

Gwydion wrote:You are taken to a room with an anti-knight and an anti-knave (as defined above), they speak in a different language to you and they have 4 words: ja, da, ka, and la (two words each for yes and no). You get to ask two questions to one of them, and if they answer ja on one of the questions, you will be freed, if not, then you will be shot. By convention, two consecutive questions will never have the same answer.

How about this:
Spoiler:
Ask the following question twice: "If I asked the other three 'Is the grass green?', would there be more answers not meaning the same as `ja' than answers meaning the same as `ja'?"

tomtom2357
Posts: 563
Joined: Tue Jul 27, 2010 8:48 am UTC

Re: Some tricky logic puzzles.

Postby tomtom2357 » Mon Jan 23, 2012 3:05 am UTC

sfwc wrote:
Gwydion wrote:You are taken to a room with an anti-knight and an anti-knave (as defined above), they speak in a different language to you and they have 4 words: ja, da, ka, and la (two words each for yes and no). You get to ask two questions to one of them, and if they answer ja on one of the questions, you will be freed, if not, then you will be shot. By convention, two consecutive questions will never have the same answer.

How about this:
Spoiler:
Ask the following question twice: "If I asked the other three 'Is the grass green?', would there be more answers not meaning the same as `ja' than answers meaning the same as `ja'?"

Other three? There are only two people in the room other than you (in the above problem) so this question has no meaning. Also, there could be a question like this:
Spoiler:
If I asked the anti-knave Q, would they answer ja?
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.

User avatar
Gwydion
Posts: 336
Joined: Sat Jun 02, 2007 7:31 pm UTC
Location: Chicago, IL

Re: Some tricky logic puzzles.

Postby Gwydion » Mon Jan 23, 2012 6:43 am UTC

tomtom2357 wrote:Also, there could be a question like this:
Spoiler:
If I asked the anti-knave Q, would they answer ja?

Well, no.
Spoiler:
That question will be answered differently by the anti-knave and anti-knight. Since you don't know to whom you're speaking, you have a 50% chance of failing.
Spoiler:
I think the right answer is the same as the standard for these types of puzzles - asking "If I asked *you* P, would you say Ja?" where P is a true statement. I get very confused when trying to diagram the actual thinking, and am afraid I'm doing it wrong because it comes out right only about 66% of the time (n=3).


Return to “Logic Puzzles”

Who is online

Users browsing this forum: No registered users and 5 guests