Towers, Courtyard, and trees

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

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

Towers, Courtyard, and trees

Postby Trebla » Wed Dec 07, 2011 3:06 pm UTC

Search didn't turn this riddle up, but it may be here in a different form (mice and cheese instead of towers and trees, for instance) so I apologize if it's a duplicate.

Two perfect logicians, Al and Bob, are traveling in a foreign land when they are arrested for crimes against humanity. They are, of course, innocent, so had not prepared for such an arrest and had made no plans ahead of time. They are immediately separated and placed in towers with no means of direct communication (aka, they cannot see, hear, feel, etc etc) each other. Each prisoner can see a courtyard, and they are both told that the courtyard contains either 18 or 20 trees. Further, between the two of them, all trees are visible, yet no tree is visible to both of them. On the first day of their captivity, Al is asked how many trees are in the courtyard. If he answers correctly, both prisoners are released; if he answers incorrectly, both prisoners are executed; if he chooses not to answer, he's left in his cell and Bob is asked the same question with the same choices. If Bob chooses not to answer, the process repeats on the next day and the next and so on until one prisoner answers.

Both prisoners have all information up to this point including the order they're asked.

Al can see 12 trees. Bob can see 8 trees.

How long will it be before one of them correctly answers with 100% certainty that there are 20 trees? Which one answers? How did they arrive at their conclusion?

User avatar
AvatarIII
Posts: 2098
Joined: Fri Apr 08, 2011 12:28 pm UTC
Location: W.Sussex, UK

Re: Towers, Courtyard, and trees

Postby AvatarIII » Wed Dec 07, 2011 3:27 pm UTC

I have absolutely no idea, as far as I can tell there is no way for Bob to ever know whether al can see 10 or 12 trees, nor for Al to know if Bob can see 6 or 8, with no way to communicate.

I look forward to seeing a solution to this.

User avatar
benneh
Posts: 74
Joined: Tue Aug 26, 2008 8:24 am UTC

Re: Towers, Courtyard, and trees

Postby benneh » Wed Dec 07, 2011 3:28 pm UTC

This is really just blue-eyes in disguise, I think.

Spoiler:
Day 1:
If Al can see more than 18 trees, he knows there must be 20 trees in total and both are released. Otherwise, both prisoners know Al can see at most 18 trees.
If Bob can see fewer than 2 trees, he knows there must be 18 trees in total and both are released. Otherwise, both prisoners know Bob can see at least 2 trees.

Day 2:
If Al can see more than 16 trees, he knows there must be 20 trees in total and both are released. Otherwise, both prisoners know Al can see at most 16 trees.
If Bob can see fewer than 4 trees, he knows there must be 18 trees in total and both are released. Otherwise, both prisoners know Bob can see at least 4 trees.

Etc.
In general, on day n:
If Al can see more than 20-2n trees, he knows there must be 20 trees in total and both are released. Otherwise, both prisoners know Al can see at most 20-2n trees.
If Bob can see fewer than 2n trees, he knows there must be 18 trees in total and both are released. Otherwise, both prisoners know Bob can see at least 2n trees.

In this situation, Al works out that there are 20 trees on day 5 and both prisoners are released.

User avatar
AvatarIII
Posts: 2098
Joined: Fri Apr 08, 2011 12:28 pm UTC
Location: W.Sussex, UK

Re: Towers, Courtyard, and trees

Postby AvatarIII » Wed Dec 07, 2011 3:33 pm UTC

benneh wrote:This is really just blue-eyes in disguise, I think.

Spoiler:
Day 1:
If Al can see more than 18 trees, he knows there must be 20 trees in total and both are released. Otherwise, both prisoners know Al can see at most 18 trees.
If Bob can see fewer than 2 trees, he knows there must be 18 trees in total and both are released. Otherwise, both prisoners know Bob can see at least 2 trees.

Day 2:
If Al can see more than 16 trees, he knows there must be 20 trees in total and both are released. Otherwise, both prisoners know Al can see at most 16 trees.
If Bob can see fewer than 4 trees, he knows there must be 18 trees in total and both are released. Otherwise, both prisoners know Bob can see at least 4 trees.

Etc.
In general, on day n:
If Al can see more than 20-2n trees, he knows there must be 20 trees in total and both are released. Otherwise, both prisoners know Al can see at most 20-2n trees.
If Bob can see fewer than 2n trees, he knows there must be 18 trees in total and both are released. Otherwise, both prisoners know Bob can see at least 2n trees.

In this situation, Al works out that there are 20 trees on day 5 and both prisoners are released.


but.... why? As far as I can tell, no information is changing each day, why would what day it was have any bearing on ability to deduce number of trees?

User avatar
benneh
Posts: 74
Joined: Tue Aug 26, 2008 8:24 am UTC

Re: Towers, Courtyard, and trees

Postby benneh » Wed Dec 07, 2011 3:39 pm UTC

AvatarIII wrote:
benneh wrote:This is really just blue-eyes in disguise, I think.

Spoiler:
Day 1:
If Al can see more than 18 trees, he knows there must be 20 trees in total and both are released. Otherwise, both prisoners know Al can see at most 18 trees.
If Bob can see fewer than 2 trees, he knows there must be 18 trees in total and both are released. Otherwise, both prisoners know Bob can see at least 2 trees.

Day 2:
If Al can see more than 16 trees, he knows there must be 20 trees in total and both are released. Otherwise, both prisoners know Al can see at most 16 trees.
If Bob can see fewer than 4 trees, he knows there must be 18 trees in total and both are released. Otherwise, both prisoners know Bob can see at least 4 trees.

Etc.
In general, on day n:
If Al can see more than 20-2n trees, he knows there must be 20 trees in total and both are released. Otherwise, both prisoners know Al can see at most 20-2n trees.
If Bob can see fewer than 2n trees, he knows there must be 18 trees in total and both are released. Otherwise, both prisoners know Bob can see at least 2n trees.

In this situation, Al works out that there are 20 trees on day 5 and both prisoners are released.


but.... why? As far as I can tell, no information is changing each day, why would what day it was have any bearing on ability to deduce number of trees?


Spoiler:
On day 1, Al can do one of two things:
Either he sees more than 18 trees, and therefore concludes that there must be 20 trees in total.
Or he sees at most 18 trees, and concludes nothing.
The relevant point here is that if the second scenario comes to pass then Bob knows that Al couldn't have seen more than 18 trees, otherwise they would both have been released. So Bob has gained some information - that Al can see at most 18 trees. This process continues, with each prisoner gradually tightening the bounds on the possible number of trees the other can see, until one of them can deduce how many trees there are in total.

User avatar
AvatarIII
Posts: 2098
Joined: Fri Apr 08, 2011 12:28 pm UTC
Location: W.Sussex, UK

Re: Towers, Courtyard, and trees

Postby AvatarIII » Wed Dec 07, 2011 3:58 pm UTC

benneh wrote:
AvatarIII wrote:
benneh wrote:This is really just blue-eyes in disguise, I think.

Spoiler:
Day 1:
If Al can see more than 18 trees, he knows there must be 20 trees in total and both are released. Otherwise, both prisoners know Al can see at most 18 trees.
If Bob can see fewer than 2 trees, he knows there must be 18 trees in total and both are released. Otherwise, both prisoners know Bob can see at least 2 trees.

