The truthteller and the politician

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

liveboy21
Posts: 136
Joined: Thu Dec 01, 2011 9:33 am UTC

The truthteller and the politician

Postby liveboy21 » Fri Dec 28, 2012 12:22 pm UTC

Many of you would know of the puzzle where you meet a person who tells only truths and a person who tells only lies. You don't know which person has which trait. You then ask a question or a few questions, depending on who's asking the question, to find out which of two places is the correct place to go to.

The version I am proposing is that you meet at a fork in the road a truthteller and a politician, and you don't know which person is which. Unlike the liar above, the politician is not forced to lie at all times. The politician will selectively tell truth, lies and nonsense answers whenever he wishes in order to get you to go the wrong way. Presumably, if he gets you to take the wrong path, he gets to kill you off so that you don't tell the press about his half brothel half dildo producing child labour sweatshop.

Your job is to ask them as few questions as you can in order to find the right path. I've been slightly vague about the behaviour of the politician because I'm hoping that he'll become as smart as the smartest forum user. Good luck!

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

Re: The truthteller and the politician

Postby Gwydion » Fri Dec 28, 2012 3:21 pm UTC

I haven't spent too much time thinking this through, so there may be a tricky answer I've missed. However, I believe that this is unsolvable. Since the politician is not forced to answer by any particular metric, he is able to selectively tell the truth or lie to keep you from finding out whether he is the truth teller or the politician. Additionally, since he can answer "nonsense", his head can not be made to explode using paradoxes, nor can he be "tricked" into telling the truth using self-reference.

I look forward to someone smarter than me proving this wrong.

User avatar
dudiobugtron
Posts: 1098
Joined: Mon Jul 30, 2012 9:14 am UTC
Location: The Outlier

Re: The truthteller and the politician

Postby dudiobugtron » Fri Dec 28, 2012 7:35 pm UTC

I'm assuming that everything is common knowledge between the two - ie: both people know who is the politician and who is the truth teller, and which path is the correct one, and they know that those things are common knowledge etc...

Now, in some situations, the politician has to answer the same way as the truth teller would. For example, if you ask the politician "Are you the truth teller", he must answer yes, otherwise you'll know he's not.
But in other situations, he must answer the opposite of what the truth teller would. For example, if you ask "Is the left road the correct road?", and he answers the same way as the truth teller, then you'd know whether or not it was the correct road.

So, what we're looking for is a question where if the politician answers the same as the truth teller, then you'll know which road is correct, but if he answers differently, you'll know who the truthteller is.
Image

User avatar
Heptadecagon
Posts: 36
Joined: Mon May 28, 2012 7:11 pm UTC

Re: The truthteller and the politician

Postby Heptadecagon » Fri Dec 28, 2012 8:07 pm UTC

I think if the politician acts as the truth teller would if the correct and incorrect roads were switched, there's no possible way to be sure which is which.

User avatar
dudiobugtron
Posts: 1098
Joined: Mon Jul 30, 2012 9:14 am UTC
Location: The Outlier

Re: The truthteller and the politician

Postby dudiobugtron » Fri Dec 28, 2012 8:37 pm UTC

Heptadecagon wrote:I think if the politician acts as the truth teller would if the correct and incorrect roads were switched, there's no possible way to be sure which is which.

If the politician answers according to a particular metric, then you'll be able to catch him out by self-reference as Gwydion suggested. For example, if he always used the metric you describe, you could ask them 'What would the politician say if I asked him "Is the left road the correct road?"?'

