The Tower and the Towns Puzzle

[pdurrant]

It's been interesting seeing the discussion of this puzzle. I'll try to post the answer and the reasons for it sometime tomorrow. Hopefully in a way that everyone can follow and agree with. GeoffC's questions have been very helpful in that regard, although I don't think I have him convinced quite yet.

[GeoffC]

Spoiler:

Night 1

X+Y = 13 or 10.

East sees X, therefore he knows West must be seeing (13-X) or (10-X). If X ≠ 13 then no one is freed and X ≠ 0.
West sees Y, therefore he knows that East must be seeing (13-Y) or (10-Y). If Y ≠ 13 then no one is freed and Y ≠ 0.
No one is released, therefore X ≠ 13, Y ≠ 13, nor 0.

Night 2

Neither X nor Y = 0 1 2 11 12 13
East sees X, therefore he knows West must be seeing (13-X) or (10-X).
West sees Y, therefore he knows East must be seeing (13-Y) or (10-Y).
If neither X nor Y = 10 neither can be certain.
No one is released, therefore X ≠ 10, Y ≠ 10, nor 3.

Night 3.

East sees X, knowing West sees (13-X) or (10-X).
West sees Y, knowing East sees (13-Y) or (10-Y).
If neither X nor Y = 11 neither can be certain of what the other sees.
No one is released, therefore X ≠ 9, Y ≠ 9, nor 4.

Night 4.

East sees X, knowing West sees (13-X) or (10-X).
West sees Y, knowing East sees (13-Y) or (10-Y).
If neither X nor Y = 10 neither can be certain of what the other sees.
No one is released, therefore X ≠ 8, Y ≠ 8, nor 5.

Night 5.
Only 6 & 7 remain = 13

[GeoffC]

I bow before those who are, obviously cleverer than I .....

I think .....

[pdurrant]

Originally Posted by GeoffC

Spoiler:

Night 1

X+Y = 13 or 10.

East sees X, therefore he knows West must be seeing (13-X) or (10-X). If X ≠ 13 then no one is freed and X ≠ 0.
West sees Y, therefore he knows that East must be seeing (13-Y) or (10-Y). If Y ≠ 13 then no one is freed and Y ≠ 0.
No one is released, therefore X ≠ 13, Y ≠ 13, nor 0.

Night 2

Neither X nor Y = 0 1 2 11 12 13
East sees X, therefore he knows West must be seeing (13-X) or (10-X).
West sees Y, therefore he knows East must be seeing (13-Y) or (10-Y).
If neither X nor Y = 10 neither can be certain.
No one is released, therefore X ≠ 10, Y ≠ 10, nor 3.

Night 3.

East sees X, knowing West sees (13-X) or (10-X).
West sees Y, knowing East sees (13-Y) or (10-Y).
If neither X nor Y = 11 neither can be certain of what the other sees.
No one is released, therefore X ≠ 9, Y ≠ 9, nor 4.

Night 4.

East sees X, knowing West sees (13-X) or (10-X).
West sees Y, knowing East sees (13-Y) or (10-Y).
If neither X nor Y = 10 neither can be certain of what the other sees.
No one is released, therefore X ≠ 8, Y ≠ 8, nor 5.

Night 5.
Only 6 & 7 remain = 13

Sorry, you have the right answer, but your reasoning seems to be incorrect.

Spoiler:

After Night 1, and if the wise men still prisoners, you seem to be saying that it is not possible for X or Y to be 0. It is. Consider X=10 and Y=0. Neither can give a certain answer on the first night, but Y=0.

But I think you're beginning to see the way to the solution.

[GeoffC]

Originally Posted by pdurrant

Sorry, you have the right answer, but your reasoning seems to be incorrect.

Spoiler:

After Night 1, and if the wise men still prisoners, you seem to be saying that it is not possible for X or Y to be 0. It is. Consider X=10 and Y=0. Neither can give a certain answer on the first night, but Y=0.

But I think you're beginning to see the way to the solution.

I beg to differ ....

