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!
Re: Logical puzzles
Posted: Thu Dec 09, 2010 11:45 am
by Bill Spight
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?
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.
Hint:
Traverse the loop backwards.
Re: Logical puzzles
Posted: Thu Dec 09, 2010 12:09 pm
by Gresil
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?
My guess is (edit) 5 and 8.
The product has multiple factorizations where neither number is 1, and exactly one of them matches the condition that the sum of the factors is less than 14.
The only way I can pin it down is an exhaustive search.
12: 3*4, 2*6, no 18: 3*6, 2*9, no 20: 4*5, 2*10, no 24: 4*6, 8*3, no 30: 5*6, 10*3, no 36: 4*9, 3*13, perhaps
edit: I looked at Averell's solution. Are you sure it's correct? There's something I'm not getting if it is.
edit 2: whoops, I missed 36 = 6*6.
40: 5*8, 4*10. So it's 5 and 8.
Re: Logical puzzles
Posted: Thu Dec 09, 2010 4:43 pm
by averell
Gresil wrote:
edit: I looked at Averell's solution. Are you sure it's correct? There's something I'm not getting if it is.
I am somewhat sure, i checked my solution and it fits but i'm prone to mistakes calculating in my head. Anyway, in your solution: Second: I knew that. The sum is less than 14. First: I knew that. However, now I know the numbers.
Now, you have 5 and 8, 40 the product, so product guy only knows it's either 2 * 20, 4 * 10, or 8 * 5, but because only 8*5 is less than 14, he is lying when he says he knew that. With 2 * 9 = 3 * 6 both sums are less than 14.
Re: Logical puzzles
Posted: Thu Dec 09, 2010 4:55 pm
by robinz
averell is quite right - 2 and 9 is the solution. (Which I had worked out for myself while away from the forum - I wasn't surprised to see it had been solved by someone else in the meantime )
Basically, 11 is the only number less than 14 for which all pairs which sum to it have a product which has (at least) two different non-trivial factorisations. And, of the pairs which sum to 11, 2 and 9 is the only one for which all possible pairs of factors for the product sum to less than 14.
Re: Logical puzzles
Posted: Fri Dec 10, 2010 12:19 pm
by Stefany93
I guess it will be take me a couple of years to solve it. I didn't know I am so smart
Re: Logical puzzles
Posted: Wed Dec 15, 2010 3:36 am
by entropi
HermanHiddema wrote:
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%
The strategy is pretty clear. Ok I accept, if it works it works
But I still have two problems with it:
1- I still don't get how you calculate 1-ln(2). It is not at all apparent for me that the probability of the longest loop not exceeding 50 is 1-ln(2). But anyway that's pure mathematics. My next problem is more important, which is:
2- Is there a proof that this strategy gives the highest survival probability?
While understanding the strategy and how it works, I must admit that I don't get the feeling of it. Why would creating such a "linked list" maximise the survival probability? Which information do you exploit for increasing the probability?
Re: Logical puzzles
Posted: Wed Dec 15, 2010 4:20 am
by HermanHiddema
entropi wrote:2- Is there a proof that this strategy gives the highest survival probability?
Not that I know of, but obviously I also do not know a better strategy.
While understanding the strategy and how it works, I must admit that I don't get the feeling of it. Why would creating such a "linked list" maximise the survival probability? Which information do you exploit for increasing the probability?
For each individual prisoners, the chance of finding their name has not increased (nor has it decreased). Each prisoner still has 50% chance of finding their name. The strategy just ties them together. So now either all the prisoners in the loop fail, or none of them fail (depending on the loop length). And by doing that, we eliminate the possibility that fewer than 51 prisoners will fail. If the longest loop is at least 51, then all the prisoners in that loop will fail. If the longest is 50 or less, nobody fails. So all the cases of 1,2,3,4,....,47,48,49,50 prisoners failing have suddenly been eliminated.
At the same time, all the cases of 51,52,53,54....,97,98,99,100 prisoners failing have had their chance increased. With a random strategy, the chance of all prisoners failing is as astronomical as all of them succeeding. With this strategy, the chance of all prisoners failing is exactly 1%. Here too, the strategy ties the prisoners together in sharing their fate.
Re: Logical puzzles
Posted: Thu Dec 16, 2010 6:38 pm
by cyclops
entropi wrote: 1- I still don't get how you calculate 1-ln(2). It is not at all apparent for me that the probability of the longest loop not exceeding 50 is 1-ln(2). But anyway that's pure mathematics. My next problem is more important, which is:
Herman is quite pessimistic. His probability of 1 - ln2 is correct in the limit towards infite prisoners. I guess in the finite case at hand the survival chance is exactly 1/2 - 1/3 + 1/4 ...... + 1/100 which is about 0.01 % better than Herman's value. I didn't manage to prove my formula yet. At least I checked it for n =2 and n = 4. When I was trying n = 6 to discover the system, some friends came to visit me unexpectedly, disturbing my cycles. Odysseus' descendents, Cyclops presumed.
Re: Logical puzzles
Posted: Fri Dec 17, 2010 2:49 pm
by cyclops
entropi wrote: 1- I still don't get how you calculate 1-ln(2). It is not at all apparent for me that the probability of the longest loop not exceeding 50 is 1-ln(2). But anyway that's pure mathematics. My next problem is more important, which is:
I'll try to calculate what is the probability that there is one cycle of length 51 exactly if we shuffle the numbers 1 to 100. There are 100! shuffles ( permatutions ). How many contain a 51 cycle? There are 100 over 51 that is 100! / ( 51! * 49! ) ways to divide the numbers in two groups: the 51 cycle group and the rest. The rest can be ordered at 49! different ways. For the 51 cycle we have 50 ways to choose the first element, 49 ways for the second and so on. So from 51 numbers one can realize a 51 cycle in 50! ways. All together, taking quotients and products, the probability is 1/51.
For Herma's problem to get the probability of failing: You repeat this for 51-cycles to 100-cycles and add the probabilities. ( They are exclusive ). So you get: 1/51 + 1/52 + 1/53 + .. .. + 1/100 as the probability for failure. Somehow this sum equals 1 - 1/2 + 1/3 - 1/4 .. + 1/100. And this approaches ln(2). Because ln(1+x) = x - x^2/2 + x^3/3 - x^4/4 ... ( substitute x = 1 )
Re: Logical puzzles
Posted: Fri Dec 17, 2010 4:38 pm
by Redundant
For a derivation of the probability in the prisoner puzzle see wikipedia.
