Quote:
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...