Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[GendoIkari]

So my friends and I appear to have logically proved 2 contradictory statements to both be true. It's a weird paradox.

If you don't know, The Shipwreck Arcana is a great co-op game in the spirit of Hanabi. Each player has 2 hidden random number tiles, each which have a number from 1 to 7 on them. On your turn, you look at your 2 tiles and choose 1 to place in front of a card that's on the table.. the card has text which restricts what is allowed to be played there. For example, a card might say "if one of your tiles is larger than the other, play the larger tile here". So if you play a 4 there, then your partner knows that your other tile must be a 1, 2, or 3. The object is to guess what your partner's unplayed tile is.

So there's a card that says you can play a tile there if your tiles are 1 number apart. So if you play a 4, then your partner knows that your hidden number must be either a 3 or a 5. If you play a 1 there, then your partner knows for a fact that your other tile must be 2; nothing else would be legal.

In our game, someone played 2 on that card. So we knew he must either a 1 or a 3. But then another teammate pointed out that if he were holding 1 and 2 as his tiles, then he would have placed the 1 on that card rather than the 2, because by placing the 1 on that card, he would be giving us an easy guaranteed correct guess. Therefore, we knew he wasn't holding a 1. So we guessed 3 and were correct.

But then I pointed out that this same logic could be extended... we had just proved that if you have a 2 and a 3, then by placing the 2 there, you give your partner a guaranteed correct guess. Therefore, if your partner places a 3 there, you know he doesn't have a 2... because if he did have a 2 he would have placed the 2 instead of the 3. Therefore, he must have a 4. And now that you've proved that if he places a 3 there, then he must have a 4... you can use the exact same deductive reasoning to show that if he places a 4 there, then he must have a 5. And so-on.

BUT.... ignoring all that for a second, if someone places a 7 there, then the only legal option is that he must be holding a 6. So if you have a 6 and a 7, you would obviously place the 7 there, because it gives your partner a guaranteed correct guess. Therefore, if someone places a 6 there, you know they didn't have 6 and 7, because 7 would have been the obvious play....

So now there's the paradox. You can prove with seemingly solid logic that if someone plays a 4, then they must have had 4 and 5. But you can equally prove with the same logic that if someone plays a 4, then they must have had 3 and 4. Just depends on which end you start the deductive reasoning from.

[MiX]

I think the logical gap here is that if you have a 1 and a 2, you always place the 1 since it gives more information. In reality, it gives the same information: with any plan at all you can deduce what number a person is holding (say, always place the lower one). The 2 gives exactly as much information as the 1 if you think about it starting from the 7. What makes both of these statements true for 1 and 2 (and 6 and 7) is that the players are humans, and thus value easier deduction "a 1 was dropped so it's a 2" higher than the deduction chain starting from the 7. When you get to a higher chain of deduction, it's less and less true, until you get to the 4, where both are equally valid.

With perfect machines, the players would need to guess from which end the person that played the card was thinking from one end or the other. But humans would always think from the closest end, and you can use this shared knowledge as information.

[silverspawn]

So now there's the paradox. You can prove with seemingly solid logic that if someone plays a 4, then they must have had 4 and 5.

So, the reason why this is not a paradox is that you didn't prove the bolded part. You've proved that, if your partner adheres to a particular decision rule, then the bolded part follows. And then, you've noticed that (a) this rule leads to optimal play if both parties know that it's followed, and (b), there seems to be a different rule that also leads to optimal play if it's followed.

Both of those things are true, but they're not a contradiction. You can have many rules that are optimal.

To be specific, there are six possible pairs of numbers you can have (left), and each one allows for two different plays (right)

(1,2) -> {1,2}
(2,3) -> {2,3}
(3,4) -> {3,4}
(4,5) -> {4,5}
(5,6) -> {5,6}
(6,7) -> {6,7}

A decision rule is any choice of one of the two numbers from the right sets for each pair on the left. (I.e., (1,2) -> 2, (2,3) -> 2, (3,4) -> 4 and so on is one rule.) If you want to follow a fixed decision rule such that your partner is always able to guess your card, there are two prerequisites:

(1) your rule must not choose any number for more than one pair (otherwise, your partner cannot identify your pair if that number is chosen)
(2) your partner must know what rule you are following.

One possible rule is:

(1,2) -> 2
(2,3) -> 3
(3,4) -> 4
(4,5) -> 5
(5,6) -> 6
(6,7) -> 7

This is the one you arrive at by 'forward induction', which was your first argument. Another possible rule is the one you arrive at if you apply the argument backward, i.e.,


(1,2) -> 1
(2,3) -> 2
(3,4) -> 3
(4,5) -> 4
(5,6) -> 5
(6,7) -> 6