Spoiler:

Yes I have ....

No one is released, therefore X ≠ 13, Y ≠ 13, nor 0.

[pdurrant]

Originally Posted by GeoffC

I beg to differ ....

Spoiler:

Yes I have ....

No one is released, therefore X ≠ 13, Y ≠ 13, nor 0.

Ah, I see where you coming from, but

Spoiler:

you're making the assumption that the number of towns is 13. There might be 10 towns, in which case the fact that neither sees 13 towns says nothing about whether either sees 0 towns.

[pdurrant]

Answers time!


Q1. How did the wise men know how many towns there were in the small kingdom?
A1:

Spoiler:

They didn't guess. On the fifth evening they both knew how many towns were in the Kingdom.

There are several ways to think about the solution to this problem. Here's one of the easiest. We think about what we could know if we were one of the wise men and saw a certain number of towns, and thereby what the other wise man could know if he saw that number of towns.

1st Day: There can only be 10 or 13 towns in the kingdom. If I could see 11, 12 or 13 towns, I would know that there were 13 towns. Similarly, if my friend could see 11, 12 or 13 towns, he would know that there were 13 towns.

1st Evening: I can't see 11, 12 or 13 towns, but if my friend can, we'll be free this evening.

2nd Day: Well, we're not free, so neither my friend nor I can see more than 10 towns, and he knows that too. Now, if I could see only 0, 1 or 2 towns, the most towns that we could jointly see would be 12 (since I know he can't see more than 10). Since there are only 10 or 13 towns, this would mean that there are 10 towns. Similarly, if my friend can only see 0, 1 or 2 towns, he would know that there are only 10 towns.

2nd Evening: I see more than 2 towns, but if my friend doesn't see more than 2 towns, he'll know there are 10 towns and we'll be free this evening.

3rd Day: Well, we're still not free, so neither my friend nor I can see fewer than 3 towns nor more than 10 towns, and my friend knows that too.
Now, if I could 8 or more towns, the fewest towns we could jointly see would be 11 (since I know that he sees 3 or more). Since there are only 10 or 13 towns, this would mean that there are 13 towns. Similarly, if my friend can see 8 or more towns, he would know that there are 13 towns.

3rd Evening: I can see fewer than 8 towns, but if my friend can see 8 or more towns, he'll know that there are 13 towns, ans we'll be free this evening.

4th Day: Well, were still not free, so neither my friend nor I can see fewer than 3 towns nor more than 7 towns, and my friend knows that too. Now, if I could see only 5 or fewer towns, the most towns we could see jointly would be 12 (since I know that he sees 7 or fewer). Since there are only 10 or 13 towns, that would mean there must be 10 towns. Similarly, if my friend can see only 5 or fewer towns, he would know that there are 10 towns.

4th Evening: I can see more than 5 towns, but if my friend doesn't see more than 5 towns, he'll know that there are 10 towns and we'll be free this evening.

5th Day: Well, we're still here, so neither my friend nor I can see fewer than 6 towns nor more than 7 towns. Since I can see 7 towns, that means my friend must see 6 towns, and there must be 13 towns in all.

5th Evening: I tell the Gaoler that that there are 13 towns in the kindgom, and my friend and I go free.

Q2. How many towns were there in the small kingdom?
A2:

Spoiler:

There are 13 towns in the small kingdom.

Supplementary Explanation. If you're happy with the above answer, there's no need to read this. But if you're still puzzled, it might help.

Spoiler:

Some people have wondered what possible information the two wise men get on the first night that makes any difference to their situation. I think this is best explained by taking a simpler case than the actual answer to the question above — a situation in which the wise men get released on the third day.

If the the wise man in the Eastern room ("E") could see 10 towns and the wise man in the Westen room ("W") could see 3 towns, they would each know that the other could not tell how many towns there were in the kingdom. This being the case, still being in prison after the first night would not be a surprise, and would give them no information about how many towns the other person could see. With no extra information about how many towns the other person can see, some people argue, they would be unable to do anything differently on subsequent nights.