Which brings me to another question - is the truthteller a perfect logician? Will s/he (I'll assume 'he', since otherwise it would be pretty easy to tell them apart...) always know how the politician would answer, if such knowledge is possible?
Image

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: The truthteller and the politician

Postby jestingrabbit » Fri Dec 28, 2012 8:47 pm UTC

Spoiler:
Ask one which way to go, and then "Is your answer to this question 'No'?" If their head explodes, go in the direction they indicated. Otherwise, go in the other direction.

You can't make the politicians head explode, but you can make the honest man's head explode.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

User avatar
Heptadecagon
Posts: 36
Joined: Mon May 28, 2012 7:11 pm UTC

Re: The truthteller and the politician

Postby Heptadecagon » Fri Dec 28, 2012 8:50 pm UTC

dudiobugtron wrote:example, if he always used the metric you describe, you could ask them 'What would the politician say if I asked him "Is the left road the correct road?"?'
If left was the correct road, the politician could say ''The politician would say left was the correct road.'' , wouldn't that work according to my rule?

edit: Well, as to the head exploding, what if the politician decides to explode his head if you ask him that question too? Maybe his life is worth messing you up for.

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: The truthteller and the politician

Postby jestingrabbit » Fri Dec 28, 2012 9:55 pm UTC

Heptadecagon wrote:edit: Well, as to the head exploding, what if the politician decides to explode his head if you ask him that question too? Maybe his life is worth messing you up for.


I guess its a question as to whether "head exploding" can only be a consequence of a question whose answer requires breaking the rules that a being is created with, or whether it can be a a chosen answer by a being without binding rules. I was assuming the former, rather than the latter.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

User avatar
dudiobugtron
Posts: 1098
Joined: Mon Jul 30, 2012 9:14 am UTC
Location: The Outlier

Re: The truthteller and the politician

Postby dudiobugtron » Fri Dec 28, 2012 10:14 pm UTC

The turth teller doesn't have to answer 'yes' or 'no', he just has to answer with the truth. He could respond to jestingrabbit's question by saying, "I can't give a yes/no answer to that question" - which would be the truth. Although then you have to allow that the truthteller might just reply "I don't want to answer that with a yes/no answer" to every question you ask...

Heptadecagon wrote:
dudiobugtron wrote:example, if he always used the metric you describe, you could ask them 'What would the politician say if I asked him "Is the left road the correct road?"?'
If left was the correct road, the politician could say ''The politician would say left was the correct road.'' , wouldn't that work according to my rule?

No, because the truth teller would say that the politician would say right is the correct road; so therefore the politician would have to say that as well according to your rule. Although I may have misunderstood your rule.

Although now that I think about it, maybe the solution is to amend your rule to be:
"I think if the politician acts as the truth teller would if the correct and incorrect roads were switched, and the truthteller and politician were switched, then there's no possible way to be sure which is which."

In that case, I'm not sure I can find a question to get around it.
Image

Chrysophylax
Posts: 4
Joined: Tue Apr 10, 2012 12:09 am UTC

Re: The truthteller and the politician

Postby Chrysophylax » Fri Dec 28, 2012 11:48 pm UTC

There's a simple answer to this problem. He's a politician. Bribe him.

Actually, this is discussed at some length in one of Martin Gardner's books (Mathematical Puzzles and Diversions). As I recall, the conclusion is that there is no solution.

User avatar
Heptadecagon
Posts: 36
Joined: Mon May 28, 2012 7:11 pm UTC

Re: The truthteller and the politician

Postby Heptadecagon » Sat Dec 29, 2012 1:17 am UTC

Although now that I think about it, maybe the solution is to amend your rule to be:
"I think if the politician acts as the truth teller would if the correct and incorrect roads were switched, and the truthteller and politician were switched, then there's no possible way to be sure which is which."

In that case, I'm not sure I can find a question to get around it.[/quote]
I didn't right that, but thought that it didn't need to be said; of course the politician pretends the roles were reversed.

joek
Posts: 95
Joined: Tue Apr 21, 2009 4:33 pm UTC

Re: The truthteller and the politician

Postby joek » Fri Jan 04, 2013 8:53 pm UTC

I think jestingrabbit has the right of it: the only possible way is to trap the truthteller into a paradox, as the politician can always answer consistently with how the truthteller would, except in the case of which road to go down... Although, thinking about it, the politician could fake being trapped in a paradox too. Unless the truthteller's head *literally* explodes when asked to answer paradoxical questions.

User avatar
dudiobugtron
Posts: 1098
Joined: Mon Jul 30, 2012 9:14 am UTC
Location: The Outlier

Re: The truthteller and the politician

Postby dudiobugtron » Fri Jan 04, 2013 10:57 pm UTC

It's a bit sad for the politician that the best possible result he can hope for is a 50% chance that you will take the wrong road, given that he is actively trying to get you to take it. And, in that case, you might as well not ask them any questions.
Image

Randomizer
Posts: 284
Joined: Fri Feb 25, 2011 8:23 am UTC
Location: My walls are full of hungry wolves.
Contact:

Re: The truthteller and the politician

Postby Randomizer » Sun Jan 06, 2013 11:16 am UTC

Well, you'd ask them questions so that, if you survive going down whichever road it is, you know who the truth teller and who the politician is next time you see one or both of them again.
Belial wrote:I'm all outraged out. Call me when the violent rebellion starts.

User avatar
Moonbeam
Posts: 292
Joined: Sat Dec 08, 2007 5:28 pm UTC
Location: UK

Re: The truthteller and the politician

Postby Moonbeam » Sun Jan 06, 2013 1:50 pm UTC

I'm not sure that this can be solved, but I'll wait and see :)

