Two Plus Two Older Archives  

Go Back   Two Plus Two Older Archives > General Gambling > Probability

Reply
 
Thread Tools Display Modes
  #11  
Old 11-18-2005, 08:07 PM
Guest
 
Posts: n/a
Default Re: math riddle: King and His Prisoners (no content, long)

[ QUOTE ]
[ QUOTE ]
[ QUOTE ]
Do the prisioners know what k is?

[/ QUOTE ]

Yes.

[/ QUOTE ]
They know k? Or did you mean n? If it's k, I might just freak out. [img]/images/graemlins/wink.gif[/img]

[/ QUOTE ]

The prisoners know n and k. So does the king.
Reply With Quote
  #12  
Old 11-18-2005, 08:07 PM
Guest
 
Posts: n/a
Default Re: math riddle: King and His Prisoners (no content, long)

Before getting out pencil and pad, I wanted to be certain
the prisoners' pass through the central rooms to their
cells didn't qualify as having been in the room. Your
answer and a re-read eliminate such a solution.

The prisoners know k; do they know n?

Are the chalice and the cup the same object? That is, are
the prisoners and the king manipulating the same object?
Reply With Quote
  #13  
Old 11-18-2005, 08:15 PM
Guest
 
Posts: n/a
Default Re: math riddle: King and His Prisoners (no content, long)

[ QUOTE ]
Are the chalice and the cup the same object? That is, are the prisoners and the king manipulating the same object?

[/ QUOTE ]

Yes, the chalice is the cup. They are one and the same.
Reply With Quote
  #14  
Old 11-18-2005, 08:26 PM
SumZero SumZero is offline
Member
 
Join Date: Jul 2004
Posts: 73
Default Re: math riddle: King and His Prisoners (no content, long)

Take the answer for k=0 (which is the typical problem). Now have each prisoner do what they have do once in the k=0 solution k more times. And have the "special" prisoner change his counting scheme to account for the (k+1)*n chalices. I think that works. There might need to be a tweak since the king can turn the chalice each direction or can not do anything, but I think it is just a wrinkle of what I've (intentionally vaguely) described.
Reply With Quote
  #15  
Old 11-19-2005, 01:52 AM
Guest
 
Posts: n/a
Default Re: math riddle: King and His Prisoners (no content, long)

I thought this post was a joke. I gave up after 30 minutes and said "there is no way you can solve this"

I figured the only solution is something riddle-esque like "they were all in the room in the beginning, so the answer is always Yes" or "the prisoners are siamese n-tuplets" something stupid.

Anyway, I found the solution doing a google search and now I feel like a moron. Nothing like a good puzzle to make you hate yourself.

Great post!
Reply With Quote
  #16  
Old 11-19-2005, 04:13 AM
Luzion Luzion is offline
Junior Member
 
Join Date: Mar 2004
Posts: 2
Default Re: math riddle: King and His Prisoners (no content, long)

Is this even possible? I know of a solution if the King doesnt get to mess with the chalice from a variant of this riddle. But the ability of the King to mess with, or NOT to mess with the chalice seems to make this impossible.
Reply With Quote
  #17  
Old 11-19-2005, 07:02 AM
Guest
 
Posts: n/a
Default Re: math riddle: King and His Prisoners (no content, long)

Since you know the solution when k=0, just alter it slightly...

Given the strategy of the prisoners, understand there is a point when the count will no longer increase for the counter. With k=0 and the sol'n you know, this point is exactly n-1. When k is non-zero there is a lower/upper limit to this count depending on if the king works to increase/decrease/not effect the count. Call the limits on this range [A,B]

So what do we do...well...
For any other k, let the prisoners effect the chalice Y times (for k=0, Y=1), where Y makes the following true:

The lowest possible total count (A) when all n-people have been in the room is greater than the maximum possible total count (B) when fewer than n-people have been in the room.

From here you have some algebra to determine Y. Plus you have a point where the counter can be sure everyone has been in the room.