Let me elaborate on the perceived problem first, and then show how they do gain information that helps them, even though neither gains any information on the first night about how many towns the other wise man can see.

E sees 10 towns. So E knows that W must see 0 or 3 towns.
W sees 3 towns. So W knows that E must see 7 or 10 towns.

Each can immediately see that the other wise man must see 10 or fewer towns, and so knows that the other wise man can't deduce how many towns there are. Neither expects to be free the first evening. The next day, each still knows that the other can't see more than 10 towns. Indeed, E still only knows that W must see 0 or 3 towns, and W still only knows that E must see 7 or 10 towns.

So what information do they gain on the first night that eventually allows them to escape?

The answer is that each gains information about what the other wise man might think about what the first wise man could see. Let us look more closely at what each knows on the first day.

E sees 10 towns. So E knows that W must see 0 or 3 towns. So E knows that W might think that E sees 10 or 13 towns (if W sees 0 towns) or 7 or 10 towns (if W sees 3 towns).

W sees 3 towns. So W knows that E must see 7 or 10 towns. So W knows that E might think that W sees 0 or 3 towns (if E sees 10 towns) or 3 or 6 towns (if E sees 7 towns).

On the second day, E now knows that W can no longer think that E can see 13 cities. E's knowledge has changed. W's knowledge has not. Their knowledge on the 2nd Day is as follows:

E sees 10 towns. So E knows that W must see 0 or 3 towns. But now E knows that W could only think that E sees 10 towns (if W sees 0 towns) or 7 or 10 towns (if W sees 3 towns).

W sees 3 towns. So W knows that E must see 7 or 10 towns. So W still knows that E could think that W sees 0 or 3 towns (if E sees 10 towns) or 3 or 6 towns (if E sees 7 towns).

What deductions can E make with this new knowledge that he has? He can now reason like this:

Suppose W sees 0 towns. Then he must think that I see 10 — he can no longer think that I see 13. So if W does see 0, he now knows that there are only 10 towns and we'll be released tonight.

The knowledge that E gains is that W can no longer thinks that E might have seen 13 towns. This new knowledge gives E an expectation that he might be released on the 2nd night, even though he had no such expectation on the 1st night.

This is a genuine piece of knowledge that E gains on the first night. On the first day he knows that W might think that E has 13 towns. On the second day he knows that this can not be so.

Of course, W doesn't (in this example) see 0 towns, and so they're still stuck in the tower when dawn comes on the third day.

E now has another piece of new information, not about what W might thinks E can see, but directly about what W can see. He now knows that W doesn't see 0 towns, as if W did see 0 towns, they would have been free last night. So E now knows that W sees 3 towns, and that there are 13 towns altogether. They are freed on the third evening.



Working through what information the wise men get on the first evening when one sees 6 and the other sees 7 towns is complex, but works in the same way. One gains information about what the other thinks the first thinks that the other thinks about what the first can see. Or something like that. English isn't the best language to describe it in!

You might be reminded of the Escape from Prison Puzzle. And it is similar. In both puzzles, the information given seems to be information that the people involved already have. The extra information given is that the information is now Common Knowledge. Every participants now know that the other participants know the information, and that all the participants know that all the other participants know the information, etc.

[Sparrow]

Originally Posted by pdurrant

Two wise men (who really were wise, and knew each other well) were captured by the king of a small kingdom and brought in secret to a lonely tower in the middle of his kingdom, arriving early one morning.

Must be quite a tall tower to see so many towns, or perhaps it's on top of a mountain.

[pdurrant]

Originally Posted by Sparrow

Must be quite a tall tower to see so many towns, or perhaps it's on top of a mountain.

A tall tower and a small kingdom. But how many towns are there? 10 or 13?

[Sparrow]

10 - there's not enough room in a small kingdom for 13 q.e.d.

[GeoffC]

Perhaps it's a lego town ....

[pdurrant]

I've just posted a new puzzle: https://www.mobileread.com/forums/sho....php?p=1004867