The politician can always answer in such a way that you won't know who's who.

For instance if you ask them, "is this the correct road to take?" the politician will always answer with the opposite to the truth teller.

If you ask them, "are you the truth teller?" the politician will always reply yes (the same as the truth teller).

If you ask them which way to go, and then "Is your answer to this question 'No'?" (as JR suggested), the truth teller does not have to reply yes or no. I'm assuming that he'll notice it's a paradox and will simply reply along the lines of, "this is a paradox and I cannot reply with yes or no". The politicain will reply in the same way and we're no nearer to finding their identities :(

gaga654
Posts: 12
Joined: Tue Mar 01, 2011 1:37 am UTC

Re: The truthteller and the politician

Postby gaga654 » Tue Jan 29, 2013 11:51 pm UTC

Chrysophylax wrote:There's a simple answer to this problem. He's a politician. Bribe him.

Actually, this is discussed at some length in one of Martin Gardner's books (Mathematical Puzzles and Diversions). As I recall, the conclusion is that there is no solution.

Yes, if I recall correctly the best solution he comes up with there is (and in that scenario here the correct road leads to a village): "Did you know they are giving out free beer in the village?" (This may have to be adapted for our scenario, but the basic idea is the same.)

bobleboffon3
Posts: 38
Joined: Fri Jul 16, 2010 7:35 am UTC

Re: The truthteller and the politician

Postby bobleboffon3 » Thu Jan 31, 2013 6:54 am UTC

The politician just have to 'act' like the truthteller would act if the roads were the other way around.
I think it's bulletproof.. there's nothing that would tell them apart.

If the truthteller says yes/no to a random question, the politician says yes/no to that question.
If the truthteller says yes/no to a question that will allow us to find the right road, the politician says no/yes, to lead us to the other road.
If the truthteller can't answer, the politician doesn't answer.
If the truthteller can't answer unless the right road is left, the politician only answer if the wrong road is left, and so on.

I think the only way for us to find out the truth in that situation is, if we have any knowledge about the truthteller, that the politician ignores.

This way, we could ask them questions that would lead us to the right road if the truthteller can answer, and the other road if he can't answer" The politician then wouldn't know if he can answer or not, so he'd guess, and we might be able to figure it out.

But then again, if we know anything personal about the truthteller, we can just ask those personnal questions right away and find out the truth.

so yeah, I think it's 100% impossible.

Xavion
Posts: 4
Joined: Wed Dec 09, 2009 10:14 pm UTC
Location: Victoria, Australia

Re: The truthteller and the politician

Postby Xavion » Thu Jan 31, 2013 5:05 pm UTC

It's obvious and has been shown that using only questions won't give you a solution for you or the politician, so obviously the only way to do it is to introduce another factor. I can't remember where I first saw this method but as far as I can see it is the only method to improve accuracy, threaten them, unless your knowledge is worth more than they are eventually one of them will change thier mind revealing who it is.

balr
Posts: 54
Joined: Mon Dec 07, 2009 5:29 pm UTC

Re: The truthteller and the politician

Postby balr » Fri Feb 01, 2013 12:20 pm UTC

Spoiler:
Do you want people to vote for you at the next election?


A truthteller would simply say no. A politician could say no, but they'd be committing career suicide, so they'd be left waffling in the wind.

Alternatively:
Spoiler:
Do you do a good job in representing your constituents?
Last edited by balr on Fri Feb 01, 2013 12:32 pm UTC, edited 2 times in total.

brenok
Needs Directions
Posts: 507
Joined: Mon Oct 17, 2011 5:35 pm UTC
Location: Brazil

Re: The truthteller and the politician

Postby brenok » Fri Feb 01, 2013 12:23 pm UTC

balr wrote:
Spoiler:
Do you want people to vote for you at the next election?


A truthteller would simply no. A politician could say no, but they'd be committing career suicide, so they'd be left waffling in the wind.

Alternatively:
Spoiler:
Do you do a good job in representing your constituents?


Spoiler:
Remember to add "I'm recording this and broadcasting in national network" and we're done.

Olejac
Posts: 1
Joined: Thu Jan 31, 2013 10:39 am UTC

Re: The truthteller and the politician

Postby Olejac » Fri Feb 01, 2013 1:48 pm UTC

Spoiler:
Ask one of them about the program of the politician's party. If he doesn't know the program of said party or can explain to you what said program is, you've found the truthsayer. If he gives you a nonsense answer, he's a politician. Now that you know which one is which, the rest should be obvious.

User avatar
Vytron
Posts: 429
Joined: Mon Oct 19, 2009 10:11 am UTC
Location: The Outside. I use She/He/Her/His/Him as gender neutral pronouns :P

Re: The truthteller and the politician

Postby Vytron » Fri Feb 01, 2013 2:54 pm UTC

Xavion wrote:the only method to improve accuracy, threaten them, unless your knowledge is worth more than they are eventually one of them will change thier mind revealing who it is.


I don't think this would work. Imagine that it works, and the truth teller tells you that he doesn't want to be threatened, and tells you that he's the truth teller and that the other one is the politician. Then he tells you that the right way is the correct one. You win.

However, the politician can do the same, and act as if he was the truth teller, and tell you the same thing, but that the way to the left is the correct one. You'd lose.

These cases are indistinguishable, so whenever that happens, you don't know if the politician jumped in first, or if he waited for the truth teller to reveal who they were. Your chances are 50% again.
Go! Go! You can do it username5243!
Cheers Marsh'n!

Image
THANKS KARHELL!! :)