Day 2:
If Al can see more than 16 trees, he knows there must be 20 trees in total and both are released. Otherwise, both prisoners know Al can see at most 16 trees.
If Bob can see fewer than 4 trees, he knows there must be 18 trees in total and both are released. Otherwise, both prisoners know Bob can see at least 4 trees.

Etc.
In general, on day n:
If Al can see more than 20-2n trees, he knows there must be 20 trees in total and both are released. Otherwise, both prisoners know Al can see at most 20-2n trees.
If Bob can see fewer than 2n trees, he knows there must be 18 trees in total and both are released. Otherwise, both prisoners know Bob can see at least 2n trees.

In this situation, Al works out that there are 20 trees on day 5 and both prisoners are released.


but.... why? As far as I can tell, no information is changing each day, why would what day it was have any bearing on ability to deduce number of trees?


Spoiler:
On day 1, Al can do one of two things:
Either he sees more than 18 trees, and therefore concludes that there must be 20 trees in total.
Or he sees at most 18 trees, and concludes nothing.
The relevant point here is that if the second scenario comes to pass then Bob knows that Al couldn't have seen more than 18 trees, otherwise they would both have been released. So Bob has gained some information - that Al can see at most 18 trees. This process continues, with each prisoner gradually tightening the bounds on the possible number of trees the other can see, until one of them can deduce how many trees there are in total.


Spoiler:
but since Bob can see 8 trees, he knows for a fact that Al can see either 10 or 12 trees, so Bob already knew that Al can see less than 18 trees,
if Al could see 18 and bob could see none or 2 trees, it would make sense, because Bob would know, after Al chose not to guess, that Al must be able to see 18, but I don't see how that it follows each day.
perhaps if the question was "Is there at most 18 trees, or at least 20?" the solution would work, but not with "Is there exactly 18 or exactly 20?"


edit: i think i sussed it.
Spoiler:
i understand now, however your original solution is wrong, since Al knows the most that Bob thinks he can see is 14, Al would know that if he he actually did have 14, Bob would require to see 6 or 4, but Al knows that 4 is impossible, so Bob must see 6, so on day 2, Bob sees 6, Al would have 14 or 12, but Bob actually see 8, meaning Al can't have 14, Al then knows that Bob can't have 6, and therefore must have 8, therefore al should be able to solve it on day 3, not day 5.

User avatar
rigwarl
Posts: 759
Joined: Wed Dec 09, 2009 9:36 pm UTC

Re: Towers, Courtyard, and trees

Postby rigwarl » Wed Dec 07, 2011 6:44 pm UTC

Spoiler:
Benneh's solution is correct I believe. Avatar, no offense but your last post is almost entirely incomprehensible to me- on what day does "since Al knows the most that Bob thinks he can see is 14" apply?
Last edited by rigwarl on Wed Dec 07, 2011 7:35 pm UTC, edited 3 times in total.

User avatar
imatrendytotebag
Posts: 152
Joined: Thu Nov 29, 2007 1:16 am UTC

Re: Towers, Courtyard, and trees

Postby imatrendytotebag » Wed Dec 07, 2011 6:54 pm UTC

AvatarIII wrote:
benneh wrote:
AvatarIII wrote:
benneh wrote:This is really just blue-eyes in disguise, I think.

Spoiler:
Day 1:
If Al can see more than 18 trees, he knows there must be 20 trees in total and both are released. Otherwise, both prisoners know Al can see at most 18 trees.
If Bob can see fewer than 2 trees, he knows there must be 18 trees in total and both are released. Otherwise, both prisoners know Bob can see at least 2 trees.

Day 2:
If Al can see more than 16 trees, he knows there must be 20 trees in total and both are released. Otherwise, both prisoners know Al can see at most 16 trees.
If Bob can see fewer than 4 trees, he knows there must be 18 trees in total and both are released. Otherwise, both prisoners know Bob can see at least 4 trees.

Etc.
In general, on day n:
If Al can see more than 20-2n trees, he knows there must be 20 trees in total and both are released. Otherwise, both prisoners know Al can see at most 20-2n trees.
If Bob can see fewer than 2n trees, he knows there must be 18 trees in total and both are released. Otherwise, both prisoners know Bob can see at least 2n trees.

In this situation, Al works out that there are 20 trees on day 5 and both prisoners are released.


but.... why? As far as I can tell, no information is changing each day, why would what day it was have any bearing on ability to deduce number of trees?


Spoiler:
On day 1, Al can do one of two things:
Either he sees more than 18 trees, and therefore concludes that there must be 20 trees in total.
Or he sees at most 18 trees, and concludes nothing.
The relevant point here is that if the second scenario comes to pass then Bob knows that Al couldn't have seen more than 18 trees, otherwise they would both have been released. So Bob has gained some information - that Al can see at most 18 trees. This process continues, with each prisoner gradually tightening the bounds on the possible number of trees the other can see, until one of them can deduce how many trees there are in total.


Spoiler:
but since Bob can see 8 trees, he knows for a fact that Al can see either 10 or 12 trees, so Bob already knew that Al can see less than 18 trees,
if Al could see 18 and bob could see none or 2 trees, it would make sense, because Bob would know, after Al chose not to guess, that Al must be able to see 18, but I don't see how that it follows each day.
perhaps if the question was "Is there at most 18 trees, or at least 20?" the solution would work, but not with "Is there exactly 18 or exactly 20?"


edit: i think i sussed it.
Spoiler:
i understand now, however your original solution is wrong, since Al knows the most that Bob thinks he can see is 14, Al would know that if he he actually did have 14, Bob would require to see 6 or 4, but Al knows that 4 is impossible, so Bob must see 6, so on day 2, Bob sees 6, Al would have 14 or 12, but Bob actually see 8, meaning Al can't have 14, Al then knows that Bob can't have 6, and therefore must have 8, therefore al should be able to solve it on day 3, not day 5.


Spoiler:
It might be easier to think of this problem from the perspective of a third prisoner who cannot see any trees, and only hears the responses of Al and Bob. Let's call him Chris.

If Al gives no answer on day 1, Chris knows Al does not see 20 or 19 trees. So if Bob saw 0 or 1 tree he would be able to deduce that there were only 18 trees, thus if Bob gives no answer, Chris knows that Al does not see 20 or 19 trees, and Bob does not see 0,1,19, or 20 trees. Proceeding in this fashion, Chris will be able to narrow down the number of trees each person can see. But since Al and Bob are perfect logicians, they know what Chris knows, and make the same deductions, until they can actually use the number of trees they see to solve the problem.
Last edited by imatrendytotebag on Tue Dec 13, 2011 9:21 am UTC, edited 1 time in total.
Hey baby, I'm proving love at nth sight by induction and you're my base case.

User avatar
AvatarIII
Posts: 2098
Joined: Fri Apr 08, 2011 12:28 pm UTC
Location: W.Sussex, UK

Re: Towers, Courtyard, and trees

Postby AvatarIII » Wed Dec 07, 2011 6:55 pm UTC

rigwarl wrote:
Spoiler:
Benneh's solution is correct I believe. Avatar, no offense but your last post is almost entirely incomprehensible to me- on what day does "since Al knows the most that Bob thinks he can see is 14" apply?

Spoiler:
Because Al has 12, which means Al knows that Bob has either 8 or 6, if Bob has 6, he will know Al has 12 or 14

