Logical puzzles

[daniel_the_smith]

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

[daniel_the_smith]

Sample output for N = 4:

Code: Select all

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?

[HermanHiddema]

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.

[ethanb]

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

[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?

[Magicwand]

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

[averell]

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.

[Magicwand]

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

[tj86430]

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.

[HermanHiddema]

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%

Background article: http://www.sciencenews.org/view/generic ... s_in_Boxes

[illluck]

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?

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.

[flOvermind]

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

[daniel_the_smith]

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

[Redundant]

Just to chime in, the technical term for what you're calling a loop is an orbit.

[illluck]

Ah, I think I (sort of) understand now. Thanks for the hints!