wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> One evil king, two prisoners, 20 trees
        
(Message started by: Zaz on Jan 7^th, 2010, 4:49am)

Title: One evil king, two prisoners, 20 trees
Post by Zaz on Jan 7^th, 2010, 4:49am

I have only heard the following riddle in swedish, and this is my attempt of a translation.

Code:

An evil king imprisons two people, A and B. They are placed in the king's evil castle in separate towers. Each tower has a window, and through the windows A and B can see separate parts of the castle's garden. In the garden there grows 20 trees. The prisoners can't communicate in any way with each other.

A can see 12 trees through the window in A-tower.
B can see 8 trees through the window in B-tower.

Both are told that the garden has either 18 or 20 trees, and that they together see all the trees, and that no tree is seen by both of them.

Every day, starting with the day they are imprisoned, a guard asks them a question. The guard first asks A, and if no answer is given, goes on to ask B. The question asked is: "Is there 18 or 20 trees in the garden?"

If the asked prisoner answers correctly, both prisoners are released immediately.
If the asked prisoner answers erroneously, both prisoners are executed immediately.
The prisoner can opt to not answer, in which case the guard will continue to ask the next prisoner as mentioned above. (The prisoner will opt this if it is not sure, since we assume both prisoners to be completely logical entities.)

Will the prisoners ever be released? After how many days?

I looked through the archives here, and couldn't find this or anything similar. If anyone knows where this riddle comes from, or its actual name and original text, please tell me. I've looked all over and haven't found it.

Title: Re: One evil king, two prisoners, 20 trees
Post by SMQ on Jan 7^th, 2010, 5:56am

The prisoners will be [hide]released on the fifth day[/hide].

[hideb]A sees 12 trees, knows B sees either 6 or 8 trees, reasons that:
If B sees 6 trees then B knows A' sees either 14 or 12 trees, reasons that:
If A' sees 14 trees then A' knows B' sees either 4 or 6 trees, reasons that:
If B' sees 4 trees then B' knows A'' sees either 16 or 14 trees, reasons that:
If A'' sees 16 trees then A'' knows B'' sees either 2 or 4 trees, reasons that:
If B'' sees 2 trees then B'' knows A⁽³⁾ sees either 18 or 16 trees, reasons that:
If A⁽³⁾ sees 18 trees then A⁽³⁾ knows B⁽³⁾ sees either 0 or 2 trees, reasons that:
If B⁽³⁾ sees 0 trees then B⁽³⁾ knows A⁽⁴⁾ sees either 20 or 18 trees, reasons that:
If A⁽⁴⁾ sees 20 trees then he would announce an answer!
Otherwise if A⁽⁴⁾ sees 18 trees then A⁽⁴⁾ knows B⁽⁴⁾ sees either 0 or 2 trees, reasons that:
...
Otherwise if B⁽³⁾ sees 2 trees then B⁽³⁾ knows A⁽⁴⁾ sees either 18 or 16 trees, reasons that:
...
Otherwise if A⁽³⁾ sees 16 trees than A⁽³⁾ knows B⁽³⁾ sees either 2 or 4 trees, reasons that:
...
Otherwise if B'' sees 4 trees then B'' knows A⁽³⁾ sees either 16 or 14 trees, reasons that:
...
Otherwise if A'' sees 14 trees then A'' knows B'' sees either 4 or 6 trees, reasons that:
...
Otherwise if B' sees 6 trees then B' knows A'' sees either 14 or 12 trees, reasons that:
...
Otherwise if A' sees 12 trees then A' knows B' sees either 6 or 8 trees, reasons that:
...
Otherwise if B sees 8 trees then B knows A' sees either 12 or 10 trees, reasons that:
If A' sees 12 trees then A' knows B' sees either 6 or 8 trees, reasons that:
...
Otherwise if A' sees 10 trees then A' knows B' sees either 8 or 10 trees, reasons that:

...and so on where A', A'', A⁽³⁾, etc. represent more deeply nested mental hypothetical prisoners.

After the first half of the first day, when A doesn't answer, the tree of possibilities is pruned since eight-times-hypothetical A⁽⁴⁾ would have answered if he saw 20 trees.

After the second half of the first day, when B doesn't answer, the tree of possibilities is pruned again since seven-times-hypothetical B⁽³⁾ wound have known A⁽⁴⁾ saw only 18 trees and answered.