User avatar
rigwarl
Posts: 759
Joined: Wed Dec 09, 2009 9:36 pm UTC

Re: Towers, Courtyard, and trees

Postby rigwarl » Wed Dec 07, 2011 7:01 pm UTC

How does "if Bob has 6" matter at all (in that context)? He doesn't, he has 8, so he knows Al has either 10 or 12. This information isn't particularly useful for him though.

douglasm
Posts: 630
Joined: Mon Apr 21, 2008 4:53 am UTC

Re: Towers, Courtyard, and trees

Postby douglasm » Wed Dec 07, 2011 7:12 pm UTC

AvatarIII wrote:
Spoiler:
i understand now, however your original solution is wrong, since Al knows the most that Bob thinks he can see is 14, Al would know that if he he actually did have 14, Bob would require to see 6 or 4, but Al knows that 4 is impossible, so Bob must see 6, so on day 2, Bob sees 6, Al would have 14 or 12, but Bob actually see 8, meaning Al can't have 14, Al then knows that Bob can't have 6, and therefore must have 8, therefore al should be able to solve it on day 3, not day 5.

You're assuming that Al and Bob have more shared knowledge than they actually do. A few times in your chain of reasoning, you state something that one person knows and then assume the other person also knows it without justification.

benneh is completely correct. For a great many variations of detailed in depth explanations of why this kind of thing works (along with a lot of people being confused and not understanding it), see the blue eyes thread.

User avatar
AvatarIII
Posts: 2098
Joined: Fri Apr 08, 2011 12:28 pm UTC
Location: W.Sussex, UK

Re: Towers, Courtyard, and trees

Postby AvatarIII » Wed Dec 07, 2011 7:22 pm UTC

rigwarl wrote:How does "if Bob has 6" matter at all (in that context)? He doesn't, he has 8, so he knows Al has either 10 or 12. This information isn't particularly useful for him though.

Because Al doesn't know that Bob has 8, so Al has to assume that Bob might have 6, which means Al also has to assume that Bob might think that Al has at most 14.

User avatar
rigwarl
Posts: 759
Joined: Wed Dec 09, 2009 9:36 pm UTC

Re: Towers, Courtyard, and trees

Postby rigwarl » Wed Dec 07, 2011 7:36 pm UTC

Douglasm summed it up, but perhaps it might help you imagine what would happen if Bob actually did have 6? What day do they go free on?

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

Re: Towers, Courtyard, and trees

Postby Trebla » Wed Dec 07, 2011 8:15 pm UTC

benneh wrote:This is really just blue-eyes in disguise, I think.


Yes, very similar to Blue Eyes... I considered putting that in a spoiler'd hint tag, but that seemed like way too much of a hint. Very eloquent explanation of the solution.

rigwarl wrote:Douglasm summed it up, but perhaps it might help you imagine what would happen if Bob actually did have 6? What day do they go free on?


Spoiler:
If Bob saw 6 (and Al still saw 12), he would correctly guess on evening of the 4th day. As he would know that Al couldn't possibly see 14 trees by this day.

User avatar
AvatarIII
Posts: 2098
Joined: Fri Apr 08, 2011 12:28 pm UTC
Location: W.Sussex, UK

Re: Towers, Courtyard, and trees

Postby AvatarIII » Wed Dec 07, 2011 8:48 pm UTC

rigwarl wrote:Douglasm summed it up, but perhaps it might help you imagine what would happen if Bob actually did have 6? What day do they go free on?

Hmm, good point. What day would they actually be freed if bob had 6?

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: Towers, Courtyard, and trees

Postby jestingrabbit » Wed Dec 07, 2011 11:49 pm UTC

benneh wrote:This is really just blue-eyes in disguise, I think.

Spoiler:
Day 1:
If Al can see more than 18 trees, he knows there must be 20 trees in total and both are released. Otherwise, both prisoners know Al can see at most 18 trees.
If Bob can see fewer than 2 trees, he knows there must be 18 trees in total and both are released. Otherwise, both prisoners know Bob can see at least 2 trees.

Day 2:
If Al can see more than 16 trees, he knows there must be 20 trees in total and both are released. Otherwise, both prisoners know Al can see at most 16 trees.
If Bob can see fewer than 4 trees, he knows there must be 18 trees in total and both are released. Otherwise, both prisoners know Bob can see at least 4 trees.

Etc.
In general, on day n:
If Al can see more than 20-2n trees, he knows there must be 20 trees in total and both are released. Otherwise, both prisoners know Al can see at most 20-2n trees.
If Bob can see fewer than 2n trees, he knows there must be 18 trees in total and both are released. Otherwise, both prisoners know Bob can see at least 2n trees.

In this situation, Al works out that there are 20 trees on day 5 and both prisoners are released.


Just a small addendum here.

Spoiler:
When Bob responds as he does on the first day, he is certainly saying that he sees at least 2 trees, but he is also saying that he sees no more than 18, and there's a similar chain of inference to draw from later declarations (or lack thereof). Doesn't change the outcome for the starting values given, but its worth noting imo.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

User avatar
benneh
Posts: 74
Joined: Tue Aug 26, 2008 8:24 am UTC

Re: Towers, Courtyard, and trees

Postby benneh » Thu Dec 08, 2011 11:49 am UTC

jestingrabbit wrote:
benneh wrote:This is really just blue-eyes in disguise, I think.

Spoiler:
Day 1:
If Al can see more than 18 trees, he knows there must be 20 trees in total and both are released. Otherwise, both prisoners know Al can see at most 18 trees.
If Bob can see fewer than 2 trees, he knows there must be 18 trees in total and both are released. Otherwise, both prisoners know Bob can see at least 2 trees.

Day 2:
If Al can see more than 16 trees, he knows there must be 20 trees in total and both are released. Otherwise, both prisoners know Al can see at most 16 trees.
If Bob can see fewer than 4 trees, he knows there must be 18 trees in total and both are released. Otherwise, both prisoners know Bob can see at least 4 trees.

Etc.
In general, on day n:
If Al can see more than 20-2n trees, he knows there must be 20 trees in total and both are released. Otherwise, both prisoners know Al can see at most 20-2n trees.
If Bob can see fewer than 2n trees, he knows there must be 18 trees in total and both are released. Otherwise, both prisoners know Bob can see at least 2n trees.

In this situation, Al works out that there are 20 trees on day 5 and both prisoners are released.


Just a small addendum here.

Spoiler:
When Bob responds as he does on the first day, he is certainly saying that he sees at least 2 trees, but he is also saying that he sees no more than 18, and there's a similar chain of inference to draw from later declarations (or lack thereof). Doesn't change the outcome for the starting values given, but its worth noting imo.


Good point. Adding that in, we get

Spoiler:
Day n:
If Al sees A < 2n-2 trees, he deduces that there are 18 trees. If he sees 20-2n < A trees, he deduces that there are 20 trees. If he sees 2n-2 <= A <= 20-2n trees, both prisoners know Al can see this many trees.
If Bob sees B < 2n trees, he deduces that there are 18 trees. If he sees 20-2n < B trees, he deduces that there are 20 trees. If he sees 2n <= B <= 20-2n trees, both prisoners know Bob can see this many trees.

ekaprits
Posts: 1
Joined: Mon Sep 02, 2013 1:34 pm UTC

Re: Towers, Courtyard, and trees

Postby ekaprits » Mon Sep 02, 2013 1:38 pm UTC