But there are other rules as well. In total, there are 64 rules you can follow, and seven of them meet the first criterion, which means they can be optimal if your partner knows you're implementing them. (Take the sequence (1,2,3,4,5,6,7), delete any one number, make those six numbers your choices for the six pairs, in order; the resulting rule meets the fist criterion.) All of those seven rules are equally valid, and for each one, you can prove that they lead to optimal play, provided your partner knows which one you're following.

[silverspawn]

Oh, and in particular, the step "if my partner had (1,2) they would have put 1" sounds intuitive but doesn't work formally -- if your partner follows the (2,3,4,5,6,7) rule, then they put 2 at (1,2), and since this is optimal, you can hardly argue that it's wrong.

[Jack Rudd]

So the question then becomes one of identifying the optimal optimal rule. Suppose you have a partner who believes you will play according to one of the optimal rules, but has no idea which one: which of the seven optimal rules should you choose to maximize your chances? Well, let's see: going from the start, there are 5 rules that map (2,3) onto 2, 1 that maps (1,2) onto 2, and 1 that doesn't map anything onto 2, so if you play 2, your partner should guess 3. Doing that rule for every output, you end up with the following being the optimal optimal rule:

(1, 2) -> 1
(2, 3) -> 2
(3, 4) -> 3
(4, 5) -> 5
(5, 6) -> 6
(6, 7) -> 7

[Awaclus]

So the question then becomes one of identifying the optimal optimal rule. Suppose you have a partner who believes you will play according to one of the optimal rules, but has no idea which one: which of the seven optimal rules should you choose to maximize your chances? Well, let's see: going from the start, there are 5 rules that map (2,3) onto 2, 1 that maps (1,2) onto 2, and 1 that doesn't map anything onto 2, so if you play 2, your partner should guess 3. Doing that rule for every output, you end up with the following being the optimal optimal rule:

(1, 2) -> 1
(2, 3) -> 2
(3, 4) -> 3
(4, 5) -> 5
(5, 6) -> 6
(6, 7) -> 7

"You just simply never play the middle one" also seems like the most intuitive optimal rule. If the cards range from 1 to 3, it's immediately obvious that's the one you follow.

[GendoIkari]

I think the logical gap here is that if you have a 1 and a 2, you always place the 1 since it gives more information. In reality, it gives the same information: with any plan at all you can deduce what number a person is holding (say, always place the lower one). The 2 gives exactly as much information as the 1 if you think about it starting from the 7.

This isn’t quite right, because in the case where someone places a 1, then there is no strategy or questioning what the optimal play would have been; the person who played it can only legally be holding a 2. Playing a 2 is different because both 1 and 3 are legal options, it’s just that one of the options means that the person made a suboptimal play.

[GendoIkari]

Oh, and in particular, the step "if my partner had (1,2) they would have put 1" sounds intuitive but doesn't work formally -- if your partner follows the (2,3,4,5,6,7) rule, then they put 2 at (1,2), and since this is optimal, you can hardly argue that it's wrong.

I think similar to the fist reply, this ignores the specialness of playing a 1 (or a 7). If you are allowed to play a 1 there, then no matter what possible agreement or understanding or convention you may have, there is never a reason not to play the 1 there... because no matter what other things might be true or might be able to be proved, if you play a 1 there then every one knows beyond a doubt that you are holding a 2, as it’s the only legal play. So there is no downside at all to breaking the rule in that case; even if you had all agreed that you would always play the higher number on that card.

[GendoIkari]

So the question then becomes one of identifying the optimal optimal rule. Suppose you have a partner who believes you will play according to one of the optimal rules, but has no idea which one: which of the seven optimal rules should you choose to maximize your chances? Well, let's see: going from the start, there are 5 rules that map (2,3) onto 2, 1 that maps (1,2) onto 2, and 1 that doesn't map anything onto 2, so if you play 2, your partner should guess 3. Doing that rule for every output, you end up with the following being the optimal optimal rule:

(1, 2) -> 1
(2, 3) -> 2
(3, 4) -> 3
(4, 5) -> 5
(5, 6) -> 6
(6, 7) -> 7

"You just simply never play the middle one" also seems like the most intuitive optimal rule. If the cards range from 1 to 3, it's immediately obvious that's the one you follow.

Indeed, it seems clear that in the version where you have only 1 to 3, playing a 2 there is always the wrong move, because your other option would have been an automatic correct guess no matter which tile the other options was.

[MiX]