bobleboffon3
Posts: 38
Joined: Fri Jul 16, 2010 7:35 am UTC

Re: The truthteller and the politician

Postby bobleboffon3 » Sat Feb 02, 2013 1:53 am UTC

Vytron wrote:
Xavion wrote:the only method to improve accuracy, threaten them, unless your knowledge is worth more than they are eventually one of them will change thier mind revealing who it is.


I don't think this would work. Imagine that it works, and the truth teller tells you that he doesn't want to be threatened, and tells you that he's the truth teller and that the other one is the politician. Then he tells you that the right way is the correct one. You win.

However, the politician can do the same, and act as if he was the truth teller, and tell you the same thing, but that the way to the left is the correct one. You'd lose.

These cases are indistinguishable, so whenever that happens, you don't know if the politician jumped in first, or if he waited for the truth teller to reveal who they were. Your chances are 50% again.


I think his point is to get the politician to lie.
Threatening the truthteller achieves nothing.

But threatening the politician ( or both of them ) until one of them lies would work.
Ask them both which road is the right one.
Then threaten them/torture them until one of them change his mind and says the other road is the right one.
You've now found the politician, and go with the other's answer.

But with questions only, and no additionnal information, it's not possible.

mward
Posts: 123
Joined: Wed Jun 22, 2011 12:48 pm UTC

Re: The truthteller and the politician

Postby mward » Sun Feb 03, 2013 12:14 pm UTC

Ask them which road to take. Then bribe them both to give the opposite answer. The one who takes the bribe is the politician.

User avatar
Vytron
Posts: 429
Joined: Mon Oct 19, 2009 10:11 am UTC
Location: The Outside. I use She/He/Her/His/Him as gender neutral pronouns :P

Re: The truthteller and the politician

Postby Vytron » Tue Feb 05, 2013 9:32 am UTC

bobleboffon3 wrote:Ask them both which road is the right one.
Then threaten them/torture them until one of them change his mind and says the other road is the right one.


I think the spirit of the puzzle is that the politician will do their best, whatever it takes, for you to take the wrong road.

No matter how much you torture him, if you go to the wrong path, he will be able to capture you and take his revenge, so imagine any kind of torture, and picture that you'd have to suffer it double if you pick the wrong road.

Then the politician will never tell the truth and will await his revenge, knowing that every lasting moment of pain will be suffered by you, when you pick the wrong road.

You can't threaten his life, because he knows killing him would get you nowhere (and you'd need to kill the truth-teller as well). In the end, if both never change their answer, you've wasted your time.

Of course, this assumes that whatever method you pick to decide on which road to take (like, flipping a coin) will lead you to the wrong road, as otherwise the puzzle loses its appeal: If there are two roads and one of them has an assassin/torturer after it waiting for you, the obvious solution is to avoid taking any of the roads.
Go! Go! You can do it username5243!
Cheers Marsh'n!

Image
THANKS KARHELL!! :)

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

Re: The truthteller and the politician

Postby Trebla » Tue Feb 05, 2013 2:20 pm UTC

Olejac wrote:
Spoiler:
Ask one of them about the program of the politician's party. If he doesn't know the program of said party or can explain to you what said program is, you've found the truthsayer. If he gives you a nonsense answer, he's a politician. Now that you know which one is which, the rest should be obvious.


This seems more likely to hurt you. If the truthteller does know, he's obligated to tell the truth, while the politician can attempt to deceive you into believing he knows nothing about it.

User avatar
Nylonathatep
NOT Nyarlathotep
Posts: 720
Joined: Tue Dec 20, 2011 3:06 am UTC

Re: The truthteller and the politician