And so on, pruning one possibility each half day, until, on the morning of the fifth day, only-once-hypothetical B can only see 8 trees, allowing A to declare that there are 20 trees in the garden.
[/hideb]
See this thread (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_medium;action=display;num=1027806383) (dicussing this riddle (http://www.ocf.berkeley.edu/~wwu/riddles/medium.shtml#brownEyesRedEyes)) for several other approaches to problems of this type. ;)

Edit: And welcome to the forum, Zaz!

--SMQ

Title: Re: One evil king, two prisoners, 20 trees
Post by rmsgrey on Jan 7^th, 2010, 6:23am

I don't recognise the "story" of the puzzle, but the mechanics of it - two or more people successively declaring their ignorance to enable one or more of them to deduce something - are used in a number of puzzles around here.

One of the archetypical ones involves five hats - three black and two white - and three people, each of whom can see the hat each of the others wears but not their own. No matter which three hats are chosen, or how they're arranged, by the time you've asked each of them once, one of them will have correctly identified their hat.

Title: Re: One evil king, two prisoners, 20 trees
Post by towr on Jan 7^th, 2010, 8:03am

Here's a graphical way to solve the problem (attached as pdf).

Title: Re: One evil king, two prisoners, 20 trees
Post by Zaz on Jan 7^th, 2010, 8:15am

Thanks for the info.

One thing I wondered though...
As you say, they will be [hideb] released at day five if one iterates reasoning from the fact that A would answer the first day if he saw 20 trees.... however, you get a different answer if you iterate from B?

If B sees 20 and A 0, B will answer the first day. If B sees 18 and A sees 0, A will answer the second day. If B sees 18 and A sees 2, B will answer the second day
[...]
If B sees 8 and A sees 12, B will answer on the seventh day.

[/hideb]

I had a blog post about this, but it is in swedish... I'll translate it when I'm not at work. ^^

Title: Re: One evil king, two prisoners, 20 trees
Post by JohanC on Jan 7^th, 2010, 8:22am

This problem certainly looks like an interesting variation to the hidden-information theme. Especially that you need so many rounds to answer a question with only two possible options.

I'm wondering whether the solution could be written simpler, I mean without all those levels of indirection. But I see it dificult.
The only thing I see (like with a lot of riddles), is first restating it with lower numbers to "get the trick".

Title: Re: One evil king, two prisoners, 20 trees
Post by towr on Jan 7^th, 2010, 8:23am

You start the iteration with whichever prisoner is asked first by the guard. If you reverse the order, it doesn't change much [hide]it would still be the fifth day, but it would be the second prisoner that gives the answer (which, however, would still be A, since we reversed their order)[/hide].
If instead of reversing the order you skip A on the first day, then [hide]you get basically the same as when you reverse the order and in addition shift the process "half a day". Which means it runs over to the sixth day.[/hide]
It is, however, important the prisoners know exactly in what order and how often they're asked.

Title: Re: One evil king, two prisoners, 20 trees
Post by Zaz on Jan 7^th, 2010, 12:13pm

Nono, that is not what I meant.

I meant that if you try to solve it by [hideb] imagining different distributions of visible trees for A and B, depending on which one you imagine starts with 20 trees, you will get a different result.

I tried to translate my blog post into english, but I can't post it here because I can't figure out the bb-code for managing tables.

I instead put the file here (http://blog.prefect.se/wp-content/uploads/eng.html), take a look and tell me if/where my reasoning is faulty.
[/hideb]

Title: Re: One evil king, two prisoners, 20 trees
Post by towr on Jan 7^th, 2010, 12:36pm

[hide]They both imagine that alternates of them can start with 20 trees. You need to start with all possible worlds. And you eliminate possible worlds according to the order in which prisoners are questioned and how they respond.

If you don't approach the problem from "both ends" (where and alternate A sees 20, and where an alternate B sees 20), then you do indeed get the problem there seem to be two answers, depending on where you start. However, if you look at the pdf I posted, you can see that it works out fine if you consider the whole picture.[/hide]

Title: Re: One evil king, two prisoners, 20 trees
Post by Hippo on Jan 7^th, 2010, 1:16pm

on 01/07/10 at 08:03:39, towr wrote:

Here's a graphical way to solve the problem (attached as pdf).

Just two things ... typo least / leaTS and I would not color the left bottom node at the first half of the first day.

The graphical solution is very nice.

Title: Re: One evil king, two prisoners, 20 trees
Post by towr on Jan 7^th, 2010, 2:05pm

on 01/07/10 at 13:16:06, Hippo wrote:

Just two things ... typo least / leaTS

Yeah, I noticed that after I uploaded it here. If I had caught it before, I would have fixed it, but unfortunately I missed it, and I didn't want to go through the trouble of reuploading it.

Quote:

and I would not color the left bottom node at the first half of the first day.

Well, as it is, the colouring accurately reflects their knowledge. At the start A would know whether he's in world 20,0 and B would also know whether he's in 0,20.
But on the other hand, to reflect the process/order in which possible worlds are eliminated, it might have been better not to have coloured the bottom left node. So I can see your point.

Quote:

The graphical solution is very nice.

Thanks.

Title: Re: One evil king, two prisoners, 20 trees
Post by rmsgrey on Jan 8^th, 2010, 7:04am

One trivial simplification for this particular version would be to count pairs of trees rather than individual trees - A sees 6 pairs, B sees 4, and there are known to be 9 or 10 pairs in total.

Title: Re: One evil king, two prisoners, 20 trees
Post by ekaprits on Sep 2^nd, 2013, 6:30am

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 [hide]certain facts are common knowledge, when they are not.[/hide]

Here is the solution:
[hideb]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.[/hideb]

What do you guys think?

Title: Re: One evil king, two prisoners, 20 trees
Post by rmsgrey on Sep 2^nd, 2013, 9:25am

on 09/02/13 at 06:30:41, ekaprits wrote:

The problem is here:

(if he saw 14, he would have answered "20", since they both know that B has 6-10 trees)

The only reason they both know that B has 6-10 trees is because A has 12. If A had 14 trees, he'd know that B has 4 or 6, so if he saw 14 trees he wouldn't be able to answer "20" because his being able to answer "20" when he sees 14 trees relies on his deductions from seeing 12 trees.

If A sees 2 trees added to his view, and is told that the total is still either 18 or 20, that B's view is unchanged, and that they still see every tree exactly once between them, then, yes, he can conclude that there are now 20 trees (and there were 18 before)...

If A sees both 14 and 12 trees for some other reason, then it's hard to make any deductions...