Life In 19x19

Life in 19x19. Go, Weiqi, Baduk... Thats the life.
https://lifein19x19.com/

Logical puzzles

https://lifein19x19.com/viewtopic.php?t=2434

Page 6 of 8

Re: Logical puzzles

Posted: Fri Dec 03, 2010 3:10 pm
by cyclops
I am getting confused so I close my topic ;)

Re: Logical puzzles

Posted: Fri Dec 03, 2010 3:11 pm
by cyclops
I am getting more confused so I close my topic once more ;)

Re: Logical puzzles

Posted: Sat Dec 04, 2010 1:39 pm
by daniel_the_smith
HermanHiddema wrote:Not really a hint, but a more an additional piece of information, regarding the cruel bandit puzzle:

The right strategy will make their probability of all surviving:

Greater than 30%


Can you double-check the problem statement? :scratch: It was driving me nuts, so I've written a program to brute force it (obviously only for small values of N) and it has not come up with anything better than what people have proposed so far. I'm going to extend my program to try a random sampling of the permutations for larger values of N (using some subset of possible choices), but I don't expect it to come up with anything new.

For N = 4, 6, or 8 (instead of 100) the first N/2 prisoners should open the first N/2 boxes; the second half of the prisoners open the rest of the boxes.

For N=4, the prisoners survive ~16% of the time, for N=6 it's ~3.3% of the time, for N=8 it's ~1.4%. I will let it do N=10 here in a minute but I expect that to take a while.

EDIT: corrected n=6 above. Also, I realized I didn't let N=8 run to completion, there are ~37771564359352320000000 combination so that won't be happening any time soon. It happens that (what I believe to be) the best case gets examined almost immediately, so I believe the number above is correct anyway.

Re: Logical puzzles

Posted: Sat Dec 04, 2010 7:21 pm
by HermanHiddema
daniel_the_smith wrote:Can you double-check the problem statement? :scratch:


I've reread it, and the problem statement is correct.

It was driving me nuts, so I've written a program to brute force it (obviously only for small values of N) and it has not come up with anything better than what people have proposed so far. I'm going to extend my program to try a random sampling of the permutations for larger values of N (using some subset of possible choices), but I don't expect it to come up with anything new.

For N = 4, 6, or 8 (instead of 100) the first N/2 prisoners should open the first N/2 boxes; the second half of the prisoners open the rest of the boxes.

For N=4, the prisoners survive ~16% of the time, for N=6 it's ~3.3% of the time, for N=8 it's ~1.4%. I will let it do N=10 here in a minute but I expect that to take a while.

EDIT: corrected n=6 above. Also, I realized I didn't let N=8 run to completion, there are ~37771564359352320000000 combination so that won't be happening any time soon. It happens that (what I believe to be) the best case gets examined almost immediately, so I believe the number above is correct anyway.


Your program needs to know the prisoners' strategy, just brute forcing all combinations won't help.

Re: Logical puzzles

Posted: Sat Dec 04, 2010 7:35 pm
by Bill Spight
SpongeBob wrote:Since lightvector's puzzle seems to be more of a math puzzle than a logical one, let me provide one more. (Herman's puzzle is too hard for me.)

You like simple looking puzzles that turn out to be nerve-wracking? Those that keep your head real busy and make you feel stupid? Here you go:

The teacher tells his kids: "We are going to write a test next week. On the day before the test, you will not know that you will write the test on the following day."

Now Bill thinks: If only I knew for what day the test has been scheduled. Well, it can't be Friday. As this is the last day of the week, we would know on Thursay that the test will be written the following day. It can't be scheduled for Friday, it must be either Monday, Tuesday, Wednesday or Thursday. Could it be scheduled for Thursday then? Well, then we would know on Wednesday, because we already found out it can't be Friday. So Thursday is out, too. With the same logic, Bill rules out all the other days of the week.

What's going on here? Is there a flaw in Bill's reasoning or does the teacher not tell the truth, or what?


The teacher is lying.

But that does not mean that the teacher is not telling the truth. ;)

Re: Logical puzzles

Posted: Sat Dec 04, 2010 8:09 pm
by daniel_the_smith
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...

Re: Logical puzzles

Posted: Sat Dec 04, 2010 8:27 pm
by 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?

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

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%

Background article: http://www.sciencenews.org/view/generic ... s_in_Boxes
All times are UTC-07:00
Page 6 of 8

Powered by phpBB® Forum Software © phpBB Limited