Postby Nylonathatep » Fri Feb 22, 2013 10:41 pm UTC

Since you aren't limited to asking any amount of questions... the dumb solution is to just keep asking questions until the politican slip up and give a false answer.

The Truthteller will always tell the truth; the politican will eveuntually lie.

The smarter way is to go directly and ask about the politician's half brothel half dildo producing child labour sweatshop. The Truthteller will tell the truth, and the politican presumably would lie about it because he don't want the people to know about it.

MakingProgress
Posts: 17
Joined: Wed Jan 02, 2013 7:41 pm UTC

Re: The truthteller and the politician

Postby MakingProgress » Sat Feb 23, 2013 1:27 pm UTC

If the truthteller knows about the politicians sweatshop he is a much bigger threat to the politician than you will ever be.

Afrael
Posts: 36
Joined: Mon Sep 20, 2010 10:23 am UTC

Re: The truthteller and the politician

Postby Afrael » Sun Feb 24, 2013 10:03 am UTC

Okay, guys, I think I have found a solution which should work without the "as few questions as you can" clause, and on the presumption that the truthteller is omniscient.
Spoiler:
Ask both of them:

0) Is this puzzle solvable?
If both say no, that means that the truthteller told you it is not possible. Go sulk in a corner.
If exactly one of them says yes, that guy is the truthteller (proof comes later). Go to 4.
If both say yes, by now the truthteller told you that it is solvable. That's good news!

Then continue with the following:

1) Start asking the guy who told you "yes, this is solvable" questions about how many questions you'd have to ask to solve this puzzle in an optimal manner (since you only get yes/no answers, you'd have to use nested intervals). This sequence of questions will give you a number n. If at any point n<=(amount of questions you have asked so far), you already failed in the "optimal amount of questions" part of the task. But depending on the rules, you may still be able to continue. If you cannot continue, go sulk in a corner.
We will call the questions that solve the puzzle optimally "OSQ" (optimal solution questions). |OSQ| =: n.

2) Work out n of the questions you have to ask using meta-questions (ie "does the third word have three letters" etc). Note: I think you can also do this with working out n-1 questions, but I am not too sure how.

3) Check using you own sense of logic if the OSQ suggested to you makes sense.
a) If not, the person you have been asking (person1) is the politician. The other one (person2) is the truthteller. (Side note: Now you can show that in step 0, the situation "truthteller answers no while politician answers yes" can never occur because that would lead to a paradox with how we just found out who the truthteller is. So in step 0, if exactly one of them answers yes, you know that that guy is the truthteller). Now you know who the truthteller is. Skip to 4.
b) If yes, the person you have been asking might be either the truthteller or the politician. Then ask the other person (person2) if the OSQ is valid. If person2 says no, they are lying, since you have already established that OSQ is valid. Thus, person1 who gave you OSQ is the truthteller. Skip to 4.
If the person2 says yes, that means that by now, the truthteller has told you that OSQ is valid. In that case, go to 3c).
c) Use the questions from OSQ to find the solution. Go to 4 or 5, depending on what you find out with the OSQ.

4) Ask the truthteller if the left road is the correct one. (Regarding the note to 2. I think this would be a valid nth question for any OSQ. Proof by contraposition: a) If that question was not a valid element of OSQ, you would have found a shorter path to victory than the truthteller. His head would explode. b) If that question was among the first n-1 elements of OSQ, that would mean that.... I will leave this as an exercise to the reader. I think that would somehow mean that |OSQ|-1=|OSQ| or something.)

5) You win.

It becomes even more easier if the politician is not omniscient.

If they are not limited to boolean answers in their answer space, that also makes the whole task much easier.

...I have spent waaaaay too much time on this.

Edit: spoilered. Sorry.

User avatar
dudiobugtron
Posts: 1098
Joined: Mon Jul 30, 2012 9:14 am UTC
Location: The Outlier

Re: The truthteller and the politician

Postby dudiobugtron » Sun Feb 24, 2013 11:08 am UTC

Excellent idea for a question Afrael! Unfortunately I think that both will answer 'no' to your question, but it is still an awesome idea.

There is a problem with this part your proof however:

Afrael wrote:
Spoiler:
If exactly one of them says yes, that guy is the truthteller (proof comes later). Go to 4.

...
(Side note: Now you can show that in step 0, the situation "truthteller answers no while politician answers yes" can never occur because that would lead to a paradox with how we just found out who the truthteller is. So in step 0, if exactly one of them answers yes, you know that that guy is the truthteller).


