It is currently Sun May 04, 2025 8:54 pm

View unanswered posts | View active topics View unread posts | View new posts | View your posts


Board index » Life In 19x19.com General Topics » Off Topic

All times are UTC - 8 hours [ DST ]



Post new topic Reply to topic  Page 5 of 6
  [ 108 posts ]  Go to page Previous  1, 2, 3, 4, 5, 6  Next
  Print view Previous topic | Next topic 
Author Message
Offline daniel_the_smith
 Post subject: Re: Logical puzzles
Post #81 Posted: Sat Dec 04, 2010 8:09 pm 
Gosei
User avatar

Posts: 2116
Location: Silicon Valley
Liked others: 152
Was liked: 330
Rank: 2d AGA
GD Posts: 1193
KGS: lavalamp
Tygem: imapenguin
IGS: lavalamp
OGS: 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...

_________________
That which can be destroyed by the truth should be.
--
My (sadly neglected, but not forgotten) project: http://dailyjoseki.com
Top
 Profile  
 
Offline daniel_the_smith
 Post subject: Re: Logical puzzles
Post #82 Posted: Sat Dec 04, 2010 8:27 pm 
Gosei
User avatar

Posts: 2116
Location: Silicon Valley
Liked others: 152
Was liked: 330
Rank: 2d AGA
GD Posts: 1193
KGS: lavalamp
Tygem: imapenguin
IGS: lavalamp
OGS: daniel_the_smith
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?

_________________
That which can be destroyed by the truth should be.
--
My (sadly neglected, but not forgotten) project: http://dailyjoseki.com
Top
 Profile  
 
Offline HermanHiddema
 Post subject: Re: Logical puzzles
Post #83 Posted: Sat Dec 04, 2010 8:29 pm 
Gosei
User avatar

Posts: 2011
Location: Groningen, NL
Liked others: 202
Was liked: 1087
Rank: Dutch 4D
GD Posts: 645
Universal go server handle: herminator
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.
Top
 Profile  
 
Offline ethanb
 Post subject: Re: Logical puzzles
Post #84 Posted: Sat Dec 04, 2010 8:52 pm 
Lives in gote

Posts: 355
Liked others: 52
Was liked: 43
Rank: AGA 2d
IGS: 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...
Top
 Profile  
 
Offline Violence
 Post subject: Re: Logical puzzles
Post #85 Posted: Tue Dec 07, 2010 3:12 pm 
Lives in sente

Posts: 754
Liked others: 9
Was liked: 144
Rank: Something Dan
GD Posts: 720
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?
Top
 Profile  
 
Offline Magicwand
 Post subject: Re: Logical puzzles
Post #86 Posted: Tue Dec 07, 2010 5:44 pm 
Tengen
User avatar

Posts: 4844
Location: Mechanicsburg, PA
Liked others: 62
Was liked: 505
Rank: Wbaduk 7D
KGS: magicwand
Tygem: magicwand
Wbaduk: rlatkfkd
DGS: magicwand
OGS: 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 :)

_________________
"The more we think we know about
The greater the unknown"
Words by neil peart, music by geddy lee and alex lifeson
Top
 Profile  
 
Offline averell
 Post subject: Re: Logical puzzles
Post #87 Posted: Tue Dec 07, 2010 5:55 pm 
Dies in gote

Posts: 61
Liked others: 57
Was liked: 19
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.
Top
 Profile  
 
Offline Magicwand
 Post subject: Re: Logical puzzles
Post #88 Posted: Tue Dec 07, 2010 6:03 pm 
Tengen
User avatar

Posts: 4844
Location: Mechanicsburg, PA
Liked others: 62
Was liked: 505
Rank: Wbaduk 7D
KGS: magicwand
Tygem: magicwand
Wbaduk: rlatkfkd
DGS: magicwand
OGS: 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 :)

_________________
"The more we think we know about
The greater the unknown"
Words by neil peart, music by geddy lee and alex lifeson
Top
 Profile  
 
Offline tj86430
 Post subject: Re: Logical puzzles
Post #89 Posted: Thu Dec 09, 2010 6:02 am 
Gosei

Posts: 1348
Location: Finland
Liked others: 49
Was liked: 129
Rank: FGA 7k GoR 1297
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.

_________________
Offending ad removed
Top
 Profile  
 
Offline HermanHiddema
 Post subject: Re: Logical puzzles
Post #90 Posted: Thu Dec 09, 2010 7:02 am 
Gosei
User avatar