I hope I worded this correctly...but, yes it is still possible.
Reply With Quote
  #18  
Old 11-19-2005, 10:20 AM
Guest
 
Posts: n/a
Default Re: math riddle: King and His Prisoners (no content, long)

[ QUOTE ]
Is this even possible? I know of a solution if the King doesnt get to mess with the chalice from a variant of this riddle. But the ability of the King to mess with, or NOT to mess with the chalice seems to make this impossible.

[/ QUOTE ]

It is possible, there is a solution. Drizzle is on the right track but hasn't gotten it yet.
Reply With Quote
  #19  
Old 11-19-2005, 11:18 AM
Guest
 
Posts: n/a
Default Re: math riddle: King and His Prisoners (no content, long)

I guess I will add to my previous post.

Break the prisoners into two groups: one counter, and then everyone else (n-1).

The counter follows these rules when called:
1. If the cup is down, do nothing.
2. If the cup is up, flip it down and increment running total.

The (n-1) non-counters do this:
1. If the cup is up, do nothing.
2. If the cup is down, flip it unless you have flipped it Y times already.

We need to find some number where the counter can be certain that everyone has been in the room. If you analyze the strategy you see that the King can use his flips to drive the largest possible count up or down as he sees fit.

We are looking for the condition where all prisoners have been in the room. (1)

The largest count that can exist without (1) being met is A*(n-2) + k. This is all but 1 non-counting prisoner using the max. flips and the King using all of his moves to drive up the count.

When all prisoners have been in the room, the count will lie between [0,A*(n-1)+k] In fact, the count will never increase beyond A*(n-1)+k given the strategy we have defined. Given all of the King's strategies, the smallest UPPER bound is A*(n-1)-k. So the upper bound must lie on [A*(n-1)-k,A*(n-1)+k]

If we can find an A, such that A*(n-1)-k is greater than A*(n-2)+k then we have our solution. Why? Because we have found a count that we are guaranteed to eventually reach that is larger than any count where (1) is not met.

A(n-1)-k > A(n-2) + k
- A - k > - 2A + k
A > 2k
The smallest such A is 2k+1, but any A larger than that will also work.

(2k+1)(n-1) - k = 2kn + n - 3k - 1
When the count reaches '2kn + n - 3k - 1' the counter can say "Yes"
Reply With Quote
  #20  
Old 11-19-2005, 05:49 PM
Guest
 
Posts: n/a
Default Re: math riddle: King and His Prisoners (no content, long)

I'm going to take a stab at this, and I haven't read any of the other posts. First, the prisoners have to appoint a counter. Next, the strategy has to be that the first K+1 times (where K = no. of times the King can touch the chalice) a non-counting prisoner enters the chamber and the chalice is up, they have to put it face down. If they enter the chamber and it's face down, or if they have already changed it to face up K+1 times, the non-counter will not touch the chalice. The counter's job will be to always change the chalice from face down to face up, and to count how many times he's done this. Once he has counted up to K+ N (N = total prisoners), he will know that all of the prisoners have entered the room. The first 1 is necessary because it's possible that the counter will be the first person into the room, and the chalice will start face down.

For example, if the king could mess with the chalice twice, and there were only 3 prisoners (a,b,c) and a was the counter, a possible sequence could go like this:

b enters and chalice is down
a enters, turns chalice up (1)
b enters, turns chalice down (1)
c enters
a enters, turns chalice up (2)
b enters, turns chalice down (2)
King enters, turns chalice up (1)
b enters, turns chalice down (3)
a enters, turns chalice up (3)
c enters, turns chalice down (1)
King enters, turns chalice up (2)
a enters
c enters, turns chalice down (2)
b enters
a enters, turns chalice up (4)
c enters, turns chalice down (3)
a enters, turns chalice up (5), and tells the king they've all been to the room.
Reply With Quote
Reply

Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump


All times are GMT -4. The time now is 08:09 AM.


Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2024, vBulletin Solutions Inc.