The Tower and the Towns Puzzle

[Sparrow]

Originally Posted by dreams

I love how this one has everyone jumping in. pdurrant, these puzzles are great!
I may have to wait for some time to try this one out, but it looks to be fun.
Congrats to all those who were able to figure this one out so quick.

Great puzzle! I got nowhere trying to figure it out, so kudos to those who did - an ingenious solution!!

[GeoffC]

but is it a solution that satisfies logic ?

[Sparrow]

Originally Posted by GeoffC

but is it a solution that satisfies logic ?

I think so.

Spoiler:

Say the king had said there was either 1 or 3 towns in his kingdom.
You'd either know straightaway (seeing 3 towns yourself).
Or you would know on the second night. Your partner not having declared 3 towns the previous night.

Bigger numbers just complicates it a bit I reckon.

[GeoffC]

What I cannot get is this 'extra' bit of information is for each night onwards.
They are both still alive; there are no other new scraps of data.

Surely they must have been executed 4 times by the 5th night ????

[LazyScot]

Originally Posted by GeoffC

What I cannot get is this 'extra' bit of information is for each night onwards.
They are both still alive; there are no other new scraps of data.

Surely they must have been executed 4 times by the 5th night ????

If they don't know, they don't have to answer: that keeps them alive, but imprisoned.

[pdurrant]

Originally Posted by GeoffC

What I cannot get is this 'extra' bit of information is for each night onwards.
They are both still alive; there are no other new scraps of data.

Surely they must have been executed 4 times by the 5th night ????

Spoiler:

The extra information is that the other wise man didn't know the answer either. This puts limits the number of towns that the other wise man could be seeing. So each night you get more information about what the other wise man can (or rather can't) see.

[GeoffC]

Originally Posted by LazyScot

If they don't know, they don't have to answer: that keeps them alive, but imprisoned.

Infinitum .....

Originally Posted by pdurrant

Spoiler:

The extra information is that the other wise man didn't know the answer either. This puts limits the number of towns that the other wise man could be seeing. So each night you get more information about what the other wise man can (or rather can't) see.

[GeoffC]

Originally Posted by Sparrow

I think so.

Spoiler:

Say the king had said there was either 1 or 3 towns in his kingdom.
You'd either know straightaway (seeing 3 towns yourself).
Or you would know on the second night. Your partner not having declared 3 towns the previous night.

Bigger numbers just complicates it a bit I reckon.

Spoiler:

What happens if both can see 1 ..... neither knows what the other sees.

[omk3]

Originally Posted by GeoffC

Spoiler:

What happens if both can see 1 ..... neither knows what the other sees.

Spoiler:

But the key information is that they know it is either 1 or 3, never 2. So both seeing 1 is not possible. They would never be free if they didn't know the towns are either 10 or 13. But this information changes everything.

[Sparrow]

Originally Posted by GeoffC

Spoiler:

What happens if both can see 1 ..... neither knows what the other sees.

Spoiler:

So neither gives an answer on the first day - but they both know they haven't been released or executed; therefore their partner didn't answer either.
The only way to answer correctly on the first day is if either saw 2 or 3 towns, in which case there are 3 towns - as no answer was given, they know neither of them saw 2 or 3 towns.
So they now know each saw either 0, or 1.
But both can't see 1, because they're told the answer isn't 2.
Hence 1 is the correct answer to give on day 2.

[GeoffC]

Originally Posted by omk3

Spoiler:

But the key information is that they know it is either 1 or 3, never 2. So both seeing 1 is not possible. They would never be free if they didn't know the towns are either 10 or 13. But this information changes everything.

this post was specifically directed at Sparrow's scenario.

Spoiler:

East sees 1 town, but doesn't know whether West sees 0 or 2.

West sees 0 towns, but doesn't know whether East sees 1 or 3.
West knows that if East sees 3 he would have used the get out of jail card.
West holds all the clues and can answer 1.

It works for the small number scenario, but when the numbers increase

[Sparrow]

Originally Posted by GeoffC

this post was specifically directed at Sparrow's scenario.

Spoiler:

It is possible that both CAN see 1, that provides a hint that the total is 3, but it is only a hint.
Neither knows what the other can see, nor can they pass the information between them.

(West: I can see 1, now my esteemed friend can either see 0 [therefore there is only 1], or he can see 2 [thus 3 in total] - now - how can I tell him what I can see ...... and get us out of this predicament)

(East: I can see 1 town .... mmmmm that means there are 3 towns in total, or only 1....I wonder what my esteemed friend can see......)

Spoiler:

(West: I can see 1, now my esteemed friend can either see 0 [therefore there is only 1], or he can see 2 [thus 3 in total] - now - how can I tell him what I can see ...... and get us out of this predicament)

If you're partner sees 2 that eliminates 1 as a possible answer - he's only left with 3.

[omk3]

Originally Posted by GeoffC

this post was specifically directed at Sparrow's scenario.

Spoiler:

It is possible that both CAN see 1, that provides a hint that the total is 3, but it is only a hint.
Neither knows what the other can see, nor can they pass the information between them.

(West: I can see 1, now my esteemed friend can either see 0 [therefore there is only 1], or he can see 2 [thus 3 in total] - now - how can I tell him what I can see ...... and get us out of this predicament)

(East: I can see 1 town .... mmmmm that means there are 3 towns in total, or only 1....I wonder what my esteemed friend can see......)

Spoiler:

I know, that's why I said the answer is either 1 or 3. It is not possible for both of them to see one town, because then the answer would be 2.
If one sees 0, he doesn't know what the other sees, so he waits.
If he sees 1, he waits. The other should see either 0 or 2 (never 1). If the other saw 2, they'd be free on the first day. If they aren't , then he must see 0, so they'll be free on the second day, saying it's 1 town only.
If he sees 2, or 3, he obviously knows the answer is 3 straight away.

[GeoffC]

At this rate I shall out-logic my logic ....

It works for the 1 - 3 scenario .... but ..... !

[LazyScot]

Originally Posted by GeoffC

At this rate I shall out-logic my logic ....

It works for the 1 - 3 scenario .... but ..... !

Spoiler:

Let's try a sort of proof by induction....

If we know it works for 1 - 3, what happens if we apply the same logic to 2 - 4?

Just as with 1 - 3 there are a small number of case that can be answered on the first night, in this case if either can see 3 or 4. Same as with 1 - 3 where the could answer if one saw 2 or 3.

Problem now is on the second night. So what do we know the wise men must be seeing? Neither can be seeing 3 or 4, so we can only have the men seeing 0 and 2, or 1 and 1 or 2 and 2. So if either can see 0 or 1, they know the answer must be 2.

So we come to the third night, when the wise men must both be seeing 2, so they can safely answer 4.

Now lets try the next case up 3 to 5, but try to generalise the answer. On the first night, if either wise man sees more than the lower number of possible towns, they can answer safely that it must be the upper number of towns.

On the second night, if either wise man sees less than the difference between the number of towns (in this case 0 or 1 as they are less than 3 -5), they can safely answer that it must be the lower number of towns, since they know that the other wise man cannot be seeing more than the lower number of towns (or that wise man would have had them released the previous night).

At this point each wise man knows that the other must be seeing a number of towns between upper-lower and lower towns (in this case 2 or 3).

On the third night, for this case, they can answer 5, but in the general case, if either wise man saw between lower and (lower - (upper - lower)), they can answer it must be the upper town count.

For the general case, if they are still present on forth night, they know the range must be reduced to (upper-lower) and (lower - (upper - lower)).

This process carries on, with the possibility of an answer alternating between the upper and lower number of towns and the range of possible towns each wise man can see, and still be imprisoned (because any other number would have allowed one or other man to have them released) is reduced, until there are no possibilities left.

(Hmmmm... this was more complicated explanation that I'd hope [Sorry, Geoff] -- I may (as an exercise to myself) go away and see if a cleaner generalised inductive proof-style answer can be generated.)

As I understand it, this sort of "communication" has been used in certain areas of human endeavour to sneek information through systems. And it's not been spotted by the brightest minds...