My objection:
Spoiler:
It's not a paradox. We wouldn't necessarily know whether the puzzle is actually solvable, so we couldn't know that one of them is the truth teller.
If you get 1 yes, 1 no, then:
If we know it is unsolvable, we know that the truthteller said it isn't solvable, and that would be a contradiction. So therefore we don't know that isn't solvable.
Image

User avatar
jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: The truthteller and the politician

Postby jaap » Sun Feb 24, 2013 12:40 pm UTC

dudiobugtron wrote:My objection:
Spoiler:
It's not a paradox. We wouldn't necessarily know whether the puzzle is actually solvable, so we couldn't know that one of them is the truth teller.
If you get 1 yes, 1 no, then:
If we know it is unsolvable, we know that the truthteller said it isn't solvable, and that would be a contradiction. So therefore we don't know that isn't solvable.


I'm not entirely sure I understand your objection, but I think I agree.
Spoiler:
We know (from the problem statement in the OP) that there is one truthteller and one politician.
For Afrael's solution to work, we need two assumptions:
1. If there is a solution, the truthteller will know of it.
2. If you hear a solution, you will be able to recognise that it is one.

Whoever says yes to the question "Is there a solution?", you will be able to extract a solution from him using the method Afrael described. If that solution makes sense, then you know the puzzle is solvable due to the existence of a solution. Therefore the person who said no was the politician, and you were talking to the truthteller all along.
If that solution did not make sense, then the person you are talking to must have been the politician. The other person is the truthteller. You have found the solution, seemingly contradicting the fact that the truthteller said no.

This is not a real contradiction, because it may well be the case that there is no solution, i.e. finite sequence of questions that forces them to reveal enough information for you to deduce the correct road, but that the politician has revealed some information anyway.

In order to deduce that this situation does not occur, we need the extra assumption that the politician will never reveal any information leading to an answer, and knowledgeable enough to recognise that answering yes to your first question is such information.

Without that assumption, a yes/no situation means that you have to go through the process of extracting the solution anyway.

So if that assumption is true and that the politician will always say no, then the truthteller is in the curious position of being able to truthfully answer either yes or no to your first question. Maybe you should add a bribe when you ask that question so that at least one of them will answer yes...


Edit:
Spoiler:
But as soon as the truthteller answers yes, the politician could answer yes too, causing the truthteller to have told a lie...

Afrael
Posts: 36
Joined: Mon Sep 20, 2010 10:23 am UTC

Re: The truthteller and the politician

Postby Afrael » Sun Feb 24, 2013 1:25 pm UTC

jaap wrote:
Spoiler:
This is not a real contradiction, because it may well be the case that there is no solution, i.e. finite sequence of questions that forces them to reveal enough information for you to deduce the correct road, but that the politician has revealed some information anyway.

Okay, I get it. But i think this could be amended by changing the wording of the first question, for example as

Spoiler:
0) Does a finite sequence of questions exist such as that if I were to ask it and evaluate the answers, it would necessarily solve this puzzle?


Obviously you have to mind wording etc, lest you are talking to a malevolent truthteller.

User avatar
dudiobugtron
Posts: 1098
Joined: Mon Jul 30, 2012 9:14 am UTC
Location: The Outlier

Re: The truthteller and the politician

Postby dudiobugtron » Sun Feb 24, 2013 9:09 pm UTC

jaap wrote:
dudiobugtron wrote:My objection:
Spoiler:
It's not a paradox. We wouldn't necessarily know whether the puzzle is actually solvable, so we couldn't know that one of them is the truth teller.
If you get 1 yes, 1 no, then:
If we know it is unsolvable, we know that the truthteller said it isn't solvable, and that would be a contradiction. So therefore we don't know that isn't solvable.


I'm not entirely sure I understand your objection


My apologies, I didn't explain it very well. Here is a more detailed version:
Spoiler:
Imagine you ask the question "Does a finite sequence of questions exist such as that if I were to ask it and evaluate the answers, it would necessarily solve this puzzle?" and receive one 'yes' and one 'no' answer. There are two possible situations:
a) The answer is yes, so the truthteller answered yes, and the politician answered no.
b) The answer is no, so the truthteller answered no, and the politician answered yes.
You don't know whether the answer is yes or no, so you don't know which situation it is. There's no inherent contradiction in the truthteller answering 'no', since you still wouldn't know that it was the truthteller who had said that. You know that if you knew it was unsolvable, then that would be a contradiction (because you'd then know who was the truthteller by virtue of them claiming you couldn't know who the truthteller was, clearly a falsehood). So all that means is you know that you can never know for sure that it is unsolvable. But that's fine - since you can never try every possible finite sequence of questions, you're not going to run into a contradiction there either. Of course, if it is solvable through a finite sequence of questions, you 'can' eventually solve it by going through every possible finite sequence of questions. You'll never actually try them all, of course, but for any finite sequence, you'll eventually try it after a finite amount of time. Basically: If it is solvable, you can obviously solve it. But if it's not solvable, you'll never find out.
Image