I used to think that the above solution was the correct one for this riddle. A friend of mine disagrees, and I'm not so sure any more. I post his solution here. Can someone spot any problems with it? My (somewhat informal) reaction to it is that it assumes that
Spoiler:
certain facts are common knowledge, when they are not.


Here is the solution:
Spoiler:
At the initial state, A knows that B sees 6 or 8 trees. He also knows that B knows that A sees 10,12, or 14 trees. Similarly, B knows that A sees 10 or 12 trees, and he knows that A knows that B sees 6, 8, or 10 trees. Therefore, the common knowledge is A:10,12,14, B:6,8,10.

By not answering on the first day, A informs B that A knows that B knows that A sees either 10 or 12 trees (if he saw 14, he would have answered "20", since they both know that B has 6-10 trees). So the common knowledge is down to A:10,12, B:6,8,10. By not answering on his turn on the first day, B informs A that he doesn't see 6 trees (otherwise he would be certain that there are 18 trees), and that he doesn't see 10 trees (otherwise he would be certain that there are 20 trees). Therefore A will answer "20" on the 2nd day, since he now knows that B has 8 trees.

Xias
Posts: 363
Joined: Mon Jul 23, 2007 3:08 am UTC
Location: California
Contact:

Re: Towers, Courtyard, and trees

Postby Xias » Sat Sep 07, 2013 7:47 pm UTC

ekaprits wrote:I used to think that the above solution was the correct one for this riddle. A friend of mine disagrees, and I'm not so sure any more. I post his solution here. Can someone spot any problems with it? My (somewhat informal) reaction to it is that it assumes that
Spoiler:
certain facts are common knowledge, when they are not.


Here is the solution:
Spoiler:
At the initial state, A knows that B sees 6 or 8 trees. He also knows that B knows that A sees 10,12, or 14 trees. Similarly, B knows that A sees 10 or 12 trees, and he knows that A knows that B sees 6, 8, or 10 trees. Therefore, the common knowledge is A:10,12,14, B:6,8,10.

By not answering on the first day, A informs B that A knows that B knows that A sees either 10 or 12 trees (if he saw 14, he would have answered "20", since they both know that B has 6-10 trees). So the common knowledge is down to A:10,12, B:6,8,10. By not answering on his turn on the first day, B informs A that he doesn't see 6 trees (otherwise he would be certain that there are 18 trees), and that he doesn't see 10 trees (otherwise he would be certain that there are 20 trees). Therefore A will answer "20" on the 2nd day, since he now knows that B has 8 trees.


Spoiler:
Same situation, but A sees 12 and B sees 6. Following the same reasoning, A knows that B sees 6 or 8, and therefore A knows that B knows that A sees 10, 12, or 14. B knows that A sees 12 or 14 trees, and he knows that A knows that B sees 4, 6, or 8 trees. A goes up first, and by not answering he says... what? If he saw 14, he still couldn't answer 20, so he doesn't signal that he doesn't see 14. Since no information was passed on to B, then B still can't answer on day 1. Day two rolls around, and A (who happens to be your friend, who thinks he solved the puzzle), confidently says "20" and is executed.

It's as you said: certain facts are not common knowledge. Saying that "A:10,12,14, B:6,8,10" is common knowledge is virtually no different from saying "A:12, B:8" is common knowledge.

ALFERALFER
Posts: 8
Joined: Tue Mar 19, 2013 3:21 pm UTC

Re: Towers, Courtyard, and trees

Postby ALFERALFER » Mon Sep 09, 2013 5:43 pm UTC

Xias wrote:
ekaprits wrote:I used to think that the above solution was the correct one for this riddle. A friend of mine disagrees, and I'm not so sure any more. I post his solution here. Can someone spot any problems with it? My (somewhat informal) reaction to it is that it assumes that
Spoiler:
certain facts are common knowledge, when they are not.


Here is the solution:
Spoiler:
At the initial state, A knows that B sees 6 or 8 trees. He also knows that B knows that A sees 10,12, or 14 trees. Similarly, B knows that A sees 10 or 12 trees, and he knows that A knows that B sees 6, 8, or 10 trees. Therefore, the common knowledge is A:10,12,14, B:6,8,10.

By not answering on the first day, A informs B that A knows that B knows that A sees either 10 or 12 trees (if he saw 14, he would have answered "20", since they both know that B has 6-10 trees). So the common knowledge is down to A:10,12, B:6,8,10. By not answering on his turn on the first day, B informs A that he doesn't see 6 trees (otherwise he would be certain that there are 18 trees), and that he doesn't see 10 trees (otherwise he would be certain that there are 20 trees). Therefore A will answer "20" on the 2nd day, since he now knows that B has 8 trees.


Spoiler:
Same situation, but A sees 12 and B sees 6. Following the same reasoning, A knows that B sees 6 or 8, and therefore A knows that B knows that A sees 10, 12, or 14. B knows that A sees 12 or 14 trees, and he knows that A knows that B sees 4, 6, or 8 trees. A goes up first, and by not answering he says... what? If he saw 14, he still couldn't answer 20, so he doesn't signal that he doesn't see 14. Since no information was passed on to B, then B still can't answer on day 1. Day two rolls around, and A (who happens to be your friend, who thinks he solved the puzzle), confidently says "20" and is executed.

It's as you said: certain facts are not common knowledge. Saying that "A:10,12,14, B:6,8,10" is common knowledge is virtually no different from saying "A:12, B:8" is common knowledge.


Spoiler:
B knows that A sees 12 or 14 trees, and he knows that A knows that B sees 4, 6, or 8 trees. WRONG............
B knows that A sees 12 or 14 trees, and B knows that A knows B sees 6 or 8 trees(because A sees 12).
A knows that B sees 6 or 8 trees, and A knows that B knows A sees 12 or 14 trees(because B sees 6).

If A passes the first time, B knows that A does not see 14. (14 & 8 are out) leaving only (14 &6) A would guess 20 if they saw 14 trees.
B knows A sees 12 so he says 18.

Xias
Posts: 363
Joined: Mon Jul 23, 2007 3:08 am UTC
Location: California
Contact:

Re: Towers, Courtyard, and trees

Postby Xias » Mon Sep 09, 2013 7:50 pm UTC

ALFERALFER wrote:
Xias wrote:
ekaprits wrote:I used to think that the above solution was the correct one for this riddle. A friend of mine disagrees, and I'm not so sure any more. I post his solution here. Can someone spot any problems with it? My (somewhat informal) reaction to it is that it assumes that
Spoiler:
certain facts are common knowledge, when they are not.


Here is the solution:
Spoiler:
At the initial state, A knows that B sees 6 or 8 trees. He also knows that B knows that A sees 10,12, or 14 trees. Similarly, B knows that A sees 10 or 12 trees, and he knows that A knows that B sees 6, 8, or 10 trees. Therefore, the common knowledge is A:10,12,14, B:6,8,10.

By not answering on the first day, A informs B that A knows that B knows that A sees either 10 or 12 trees (if he saw 14, he would have answered "20", since they both know that B has 6-10 trees). So the common knowledge is down to A:10,12, B:6,8,10. By not answering on his turn on the first day, B informs A that he doesn't see 6 trees (otherwise he would be certain that there are 18 trees), and that he doesn't see 10 trees (otherwise he would be certain that there are 20 trees). Therefore A will answer "20" on the 2nd day, since he now knows that B has 8 trees.


