Life In 19x19
http://lifein19x19.com/

Logical puzzles
http://lifein19x19.com/viewtopic.php?f=8&t=2434		 Page 5 of 6
Author:  daniel_the_smith [ Sat Dec 04, 2010 8:09 pm ]
Post subject:  Re: Logical puzzles
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...
Author:  daniel_the_smith [ Sat Dec 04, 2010 8:27 pm ]
Post subject:  Re: Logical puzzles
Sample output for N = 4:

Code:
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?
Author:  HermanHiddema [ Sat Dec 04, 2010 8:29 pm ]
Post subject:  Re: Logical puzzles
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.
Author:  ethanb [ Sat Dec 04, 2010 8:52 pm ]
Post subject:  Re: Logical puzzles
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 :lol:


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...
Author:  Violence [ Tue Dec 07, 2010 3:12 pm ]
Post subject:  Re: Logical puzzles
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?
Author:  Magicwand [ Tue Dec 07, 2010 5:44 pm ]
Post subject:  Re: Logical puzzles
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 :)
Author:  averell [ Tue Dec 07, 2010 5:55 pm ]
Post subject:  Re: Logical puzzles
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.
Author:  Magicwand [ Tue Dec 07, 2010 6:03 pm ]
Post subject:  Re: Logical puzzles
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 :)
Author:  tj86430 [ Thu Dec 09, 2010 6:02 am ]
Post subject:  Re: Logical puzzles
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.
Author:  HermanHiddema [ Thu Dec 09, 2010 7:02 am ]
Post subject:  Re: Logical puzzles
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%

Background article: http://www.sciencenews.org/view/generic ... s_in_Boxes
Author:  illluck [ Thu Dec 09, 2010 9:11 am ]
Post subject:  Re: Logical puzzles
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.
Author:  flOvermind [ Thu Dec 09, 2010 9:29 am ]
Post subject:  Re: Logical puzzles
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 :P
Try to go slowly through all the steps again ;)
Author:  daniel_the_smith [ Thu Dec 09, 2010 9:40 am ]
Post subject:  Re: Logical puzzles
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...
Author:  Redundant [ Thu Dec 09, 2010 9:43 am ]
Post subject:  Re: Logical puzzles
Just to chime in, the technical term for what you're calling a loop is an orbit.
Author:  illluck [ Thu Dec 09, 2010 10:30 am ]
Post subject:  Re: Logical puzzles
Ah, I think I (sort of) understand now. Thanks for the hints!
Author:  Bill Spight [ Thu Dec 09, 2010 11:45 am ]
Post subject:  Re: Logical puzzles
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. :)
Author:  Gresil [ Thu Dec 09, 2010 12:09 pm ]
Post subject:  Re: Logical puzzles
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.
Author:  averell [ Thu Dec 09, 2010 4:43 pm ]
Post subject:  Re: Logical puzzles
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.
Author:  robinz [ Thu Dec 09, 2010 4:55 pm ]
Post subject:  Re: Logical puzzles
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.
Author:  Stefany93 [ Fri Dec 10, 2010 12:19 pm ]
Post subject:  Re: Logical puzzles
I guess it will be take me a couple of years to solve it. I didn't know I am so smart :o
Page 5 of 6 All times are UTC - 8 hours [ DST ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/