HermanHiddema wrote:
Your program needs to know the prisoners' strategy, just brute forcing all combinations won't help.
Uh... logically their strategy must be a member of the set of all combinations, no? The problem states they can't communicate in any way once the trial starts...
permutation 0: [0 1 2 3] (each number represents a prisoner; each permutation is a possible way the prisoners could be arranged in the boxes)
permutation 1: [0 1 3 2]
permutation 2: [0 2 1 3]
permutation 3: [0 3 1 2]
permutation 4: [0 2 3 1]
permutation 5: [0 3 2 1]
permutation 6: [1 0 2 3]
permutation 7: [1 0 3 2]
permutation 8: [2 0 1 3]
permutation 9: [3 0 1 2]
permutation 10: [2 0 3 1]
permutation 11: [3 0 2 1]
permutation 12: [1 2 0 3]
permutation 13: [1 3 0 2]
permutation 14: [2 1 0 3]
permutation 15: [3 1 0 2]
permutation 16: [2 3 0 1]
permutation 17: [3 2 0 1]
permutation 18: [1 2 3 0]
permutation 19: [1 3 2 0]
permutation 20: [2 1 3 0]
permutation 21: [3 1 2 0]
permutation 22: [2 3 1 0]
permutation 23: [3 2 1 0]
box choice 0: [0 1] (these are the 6 unique possible ways of choosing 2 out of 4 boxes)
box choice 1: [0 2]
box choice 2: [0 3]
box choice 3: [1 2]
box choice 4: [1 3]
box choice 5: [2 3]
(the brute force function prints a line each time it finds a better solution:)
= 2 (two possible arrangements satisfied that set of choices)
= 2, [[0 3]]
= 4
= 4, [[2 3]]
= 4, [[2 3] [2 3]]
= 4, [[0 1] [2 3] [2 3]]
(final output:)
0.16666666666666666 [[0 1] [0 1] [2 3] [2 3]]
(meaning that the best solution matched 4/24 arrangements, or 16.6%, and the choices that got there were the first two boxes twice, then the second two twice)
In what way am I misunderstanding the problem?
Re: Logical puzzles
Posted: Sat Dec 04, 2010 8:29 pm
by HermanHiddema
daniel_the_smith wrote:
HermanHiddema wrote:
Your program needs to know the prisoners' strategy, just brute forcing all combinations won't help.
Uh... logically their strategy must be a member of the set of all combinations, no? The problem states they can't communicate in any way once the trial starts...
I will add a hint: (this one shows why your brute force strategy doesn't work)
Prisoners do not know, in advance, which 50 boxes they will open.
And another, bigger hint:
Prisoners do know, in advance, which box they will open first.
Re: Logical puzzles
Posted: Sat Dec 04, 2010 8:52 pm
by ethanb
robinz wrote:
PS: isn't it nice of bad guys in these kind of puzzles to always actually pose a solveable puzzle, rather than just killing the lot of them
Honestly I was more interested in the fact that there is an official village logician. Although I guess it could be a PC way of saying "witch doctor" or something...
Re: Logical puzzles
Posted: Tue Dec 07, 2010 3:12 pm
by Violence
Here's a fun one for you all.
A teacher says: I'm thinking of two natural numbers bigger than 1. Try to guess what they are.
The first student knows their product and the other one knows their sum.
First: I do not know the sum.
Second: I knew that. The sum is less than 14.
First: I knew that. However, now I know the numbers.
Second: And so do I.
What were the numbers?
Re: Logical puzzles
Posted: Tue Dec 07, 2010 5:44 pm
by Magicwand
Violence wrote:Here's a fun one for you all.
A teacher says: I'm thinking of two natural numbers bigger than 1. Try to guess what they are.
The first student knows their product and the other one knows their sum.
First: I do not know the sum.
Second: I knew that. The sum is less than 14.
First: I knew that. However, now I know the numbers.
Second: And so do I.
What were the numbers?
ok ..two numbers are {3,7} i hope i am right
Re: Logical puzzles
Posted: Tue Dec 07, 2010 5:55 pm
by averell
Magicwand wrote:
Violence wrote:Here's a fun one for you all.
A teacher says: I'm thinking of two natural numbers bigger than 1. Try to guess what they are.
The first student knows their product and the other one knows their sum.
First: I do not know the sum.
Second: I knew that. The sum is less than 14.
First: I knew that. However, now I know the numbers.
Second: And so do I.
What were the numbers?
ok ..two numbers are {3,7} i hope i am right
Not quite right.
If it's 3 and 7, the product is 21, and for numbers bigger than 1, 3 and 7 are the only factorization.
So the first student knows from the product also the sum. But he says he doesn't know the sum
Spoiler:
one point of information passed is that sum-guy knows product-guy doesn't know the sum.
Solution:
2 and 9, sum is 11, all possible pairs of summands have non-unique factorization, yet all sums are smaller than 14.
Re: Logical puzzles
Posted: Tue Dec 07, 2010 6:03 pm
by Magicwand
averell wrote:
Not quite right.
If it's 3 and 7, the product is 21, and for numbers bigger than 1, 3 and 7 are the only factorization.
So the first student knows from the product also the sum. But he says he doesn't know the sum
i guess i am really tired and not thinking straight..
also..i guess these things have no corelation with go rank
Re: Logical puzzles
Posted: Thu Dec 09, 2010 6:02 am
by tj86430
HermanHiddema wrote:
daniel_the_smith wrote:
HermanHiddema wrote:
Your program needs to know the prisoners' strategy, just brute forcing all combinations won't help.
Uh... logically their strategy must be a member of the set of all combinations, no? The problem states they can't communicate in any way once the trial starts...
I will add a hint: (this one shows why your brute force strategy doesn't work)
Prisoners do not know, in advance, which 50 boxes they will open.
And another, bigger hint:
Prisoners do know, in advance, which box they will open first.
I would like to see the solution, please. If you don't want to post it here, pm me.
Re: Logical puzzles
Posted: Thu Dec 09, 2010 7:02 am
by HermanHiddema
tj86430 wrote:I would like to see the solution, please. If you don't want to post it here, pm me.
As requested, the solution:
On the evening in advance, the prisoners get together and assign a number (1 through 100) to each prisoner. Each prisoner memorizes the numbers of all prisoners. This means that each box is now virtually marked with a prisoner name on the outside. It also means that the piece of paper in any box can now be seen as a reference to a box. Effectively, the boxes have become a permutation of the numbers 1-100, referencing each other.
The next day, each prisoner enters the room and opens the box with his own number on it. If it contains his name, he's done. If it contains another prisoners name, he next opens that prisoners box. He repeats this procedure, following the references to new boxes, until he has found his name, or until his 50 tries are up.
Each permutation is guaranteed to contain loops, and every box is guaranteed to be part of exactly one loop. The shortest loops are when a box points to itself (loop of length 1) or when two boxes point to each other (length 2). The longest possible loop has length 100 (each box points to a new box, until the 100th box in the sequence points back to the first).
The prisoners all go free if the longest loop in the permutation contains at most 50 boxes. The chance of that is 1 - ln(2), which is about 31.18%
Especially "The prisoners all go free if the longest loop in the permutation contains at most 50 boxes." As far as I can see that is not true - imagine 50 2-box loops. Am I misunderstanding the solution?
Edit after 1 min to clarify:
I think (if I didn't fail at reading :p) that for some reason the solution assumes that the prisoner's name will be in the first loop he selects, and since I can't see how that is true the conclusion doesn't hold.
Re: Logical puzzles
Posted: Thu Dec 09, 2010 9:29 am
by flOvermind
illluck wrote:
I think (if I didn't fail at reading :p) that for some reason the solution assumes that the prisoner's name will be in the first loop he selects, and since I can't see how that is true the conclusion doesn't hold.
Assuming the initial cycle of the prisoner is shorter than 50. What are the prisoners supposed to do after the end of the cycle? Start another cycle at a random box?
That's not a question. That's a hint
Try to go slowly through all the steps again
Re: Logical puzzles
Posted: Thu Dec 09, 2010 9:40 am
by daniel_the_smith
illluck wrote:I'm confused at the solution:
Especially "The prisoners all go free if the longest loop in the permutation contains at most 50 boxes." As far as I can see that is not true - imagine 50 2-box loops. Am I misunderstanding the solution?
Remember that by definition:
A loop contains the prisoner's number. In fact, it is always the last box in the loop.
For much the same reason you always find something in the last place you look...
Re: Logical puzzles
Posted: Thu Dec 09, 2010 9:43 am
by Redundant
Just to chime in, the technical term for what you're calling a loop is an orbit.
Re: Logical puzzles
Posted: Thu Dec 09, 2010 10:30 am
by illluck
Ah, I think I (sort of) understand now. Thanks for the hints!