Spoiler:
Same situation, but A sees 12 and B sees 6. Following the same reasoning, A knows that B sees 6 or 8, and therefore A knows that B knows that A sees 10, 12, or 14. B knows that A sees 12 or 14 trees, and he knows that A knows that B sees 4, 6, or 8 trees. A goes up first, and by not answering he says... what? If he saw 14, he still couldn't answer 20, so he doesn't signal that he doesn't see 14. Since no information was passed on to B, then B still can't answer on day 1. Day two rolls around, and A (who happens to be your friend, who thinks he solved the puzzle), confidently says "20" and is executed.

It's as you said: certain facts are not common knowledge. Saying that "A:10,12,14, B:6,8,10" is common knowledge is virtually no different from saying "A:12, B:8" is common knowledge.


Spoiler:
B knows that A sees 12 or 14 trees, and he knows that A knows that B sees 4, 6, or 8 trees. WRONG............
B knows that A sees 12 or 14 trees, and B knows that A knows B sees 6 or 8 trees(because A sees 12).
A knows that B sees 6 or 8 trees, and A knows that B knows A sees 12 or 14 trees(because B sees 6).


No. Since B doesn't know that A sees 12, B must take into account the possibility that A sees 14, in which case A's knowledge of possible B's would include B seeing 4 trees. Same with A knowing that B knows that A sees 10, 12, or 14. This shouldn't be that hard to follow, it's the exact same logic you used to "solve" the 12/8 case incorrectly.

ALFERALFER wrote:
Spoiler:
If A passes the first time, B knows that A does not see 14. (14 & 8 are out) leaving only (14 &6) A would guess 20 if they saw 14 trees.
B knows A sees 12 so he says 18.


Why would A ever guess 20 just because he sees 14 trees, having received no information from B?

Consider this from the perspective of A:
1. You see 12 trees. You pass the first round. Then B passes. Does B see 6 or 8 trees? How do you know?
2. You see 14 trees. Does B have 4 or 6 trees? How do you know?

Consider this ffrom the perspective of B:
3. You see 6 trees. A passes the first round. Does he have 12 or 14 trees? How do you know?
4. You see 8 trees. A passes the first round. Does he have 10 or 12 trees? How do you know?

Your "solution" dictates that the answer to (1) is "8", but that requires the answers to (2) and (3) to be "6" and "12", respectively. But it also requires the answer to (4) to be "I don't know," but (3) and (4) are functionally identical.

The only *common* knowledge is that they both see an even number of trees.

campboy
Posts: 52
Joined: Wed Jun 18, 2008 1:54 am UTC

Re: Towers, Courtyard, and trees

Postby campboy » Tue Sep 10, 2013 10:12 am UTC

ekaprits wrote:I used to think that the above solution was the correct one for this riddle. A friend of mine disagrees, and I'm not so sure any more. I post his solution here. Can someone spot any problems with it? My (somewhat informal) reaction to it is that it assumes that
Spoiler:
certain facts are common knowledge, when they are not.


Yes, the problem is that your friend has the wrong definition of "common knowledge". For P to be common knowledge, any finite sentence of the form "A knows B knows A knows ... knows P" must be true. Working from that definition, if P is common knowledge then both A and B are aware that it is common knowledge, which is the property you actually need for any solution to work.

Setting P to be "B sees 6, 8, or 10 trees", A can't be sure that B knows that A knows P, so it is not common knowledge.

jay35
Posts: 46
Joined: Wed Oct 17, 2012 7:59 pm UTC

Re: Towers, Courtyard, and trees

Postby jay35 » Thu Sep 12, 2013 7:37 pm UTC

benneh wrote:
AvatarIII wrote:
benneh wrote:This is really just blue-eyes in disguise, I think.

Spoiler:
Day 1:
If Al can see more than 18 trees, he knows there must be 20 trees in total and both are released. Otherwise, both prisoners know Al can see at most 18 trees.
If Bob can see fewer than 2 trees, he knows there must be 18 trees in total and both are released. Otherwise, both prisoners know Bob can see at least 2 trees.

Day 2:
If Al can see more than 16 trees, he knows there must be 20 trees in total and both are released. Otherwise, both prisoners know Al can see at most 16 trees.
If Bob can see fewer than 4 trees, he knows there must be 18 trees in total and both are released. Otherwise, both prisoners know Bob can see at least 4 trees.

Etc.
In general, on day n:
If Al can see more than 20-2n trees, he knows there must be 20 trees in total and both are released. Otherwise, both prisoners know Al can see at most 20-2n trees.
If Bob can see fewer than 2n trees, he knows there must be 18 trees in total and both are released. Otherwise, both prisoners know Bob can see at least 2n trees.

In this situation, Al works out that there are 20 trees on day 5 and both prisoners are released.


but.... why? As far as I can tell, no information is changing each day, why would what day it was have any bearing on ability to deduce number of trees?


Spoiler:
On day 1, Al can do one of two things:
Either he sees more than 18 trees, and therefore concludes that there must be 20 trees in total.
Or he sees at most 18 trees, and concludes nothing.
The relevant point here is that if the second scenario comes to pass then Bob knows that Al couldn't have seen more than 18 trees, otherwise they would both have been released. So Bob has gained some information - that Al can see at most 18 trees. This process continues, with each prisoner gradually tightening the bounds on the possible number of trees the other can see, until one of them can deduce how many trees there are in total.


Spoiler:
The relevant point here is that if the second scenario comes to pass then Bob knows that Al couldn't have seen more than 18 trees, otherwise they would both have been released. So Bob has gained some information - that Al can see at most 18 trees.

Actually, Bob would know more than that. Based on the number of trees he (Bob) saw, he would know that Al saw at most 20 minus the number Bob saw. This should speed things up.

Xias
Posts: 363
Joined: Mon Jul 23, 2007 3:08 am UTC
Location: California
Contact:

Re: Towers, Courtyard, and trees

Postby Xias » Thu Sep 12, 2013 10:58 pm UTC

jay35 wrote:
benneh wrote:
AvatarIII wrote:
benneh wrote:This is really just blue-eyes in disguise, I think.

Spoiler:
Day 1:
If Al can see more than 18 trees, he knows there must be 20 trees in total and both are released. Otherwise, both prisoners know Al can see at most 18 trees.
If Bob can see fewer than 2 trees, he knows there must be 18 trees in total and both are released. Otherwise, both prisoners know Bob can see at least 2 trees.

Day 2:
If Al can see more than 16 trees, he knows there must be 20 trees in total and both are released. Otherwise, both prisoners know Al can see at most 16 trees.
If Bob can see fewer than 4 trees, he knows there must be 18 trees in total and both are released. Otherwise, both prisoners know Bob can see at least 4 trees.

Etc.
In general, on day n:
If Al can see more than 20-2n trees, he knows there must be 20 trees in total and both are released. Otherwise, both prisoners know Al can see at most 20-2n trees.
If Bob can see fewer than 2n trees, he knows there must be 18 trees in total and both are released. Otherwise, both prisoners know Bob can see at least 2n trees.

In this situation, Al works out that there are 20 trees on day 5 and both prisoners are released.


but.... why? As far as I can tell, no information is changing each day, why would what day it was have any bearing on ability to deduce number of trees?