Posts: 2011
Location: Groningen, NL
Liked others: 202
Was liked: 1087
Rank: Dutch 4D
GD Posts: 645
Universal go server handle: herminator
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
Top
 Profile  
 
Offline illluck
 Post subject: Re: Logical puzzles
Post #91 Posted: Thu Dec 09, 2010 9:11 am 
Lives in sente

Posts: 1223
Liked others: 738
Was liked: 239
Rank: OGS 2d
KGS: illluck
Tygem: Trickprey
OGS: 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.
Top
 Profile  
 
Offline flOvermind
 Post subject: Re: Logical puzzles
Post #92 Posted: Thu Dec 09, 2010 9:29 am 
Lives with ko
User avatar

Posts: 295
Location: Linz, Austria
Liked others: 21
Was liked: 44
Rank: EGF 4 kyu
GD Posts: 627
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 ;)
Top
 Profile  
 
Offline daniel_the_smith
 Post subject: Re: Logical puzzles
Post #93 Posted: Thu Dec 09, 2010 9:40 am 
Gosei
User avatar

Posts: 2116
Location: Silicon Valley
Liked others: 152
Was liked: 330
Rank: 2d AGA
GD Posts: 1193
KGS: lavalamp
Tygem: imapenguin
IGS: lavalamp
OGS: 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...

_________________
That which can be destroyed by the truth should be.
--
My (sadly neglected, but not forgotten) project: http://dailyjoseki.com
Top
 Profile  
 
Offline Redundant
 Post subject: Re: Logical puzzles
Post #94 Posted: Thu Dec 09, 2010 9:43 am 
Lives in sente
User avatar

Posts: 924
Location: Pittsburgh
Liked others: 45
Was liked: 103
Rank: lazy
KGS: redundant/silchas
Tygem: redundant
Wbaduk: redundant
DGS: redundant
OGS: redundant
Just to chime in, the technical term for what you're calling a loop is an orbit.
Top
 Profile  
 
Offline illluck
 Post subject: Re: Logical puzzles
Post #95 Posted: Thu Dec 09, 2010 10:30 am 
Lives in sente

Posts: 1223
Liked others: 738
Was liked: 239
Rank: OGS 2d
KGS: illluck
Tygem: Trickprey
OGS: illluck
Ah, I think I (sort of) understand now. Thanks for the hints!
Top
 Profile  
 
Offline Bill Spight
 Post subject: Re: Logical puzzles
Post #96 Posted: Thu Dec 09, 2010 11:45 am 
Honinbo

Posts: 10905
Liked others: 3651
Was liked: 3374
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. :)

_________________
The Adkins Principle:
At some point, doesn't thinking have to go on?
— Winona Adkins

Visualize whirled peas.

Everything with love. Stay safe.
Top
 Profile  
 
Offline Gresil
 Post subject: Re: Logical puzzles
Post #97 Posted: Thu Dec 09, 2010 12:09 pm 
Lives with ko
User avatar

Posts: 206
Location: Finland
Liked others: 29
Was liked: 9
Rank: mid-SDK
GD Posts: 495
KGS: 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.

_________________
So you've got an eye?
That don't impress me much
Top
 Profile  
 
Offline averell
 Post subject: Re: Logical puzzles
Post #98 Posted: Thu Dec 09, 2010 4:43 pm 
Dies in gote

Posts: 61
Liked others: 57
Was liked: 19
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.
Top
 Profile  
 
Offline robinz
 Post subject: Re: Logical puzzles
Post #99 Posted: Thu Dec 09, 2010 4:55 pm 
Lives in gote

Posts: 414
Location: Durham, UK
Liked others: 96
Was liked: 15
Rank: KGS 9k
KGS: 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.
Top
 Profile  
 
Offline Stefany93
 Post subject: Re: Logical puzzles
Post #100 Posted: Fri Dec 10, 2010 12:19 pm 
Lives with ko
User avatar

Posts: 248
Location: Arkansas, USA
Liked others: 193
Was liked: 21
Rank: KGS 8k
KGS: Azumi93
Online playing schedule: When I am in a mood for Go :D
I guess it will be take me a couple of years to solve it. I didn't know I am so smart :o

_________________
Stefany, web programmer
Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  Page 5 of 6
  [ 108 posts ]  Go to page Previous  1, 2, 3, 4, 5, 6  Next

Board index » Life In 19x19.com General Topics » Off Topic

All times are UTC - 8 hours [ DST ]

Who is online

Users browsing this forum: No registered users and 1 guest

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group