I think the logical gap here is that if you have a 1 and a 2, you always place the 1 since it gives more information. In reality, it gives the same information: with any plan at all you can deduce what number a person is holding (say, always place the lower one). The 2 gives exactly as much information as the 1 if you think about it starting from the 7.

This isn’t quite right, because in the case where someone places a 1, then there is no strategy or questioning what the optimal play would have been; the person who played it can only legally be holding a 2. Playing a 2 is different because both 1 and 3 are legal options, it’s just that one of the options means that the person made a suboptimal play.

That's only true if you consider the logic "starting from the 7 and going all the way down to 2" (as you described it in the OP) less strong than "a 1 was placed so it has to be a 2". In reality, they are not: they're both deterministic, so they're the same strength. One is just more simple than the other.

silverspawn explained it better than I possibly could, but basically all optimal rules are equal, and so you cannot distinguish them like that. What you're basically doing by choosing to put down a 1 instead of a 2 when you have both, is go by the simplest thing the other players will think about, because that is a perfectly normal thing for humans to do. But without that, putting either down is equivalent, if you don't have one of those 7 rules already pre-established (in practice, the "pre-established" rule is the one that omits the 4, as that's what makes the most sense for humans).

[silverspawn]

Oh, and in particular, the step "if my partner had (1,2) they would have put 1" sounds intuitive but doesn't work formally -- if your partner follows the (2,3,4,5,6,7) rule, then they put 2 at (1,2), and since this is optimal, you can hardly argue that it's wrong.

I think similar to the fist reply, this ignores the specialness of playing a 1 (or a 7). If you are allowed to play a 1 there, then no matter what possible agreement or understanding or convention you may have, there is never a reason not to play the 1 there... because no matter what other things might be true or might be able to be proved, if you play a 1 there then every one knows beyond a doubt that you are holding a 2, as it’s the only legal play. So there is no downside at all to breaking the rule in that case; even if you had all agreed that you would always play the higher number on that card.

The mathematical translation of what you're saying is that any rule can be changed by setting (1, 2) -> 1 and (6, 7) -> 7 regardless of what it was before and this cannot break injectivity. Which is true, but so what?

The correct (but unhelpful) answer to 'look at this paradox' is always 'try to translate it into a formal statement. You'll inevitably see that there is no contradiction'. In this case, it's true that the rule can be broken in those two cases and this wouldn't degrade performance in that instance, but this doesn't give you an inductive argument anymore.

[spineflu]

this is just a two-way hangman paradox

[silverspawn]

this is just a two-way hangman paradox

I would dispute that. In the case of this game, the induction is arbitrary, it's just 'if the player follows this rule', but the player doesn't need to follow that rule. In the hangman non-paradox, the premise that seems to allow the induction is explicitly part of the problem description.

In particular, the resolution for both is different.

[GendoIkari]

this is just a two-way hangman paradox

Yeah, I actually brought up the unexpected hanging paradox when talking about this with my friends last night. It seemed like a similar idea.

[blueblimp]

If you can agree ahead of time on a convention, then there are multiple conventions that can work, as silverspawn points out.

If you can't agree ahead of time on a convention but expect that your partner is going to play according to a convention, then you're trying to find a Schelling point: you and your partner want to choose the same convention, despite not being able to communicate. I don't know much about these, but they seem more about psychology than about logic or math. Jack Rudd's convention (of playing towards the edges) seems like a reasonable choice because it's the only symmetric convention. (Note: The reasoning in your original post resembles the level-n theory described in the Wikipedia article.)

If your partner doesn't play according to a convention (which is not an effective way to play, but maybe they're bad at the game), then there's probably not much you can do.

[Dylan32]

Reading the OP reminded me of an old joke.

There was a man who had been convicted of a terrible crime. At his sentencing, the judge made two stipulations regarding his impending execution: It would be carried out sometime the next calendar week, and that the day it is carried out would be a surprise for the man.

The man sat in his cell that evening waiting for the week to begin, and his thoughts turned to guessing how much time he had left in this world.  Suddenly, he realized that it was quite impossible for him to be executed on the next Saturday, because if he reached the final day of the week then it would not be a surprise at all.  But if Saturday was impossible, then Friday likewise would not fulfill both of the judges stipulations, because he would hardly be surprised.  Likewise, he reasoned, Thursday would also not be possible, since surviving till then would assure him that Thursday was the day, thus removing the surprise.  And so his reasoning continued, and as he crossed off each day, his mood fell more and more realizing his time was short indeed.  However, upon realizing that his execution must occur on Sunday but that this fact meant he would not be surprised, he realized it would be impossible for his sentence to be carried out in accordance to the judge's ruling, and as such he could not be executed at all.  With that thought, the man went to sleep in high spirits.