User avatar
jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: The truthteller and the politician

Postby jaap » Sun Feb 24, 2013 9:47 pm UTC

dudiobugtron wrote:
Spoiler:
Imagine you ask the question "Does a finite sequence of questions exist such as that if I were to ask it and evaluate the answers, it would necessarily solve this puzzle?" and receive one 'yes' and one 'no' answer. There are two possible situations:
a) The answer is yes, so the truthteller answered yes, and the politician answered no.
b) The answer is no, so the truthteller answered no, and the politician answered yes.
[snip]
Basically: If it is solvable, you can obviously solve it. But if it's not solvable, you'll never find out.

Spoiler:
If the politician answered yes, then you will solve the puzzle.
Regardless of whether the puzzle is normally solvable, if the politician said yes, you can ask him a finite number of questions and get him to literally spell out the solution he claims exists in a manner much like Stephen Hawking's speech computer. Once you have that claimed solution, by examining it you can see whether it is valid or not. If the puzzle were unsolvable, that claimed solution will be invalid, and since the truthteller would never claim a false solution to be true, you can deduce that the person you got that solution from is the politician. If the claimed solution turns out to be valid, then you don't know which of them told you that valid solution, but in that case you can actually ask those questions in that solution and again find out who the politician is.

So once anyone says yes to that first question, the problem has become solvable, even if it wasn't before.

User avatar
dudiobugtron
Posts: 1098
Joined: Mon Jul 30, 2012 9:14 am UTC
Location: The Outlier

Re: The truthteller and the politician

Postby dudiobugtron » Mon Feb 25, 2013 12:23 am UTC

That's clever, and assuming omniscience of the truthteller, I agree with you.
Spoiler:
It's not possible for the truthteller to know a solution exists without knowing what the solution is, since he is omniscient. Therefore the politician can't pretend to not know the solution without giving away that he is the politician.


And in that case, it's now clear that:
Spoiler:
if there is a solution, then the politician cannot circumvent us finding out that solution, regardless of how he answers.


That doesn't really bring us any closer to finding out if there is a solution at all, though!
Image

User avatar
Vytron
Posts: 429
Joined: Mon Oct 19, 2009 10:11 am UTC
Location: The Outside. I use She/He/Her/His/Him as gender neutral pronouns :P

Re: The truthteller and the politician

Postby Vytron » Mon Feb 25, 2013 3:32 am UTC

I think this is a huge hole in the strategy:

Spoiler:
Afrael wrote:a) If not, the person you have been asking (person1) is the politician. The other one (person2) is the truthteller. (Side note: Now you can show that in step 0, the situation "truthteller answers no while politician answers yes" can never occur because that would lead to a paradox with how we just found out who the truthteller is. So in step 0, if exactly one of them answers yes, you know that that guy is the truthteller). Now you know who the truthteller is. Skip to 4.


(Emphasis mine)

I think that this leads to a contradiction. First, after getting at least one Yes, you assume the puzzle must be solvable, and that the politician said no. However, this makes the politician strategy's clear:

If the puzzle has no solution, he should say Yes, so you conclude as above that it's the truthteller, go to step 4 and pick the wrong road.

So the politician can rule out the "You get two noes and go sulk in the corner". Either The puzzle has no solution and you go the wrong road, or it does and you solve the puzzle.

HOWEVER, this allows the politician to also rule out the possibility of both saying yes: If the puzzle has a solution, the truthteller would say yes, the the politician would say no. In this scenario, though, you can still talk to the truth teller and find what's the solution, but you can never be sure if you're in this case where the puzzle has a solution, or if you're in the case where the politician told you there's a solution and will act as if there was one, he was the truthteller, and the wrong road was the right one.

You'd need to know if there was a solution a priory, but if you were omniscient you'd not need the truthteller in the first place.
Go! Go! You can do it username5243!
Cheers Marsh'n!

Image
THANKS KARHELL!! :)

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: The truthteller and the politician

Postby jestingrabbit » Mon Feb 25, 2013 3:43 am UTC

Vytron wrote:I think this is a huge hole in the strategy:

Spoiler:
Afrael wrote:a) If not, the person you have been asking (person1) is the politician. The other one (person2) is the truthteller. (Side note: Now you can show that in step 0, the situation "truthteller answers no while politician answers yes" can never occur because that would lead to a paradox with how we just found out who the truthteller is. So in step 0, if exactly one of them answers yes, you know that that guy is the truthteller). Now you know who the truthteller is. Skip to 4.


(Emphasis mine)

I think that this leads to a contradiction. First, after getting at least one Yes, you assume the puzzle must be solvable, and that the politician said no. However, this makes the politician strategy's clear:

If the puzzle has no solution, he should say Yes, so you conclude as above that it's the truthteller, go to step 4 and pick the wrong road.

So the politician can rule out the "You get two noes and go sulk in the corner". Either The puzzle has no solution and you go the wrong road, or it does and you solve the puzzle.

HOWEVER, this allows the politician to also rule out the possibility of both saying yes: If the puzzle has a solution, the truthteller would say yes, the the politician would say no. In this scenario, though, you can still talk to the truth teller and find what's the solution, but you can never be sure if you're in this case where the puzzle has a solution, or if you're in the case where the politician told you there's a solution and will act as if there was one, he was the truthteller, and the wrong road was the right one.

You'd need to know if there was a solution a priory, but if you were omniscient you'd not need the truthteller in the first place.


No, read this post by jaap.

forums.xkcd.com/viewtopic.php?f=3&t=99410#p3282140

Spoiler:
If the politician answers yes, then you can determine who is the liar and who the truthteller, and from there solve.


Still, I think the assumption that the truthteller is omniscient is less likely than a head exploding truthteller, but whatever...
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

User avatar
Vytron
Posts: 429
Joined: Mon Oct 19, 2009 10:11 am UTC
Location: The Outside. I use She/He/Her/His/Him as gender neutral pronouns :P

Re: The truthteller and the politician

Postby Vytron » Mon Feb 25, 2013 4:20 am UTC

Spoiler:
jestingrabbit wrote:No, read this post by jaap.


I did, and as I said, it pre-supposes that the puzzle has a solution and then finds it. Whatever method you use for it whenever you get "yes/no" to the question "Does the puzzle have a solution", could be for the puzzle having a solution and the truth teller telling you it, or it could be for the politician posing as the truth teller and giving you a method that leads you to the wrong road.

You say that if the truthteller said no, and the politician answered yes, then you'd be able to see that the politician's strategy never worked, ask the other person what's the right road, and go to it. But that would be a solution, and would make the truthteller a liar. This scenario is impossible.

You could say that this scenario being impossible forces the politician to say no, but in reality the politician can do whatever he pleases, including making the truthteller a liar.

If there is a solution, the strategy allows the truthteller to say yes, and the politician to say yes, and then you have all the time in the world to check which one of these solutions works, and pick the right road. But this presupposes the puzzle is solvable. If it isn't you don't know in what scenario you're in.

In conclusion: If you get a Yes and a No for the question: "Can I ask a series of questions that lead me to the right road?", you can't tell if the puzzle is unsolvable, or if it is solvable and the truthteller would tell you how, because the scenario where the politician answers yes and you know the other one is the truth teller and ask him the question and leave would make the truthteller a liar.

If this was possible the truthteller would have said yes initially, and you'd be able to proceed with the plan of asking him what was the solution, but this requires the puzzle to be solvable in the first place. We don't know if it is.

The truthteller can't answer no to the question because the politician can make the puzzle solvable, is this such a question that the truthteller can answer? Such as "Will I raise my hand the next minute?" (If truthteller answers yes you don't raise it. If he says no you raise it.)
Go! Go! You can do it username5243!
Cheers Marsh'n!

Image
THANKS KARHELL!! :)

User avatar
dudiobugtron
Posts: 1098
Joined: Mon Jul 30, 2012 9:14 am UTC
Location: The Outlier

Re: The truthteller and the politician

Postby dudiobugtron » Mon Feb 25, 2013 5:49 am UTC

Vytron wrote:The truthteller can't answer no to the question because the politician can make the puzzle solvable

I think this really gets at the crux of the issue; thanks for giving me something to think about!
Image

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

Re: The truthteller and the politician

Postby Trebla » Thu Feb 28, 2013 3:52 pm UTC

dudiobugtron wrote:
Vytron wrote:The truthteller can't answer no to the question because the politician can make the puzzle solvable

I think this really gets at the crux of the issue; thanks for giving me something to think about!


Corollary:
Spoiler:
The truthteller can't answer "yes" to the question because the politician can mimic the truthteller and make the puzzle unsolvable.


Return to “Logic Puzzles”

Who is online

Users browsing this forum: No registered users and 6 guests