Spoiler:
On day 1, Al can do one of two things:
Either he sees more than 18 trees, and therefore concludes that there must be 20 trees in total.
Or he sees at most 18 trees, and concludes nothing.
The relevant point here is that if the second scenario comes to pass then Bob knows that Al couldn't have seen more than 18 trees, otherwise they would both have been released. So Bob has gained some information - that Al can see at most 18 trees. This process continues, with each prisoner gradually tightening the bounds on the possible number of trees the other can see, until one of them can deduce how many trees there are in total.


Spoiler:
The relevant point here is that if the second scenario comes to pass then Bob knows that Al couldn't have seen more than 18 trees, otherwise they would both have been released. So Bob has gained some information - that Al can see at most 18 trees.

Actually, Bob would know more than that. Based on the number of trees he (Bob) saw, he would know that Al saw at most 20 minus the number Bob saw. This should speed things up.


Intuitively, yes. However, since Al doesn't know what numbers Bob has Al limited to (he can only limit them to some set of numbers himself) and Bob can't know what those numbers are, it doesn't actually speed anything up. It's the same in the blue eyes puzzle; All of the blue eyed people know that the other blue eyed people see either 98 or 99 other blue eyed people, but since it's not common knowledge, that really doesn't help anyone.

A knowing that B sees either (18-A) or (20-A) is no different, before the game is played, from knowing that the total is either 18 or 20. It is only useful once A can learn what B doesn't know.

User avatar
learsfool
Posts: 239
Joined: Sat Sep 14, 2013 3:29 am UTC
Location: Madison, WI

Re: Towers, Courtyard, and trees

Postby learsfool » Sun Sep 15, 2013 2:28 am UTC

Xias wrote:A knowing that B sees either (18-A) or (20-A) is no different, before the game is played, from knowing that the total is either 18 or 20. It is only useful once A can learn what B doesn't know.

Yeah, I'm in agreement here.

If B sees 6 trees, I see exactly the same scenario.

The only logical outcome I see is they both stay imprisoned and hope eventually to get out of that crazy mess some other way.

User avatar
Moose Anus
Posts: 430
Joined: Fri Oct 14, 2011 10:12 pm UTC

Re: Towers, Courtyard, and trees

Postby Moose Anus » Mon Sep 16, 2013 4:22 pm UTC

Al says there are 0 trees on the first day. Because prison sucks.
Lemonade? ...Aww, ok.

Xias
Posts: 363
Joined: Mon Jul 23, 2007 3:08 am UTC
Location: California
Contact:

Re: Towers, Courtyard, and trees

Postby Xias » Mon Sep 16, 2013 11:35 pm UTC

learsfool wrote:
Xias wrote:A knowing that B sees either (18-A) or (20-A) is no different, before the game is played, from knowing that the total is either 18 or 20. It is only useful once A can learn what B doesn't know.

Yeah, I'm in agreement here.

If B sees 6 trees, I see exactly the same scenario.

The only logical outcome I see is they both stay imprisoned and hope eventually to get out of that crazy mess some other way.


But they can get out of it through the solution to the puzzle:

Spoiler:
They pass until Day 5, when Al correctly says "20." Bob passing on each day removes the possibilities 0, 2, 4, and 6, respectively, and once Bob passes on day 4, Al knows that Bob's only possible number is 8.


If you have trouble seeing how there is information passed (it's obvious that Bob doesn't see 20 right from the start!) try thinking about it this way:

Spoiler:
You are an outsider and do not know how many trees either of them see.

Possible arrangements: (20,0), (18,2), (18,0), (16,4), (16,2), (14,6), (14,4), (12,8), (12,6), (10,10), (10,8), (8,10), (8,12), (6,14) (6,12), (4,16), (4,14), (2,18), (2,16), (0,18), (0,20).

On day 1, the only way for Al to know how many trees there are is if he saw 20. So when he passes, you rule out (20,0) from the possibilities. Then the only way for Bob to guess correctly is if he sees 20 or 0, so when he passes, you rule out (0,20) and (18,0).

On day 2, the only way for Al to know how many trees there are is if he saw 18 or 0, so when he passes you rule out (18,2) and (0,18). Then Bob passes, ruling out (2,18) and (16,2).

On day 3, you rule out (16,4) and (2,16), then you rule out (4,16) and (14,4).

On day 4, you rule out (14,6) and (4,14), then you rule out (6,14) and (12,6). Now the only possible remaining combinations are (12,8), (10,10), (10,8), (8,10), (8,12), (6,12).

On the morning of day 5, you find out that Al sees 12 trees. Since the only remaining possibility with Al=12 is (12,8), you now know for certain that the total is 20.

Now, why would knowing that Al had 12 from the beginning hinder you in this process? Sure, you would have known from the beginning that it was either (12,8) or (12,6). So you would have predicted that they would both pass on days one, two, and three. The question for you (and Al) then becomes "Does Bob have 6 or 8 trees? If he see 6, then he'll answer on day 4. If he doesn't, then I know he sees 8."

User avatar
learsfool
Posts: 239
Joined: Sat Sep 14, 2013 3:29 am UTC
Location: Madison, WI

Re: Towers, Courtyard, and trees

Postby learsfool » Tue Sep 17, 2013 12:05 am UTC

Xias wrote:But they can get out of it through the solution to the puzzle:

Spoiler:
They pass until Day 5, when Al correctly says "20." Bob passing on each day removes the possibilities 0, 2, 4, and 6, respectively, and once Bob passes on day 4, Al knows that Bob's only possible number is 8.


If you have trouble seeing how there is information passed (it's obvious that Bob doesn't see 20 right from the start!) try thinking about it this way:

Spoiler:
You are an outsider and do not know how many trees either of them see.

Possible arrangements: (20,0), (18,2), (18,0), (16,4), (16,2), (14,6), (14,4), (12,8), (12,6), (10,10), (10,8), (8,10), (8,12), (6,14) (6,12), (4,16), (4,14), (2,18), (2,16), (0,18), (0,20).

On day 1, the only way for Al to know how many trees there are is if he saw 20. So when he passes, you rule out (20,0) from the possibilities. Then the only way for Bob to guess correctly is if he sees 20 or 0, so when he passes, you rule out (0,20) and (18,0).

On day 2, the only way for Al to know how many trees there are is if he saw 18 or 0, so when he passes you rule out (18,2) and (0,18). Then Bob passes, ruling out (2,18) and (16,2).

On day 3, you rule out (16,4) and (2,16), then you rule out (4,16) and (14,4).

On day 4, you rule out (14,6) and (4,14), then you rule out (6,14) and (12,6). Now the only possible remaining combinations are (12,8), (10,10), (10,8), (8,10), (8,12), (6,12).

On the morning of day 5, you find out that Al sees 12 trees. Since the only remaining possibility with Al=12 is (12,8), you now know for certain that the total is 20.

Now, why would knowing that Al had 12 from the beginning hinder you in this process? Sure, you would have known from the beginning that it was either (12,8) or (12,6). So you would have predicted that they would both pass on days one, two, and three. The question for you (and Al) then becomes "Does Bob have 6 or 8 trees? If he see 6, then he'll answer on day 4. If he doesn't, then I know he sees 8."


Wait, where does it say that they always see a different number of trees, that the view never repeats, and that they know that?

Also, where are all the odd numbers?