The executioner came for him on Tuesday, and he was surprised.

[silverspawn]

Reading the OP reminded me of an old joke.

[...]

This is the

hangman paradox

[Dylan32]

I guess that's why it reminded me of it then.

[GendoIkari]

Somewhat off topic, but while trying to figure out this particular problem, I thought of a solution to the Unexpected Hanging Paradox that was different, or at least explained differently, than any I had heard before... the issue lies in this part:

“he realized it would be impossible for his sentence to be carried out in accordance to the judge's ruling, and as such he could not be executed at all.”

If he realized that the judge's ruling could not be carried out exactly, then it does not naturally follow that he could not be executed at all... there are 2 ways in which the judge's ruling could have been incorrect. One, that he isn’t executed at all. Or two, that he will be able to predict the execution day ahead of time. He assumed that the judge was wrong in the first way, rather than considering the possibility that he was wrong in the second way instead.

So he should have instead thought:

“he realized it would be impossible for his sentence to be carried out in accordance to the judge's ruling, and as such he might be able to predict the day of his execution ahead of time after all”.

Had he concluded that instead, then everything would have followed just fine. If he still wasn’t executed by Thursday night, he would have thought “tomorrow I will find out whether the judge was wrong about me being executed this week, or whether he was wrong about the day being unpredictable. Either way he was wrong.”

[MiX]

But if the judge's ruling is impossible to be carried out, the prisoner cannot predict when the execution is coming: there is no more information. Thus it will be a surprise.

[silverspawn]

I don't think you need that, so I'll just say what I think is a perfect resolution.

The inductive argument would be correct if the prisoner was guaranteed not to know the day. But in fact, they're only very likely not to know the day. Say the week goes from Monday to Sunday. If it's Saturday, the prisoner can suspect that the hanging is probably not tomorrow because then the judge would have lied, but he doesn't know for sure. Same logic on Friday and so on. A tiny chance for the prisoner not to be surprised is all it takes. And that sounds very convincing because now you can correctly say

The executioner came for him on Tuesday, and he was surprised.

But if you have that nonzero probability for non-surprise, there is no contradiction.

For example, the judge may choose a distribution like this:

0.01% Sunday
0.1% Saturday
1% Friday
10% Thursday
rest equally on Monday-Wednesday

With this, the prisoner will almost certainly be surprised, but the hanging can still happen on Tuesday.

Formally, if you fix any algorithm that implements the judge, it has to implement some probability distribution. Whatever that distribution looks like, there is a latest day that has nonzero probability mass. In the event that this day is reached, the prisoner knows that the hanging is on that day and will not be surprised.

I've recently seen this puzzle advertised as showing a limitation of logic, which I found fairly annoying. It's the same kind of thing as saying 'one drop plus one drop of water gives one drop, but math says 1+1=2, so that's a limitation of math'.

[GendoIkari]

But if the judge's ruling is impossible to be carried out, the prisoner cannot predict when the execution is coming: there is no more information. Thus it will be a surprise.

It’s not so much that it’s impossible, it’s more the acknowledgment that the judge could potentially be mistaken. If you allow for the possibility that the judge is mistaken, then there is no contradiction in a last-day execution.

[GendoIkari]

Right, I think your explanation is mostly the same as what I was trying to say; but I made the mistake of referring to the judge’s decree as being “impossible” when I meant to say that it was determined that the judge could potentially be wrong.

[pubby]

The hangman paradox is just confusion about when the prisoner's guess happens.

The first induction step assumes the prisoner is allowed to change his mind day-by-day. But if you allow that, the problem falls apart. Each day the prisoner could say, "I'm expecting to be executed today", and would eventually be right (and not surprised about it).

This can be fixed by redefining the problem as, "each day the prisoner will guess and will always be wrong about it". If you do this, the induction logic works correctly and the prisoner can't be executed. But it's not a useful statement for the judge to make.

But most people understand the judge's sentence meaning, "the prisoner will guess once in advance without 100% accuracy".

[infangthief]

Agreed.
If the judge means "at the time of this sentencing you don't know which day the hanging will be", then there is no contradiction; the hanging could be any day.
If the judge means "each evening you won't know if it'll be tomorrow or not", then logically that is the same as saying "it won't be Friday, it won't be Thursday, it won't be Wednesday, etc", which, taken alongside the statement "it'll be sometime next week", amounts to a sentence equivalent to "you will be hanged; you won't be hanged".

Here's another paradox, similar to the hangman one, but with a flavour similar to the one in the OP:
Logicians A and B each choose a number, which they tell C in secret. C then tells them "each of you has chosen a different positive integer, but neither of you knows which of you chose the smaller number".