Xias
Posts: 363
Joined: Mon Jul 23, 2007 3:08 am UTC
Location: California
Contact:

Re: Towers, Courtyard, and trees

Postby Xias » Tue Sep 17, 2013 9:08 am UTC

learsfool wrote:
Xias wrote:But they can get out of it through the solution to the puzzle:

Spoiler:
They pass until Day 5, when Al correctly says "20." Bob passing on each day removes the possibilities 0, 2, 4, and 6, respectively, and once Bob passes on day 4, Al knows that Bob's only possible number is 8.


If you have trouble seeing how there is information passed (it's obvious that Bob doesn't see 20 right from the start!) try thinking about it this way:

Spoiler:
You are an outsider and do not know how many trees either of them see.

Possible arrangements: (20,0), (18,2), (18,0), (16,4), (16,2), (14,6), (14,4), (12,8), (12,6), (10,10), (10,8), (8,10), (8,12), (6,14) (6,12), (4,16), (4,14), (2,18), (2,16), (0,18), (0,20).

On day 1, the only way for Al to know how many trees there are is if he saw 20. So when he passes, you rule out (20,0) from the possibilities. Then the only way for Bob to guess correctly is if he sees 20 or 0, so when he passes, you rule out (0,20) and (18,0).

On day 2, the only way for Al to know how many trees there are is if he saw 18 or 0, so when he passes you rule out (18,2) and (0,18). Then Bob passes, ruling out (2,18) and (16,2).

On day 3, you rule out (16,4) and (2,16), then you rule out (4,16) and (14,4).

On day 4, you rule out (14,6) and (4,14), then you rule out (6,14) and (12,6). Now the only possible remaining combinations are (12,8), (10,10), (10,8), (8,10), (8,12), (6,12).

On the morning of day 5, you find out that Al sees 12 trees. Since the only remaining possibility with Al=12 is (12,8), you now know for certain that the total is 20.

Now, why would knowing that Al had 12 from the beginning hinder you in this process? Sure, you would have known from the beginning that it was either (12,8) or (12,6). So you would have predicted that they would both pass on days one, two, and three. The question for you (and Al) then becomes "Does Bob have 6 or 8 trees? If he see 6, then he'll answer on day 4. If he doesn't, then I know he sees 8."


Wait, where does it say that they always see a different number of trees, that the view never repeats, and that they know that?

Also, where are all the odd numbers?


Whoops, I did screw up on the odd numbers - I have NO idea why I did that. However, it says that the total is either 18 or 20, that they have a view from a tower (and I'm assuming the trees don't uproot themselves and move around) and that they all know this information.

To correct for odd numbers:

Spoiler:
Just include the next odd number (either next lowest when working down, or next highest when working up)

What Al must see to guess correctly on the following days:
Day 1: 20 or 19
Day 2: 18 or 17 or 0 or 1
Day 3: 16 or 15 or 2 or 3
Day 4: 14 or 13 or 4 or 5
etc...

For Bob:
Day 1: 20 or 19 or 0 or 1
Day 2: 18 or 17 or 2 or 3
Day 3: 16 or 15 or 4 or 5
Day 4: 14 or 13 or 6 or 7
etc.

This is because if Al sees 19 on the first day, then he knows the total is 20, and so on.

User avatar
learsfool
Posts: 239
Joined: Sat Sep 14, 2013 3:29 am UTC
Location: Madison, WI

Re: Towers, Courtyard, and trees

Postby learsfool » Tue Sep 17, 2013 11:12 am UTC

Xias wrote:
Whoops, I did screw up on the odd numbers - I have NO idea why I did that. However, it says that the total is either 18 or 20, that they have a view from a tower (and I'm assuming the trees don't uproot themselves and move around) and that they all know this information.

To correct for odd numbers:

Spoiler:
Just include the next odd number (either next lowest when working down, or next highest when working up)

What Al must see to guess correctly on the following days:
Day 1: 20 or 19
Day 2: 18 or 17 or 0 or 1
Day 3: 16 or 15 or 2 or 3
Day 4: 14 or 13 or 4 or 5
etc...

For Bob:
Day 1: 20 or 19 or 0 or 1
Day 2: 18 or 17 or 2 or 3
Day 3: 16 or 15 or 4 or 5
Day 4: 14 or 13 or 6 or 7
etc.

This is because if Al sees 19 on the first day, then he knows the total is 20, and so on.


Even with the odd numbers, I still have no idea why they have to be unique every day. If Al sees 12 on day one, and 9 on day 2, why can't he see 12 again on day three?

Are we really sure there's a solution to this?

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: Towers, Courtyard, and trees

Postby jestingrabbit » Tue Sep 17, 2013 11:31 am UTC

We're definitely assuming that Al sees the same number of trees every day, same with Bob. What is changing is the cases that we can eliminate.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

User avatar
learsfool
Posts: 239
Joined: Sat Sep 14, 2013 3:29 am UTC
Location: Madison, WI

Re: Towers, Courtyard, and trees

Postby learsfool » Tue Sep 17, 2013 8:33 pm UTC

jestingrabbit wrote:We're definitely assuming that Al sees the same number of trees every day, same with Bob. What is changing is the cases that we can eliminate.


Is there some form of 'logical' that I'm not aware of then?

Because unless they have a chance to plot beforehand, there's no solution to this other than stalling for as long as possible.

User avatar
JBJ
Posts: 1263
Joined: Fri Dec 12, 2008 6:20 pm UTC
Location: a point or extent in space

Re: Towers, Courtyard, and trees

Postby JBJ » Tue Sep 17, 2013 8:57 pm UTC

learsfool wrote:
jestingrabbit wrote:We're definitely assuming that Al sees the same number of trees every day, same with Bob. What is changing is the cases that we can eliminate.


Is there some form of 'logical' that I'm not aware of then?

Because unless they have a chance to plot beforehand, there's no solution to this other than stalling for as long as possible.

If I'm not mistaken... while they aren't able to plot beforehand, they are perfect logicians so they are able to collaborate in the sense that they can rely on the other to act a certain way given the amount of information they have.
Both Al and Bob know that there are either 18 or 20 trees. Al can see 12, which is more than 1/2 of the known upper limit so he is going to tackle the upper bound. He knows that Bob can see less than half of the known upper limit, so Al is going to rely on Bob to tackle the lower bound.

I'm curious, would there be a solution if both Al and Bob saw 9 or 10 trees (for a total number of 18/20 respectively)?
So, you sacked the cocky khaki Kicky Sack sock plucker?
The second cocky khaki Kicky Sack sock plucker I've sacked since the sixth sitting sheet slitter got sick.

User avatar
learsfool
Posts: 239
Joined: Sat Sep 14, 2013 3:29 am UTC
Location: Madison, WI

Re: Towers, Courtyard, and trees

Postby learsfool » Tue Sep 17, 2013 9:18 pm UTC

JBJ wrote:
learsfool wrote:Is there some form of 'logical' that I'm not aware of then?

Because unless they have a chance to plot beforehand, there's no solution to this other than stalling for as long as possible.

If I'm not mistaken... while they aren't able to plot beforehand, they are perfect logicians so they are able to collaborate in the sense that they can rely on the other to act a certain way given the amount of information they have.
Both Al and Bob know that there are either 18 or 20 trees. Al can see 12, which is more than 1/2 of the known upper limit so he is going to tackle the upper bound. He knows that Bob can see less than half of the known upper limit, so Al is going to rely on Bob to tackle the lower bound.

I'm curious, would there be a solution if both Al and Bob saw 9 or 10 trees (for a total number of 18/20 respectively)?

Yeah, see, there isn't.

We're talking about a gamble here. Once Al and Bob both pass, with no information, they're stuck making predictions. Those predictions have the same results regardless of how many trees they see.

Unless they're forced to make a decision, they'd always pass.

Xias
Posts: 363
Joined: Mon Jul 23, 2007 3:08 am UTC
Location: California
Contact:

Re: Towers, Courtyard, and trees

Postby Xias » Tue Sep 17, 2013 9:58 pm UTC

JBJ wrote:
learsfool wrote:Is there some form of 'logical' that I'm not aware of then?

Because unless they have a chance to plot beforehand, there's no solution to this other than stalling for as long as possible.

If I'm not mistaken... while they aren't able to plot beforehand, they are perfect logicians so they are able to collaborate in the sense that they can rely on the other to act a certain way given the amount of information they have.
Both Al and Bob know that there are either 18 or 20 trees. Al can see 12, which is more than 1/2 of the known upper limit so he is going to tackle the upper bound. He knows that Bob can see less than half of the known upper limit, so Al is going to rely on Bob to tackle the lower bound.

I'm curious, would there be a solution if both Al and Bob saw 9 or 10 trees (for a total number of 18/20 respectively)?


Yes.
Spoiler:
If they both see 9, Bob correctly says "18" on day 5. If they both see 10, Al correctly says "20" on day 6. They don't really need to choose which direction they go; both the upper bound and lower bound are excluded on each day through logic alone.

learsfool wrote:Yeah, see, there isn't.

We're talking about a gamble here. Once Al and Bob both pass, with no information, they're stuck making predictions. Those predictions have the same results regardless of how many trees they see.

Unless they're forced to make a decision, they'd always pass.


There's absolutely no gamble.

Spoiler:
If Al sees 20, or 19, do you agree that he would correctly guess on the first day?

So, if he doesn't correctly guess on the first day, then Bob knows that Al does NOT see 20 or 19. So, if Bob sees 0, 1, 19, or 20, he can correctly guess on the first day, right?

So, if Bob doesn't correctly guess on the first day, then Al knows that Bob does NOT see 0, 1, 19, or 20. So, if Al sees 0, 1, 17, or 18, then he can correctly guess on the second day.

Etc.

If you think that Bob seeing some number greater than 1 and automatically knowing that Al doesn't see 19 or 20 somehow negates this logic, you are wrong. Knowing how many trees they can see for themselves (and the possible number of trees that their opponent can see) only means they can already predict that their opponent will pass on days 1 through n.


And if you're stuck on the "what if they see different trees every day" question, that's a weird assumption to make. They are in a prison, assigned to towers facing a courtyard. Unless the prison is made out of Hogwarts or the trees are Ents, it is not reasonable for them to think that anything changes from day to day.

Here are the possible starting points and their solutions:
Spoiler:
Day 1: Al correctly guesses if he sees 20 or 19 trees. Bob correctly guesses if he sees 0, 1, 19, or 20 trees.
Day 2: Al correctly guesses if he sees 0, 1, 17, or 18 trees. Bob correctly guesses if he sees 2, 3, 17, or 18 trees.
Day 3: Al correctly guesses if he sees 2, 3, 15, or 16 trees. Bob correctly guesses if he sees 4, 5, 15, or 16 trees.
Day 4: Al correctly guesses if he sees 4, 5, 13, or 14 trees. Bob correctly guesses if he sees 6, 7, 13, or 14 trees.
Day 5: Al correctly guesses if he sees 6, 7, 11, or 12 trees. Bob correctly guesses if he sees 8, 9, 11, or 12 trees.
Day 6: Al correctly guesses if he sees 8, 9, or 10 trees.

Each day works through a sort of induction as tree views get cancelled out.

User avatar
learsfool
Posts: 239
Joined: Sat Sep 14, 2013 3:29 am UTC
Location: Madison, WI

Re: Towers, Courtyard, and trees

Postby learsfool » Wed Sep 18, 2013 12:47 am UTC

Xias wrote:
There's absolutely no gamble.

Spoiler:
If Al sees 20, or 19, do you agree that he would correctly guess on the first day?

So, if he doesn't correctly guess on the first day, then Bob knows that Al does NOT see 20 or 19. So, if Bob sees 0, 1, 19, or 20, he can correctly guess on the first day, right?

So, if Bob doesn't correctly guess on the first day, then Al knows that Bob does NOT see 0, 1, 19, or 20. So, if Al sees 0, 1, 17, or 18, then he can correctly guess on the second day.

Etc.

If you think that Bob seeing some number greater than 1 and automatically knowing that Al doesn't see 19 or 20 somehow negates this logic, you are wrong. Knowing how many trees they can see for themselves (and the possible number of trees that their opponent can see) only means they can already predict that their opponent will pass on days 1 through n.


And if you're stuck on the "what if they see different trees every day" question, that's a weird assumption to make. They are in a prison, assigned to towers facing a courtyard. Unless the prison is made out of Hogwarts or the trees are Ents, it is not reasonable for them to think that anything changes from day to day.

Here are the possible starting points and their solutions:
Spoiler:
Day 1: Al correctly guesses if he sees 20 or 19 trees. Bob correctly guesses if he sees 0, 1, 19, or 20 trees.
Day 2: Al correctly guesses if he sees 0, 1, 17, or 18 trees. Bob correctly guesses if he sees 2, 3, 17, or 18 trees.
Day 3: Al correctly guesses if he sees 2, 3, 15, or 16 trees. Bob correctly guesses if he sees 4, 5, 15, or 16 trees.
Day 4: Al correctly guesses if he sees 4, 5, 13, or 14 trees. Bob correctly guesses if he sees 6, 7, 13, or 14 trees.
Day 5: Al correctly guesses if he sees 6, 7, 11, or 12 trees. Bob correctly guesses if he sees 8, 9, 11, or 12 trees.
Day 6: Al correctly guesses if he sees 8, 9, or 10 trees.

Each day works through a sort of induction as tree views get cancelled out.

I see it, no worries there. I just brought up the odd numbers because that's totally the sort of thing -I- would miss :)

What actually throws me is the fact that they'd have got be assuming that there's only one solution to the puzzle and both be acting upon this one. I get the upper/lower bounds bit, and it's clever, but not being a perfect logician myself I'm not sure that I can predict them only being able to come up with one solution like that.
Last edited by learsfool on Wed Sep 18, 2013 5:25 am UTC, edited 1 time in total.

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

Re: Towers, Courtyard, and trees

Postby Gwydion » Wed Sep 18, 2013 5:10 am UTC

learsfool wrote:What actually throws me is the fact that they'd have go be assuming that there's only one solution to the puzzle and both be acting upon this one. I get the upper/lower bounds bit, and it's clever, but not being a perfect logician myself I'm not sure that I can predict them only being able to come up with one solution like that.
In a manner similar to blue eyes, we can further show that any solution that takes longer is irrelevant and no solution that gets to an answer faster is possible. As perfect logicians, they might think of other solutions but the slower ones will be ignored in favor of this (or any equivalent ones).


Return to “Logic Puzzles”

Who is online

Users browsing this forum: No registered users and 11 guests