Author |
Topic: Criminal Cupbearers Variant (Read 4588 times) |
|
ChunkTug
Full Member
Gender: 
Posts: 166
|
 |
Criminal Cupbearers Variant
« on: May 19th, 2006, 1:37pm » |
 Quote  Modify
|
A variant on the original Criminal Cupbearers was asked recently. (Note: It's funny how often activity in this forum is paralelled by activity on the riddle threads at work).
If 2 bottles of the 1000 are poisoned, what's the minimum number of prisoners required to determine the poisoned bottles? Can we generalize to N bottles, K of which are poisoned?
I do not have an answer to this.
The discussion for the original puzzle can be found in this thread.
|
|
 IP Logged |
|
|
|
alien
Guest
|
|
Re: Criminal Cupbearers Variant
« Reply #1 on: May 19th, 2006, 3:29pm » |
Quote Modify
 Remove
|
In any possible realization, I'd say 2.
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Criminal Cupbearers Variant
« Reply #2 on: May 19th, 2006, 7:40pm » |
Quote Modify
|
I believe he means the minimum number of prisoners to be assured the bottles will be identitified within 5 weeks.
Because each prisoner can only give you a single bit of information (he either lives or dies, and even if he lives, by the time you are sure, it is too late to have him test another bottle), I think that the best you can hope for from each prisoner by himself is to halve the number of suspect bottles. If I am correct, then the minimum number of prisoners needed is Ceiling(log2 (N/K)).
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Criminal Cupbearers Variant
« Reply #3 on: May 20th, 2006, 3:34am » |
Quote Modify
|
on May 19th, 2006, 7:40pm, Icarus wrote:| If I am correct, then the minimum number of prisoners needed is Ceiling(log2[/sub] (N/K)). |
|
I don't think you are correct. Consider 1000 bottles, 999 of which are poisoned. You will need 999 prisoners to find the one that isn't poisoned, because any prisoner tasting from two or more bottles dies.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: Criminal Cupbearers Variant
« Reply #4 on: May 20th, 2006, 9:49am » |
Quote Modify
|
Quick information theoretic argument says that you'd need at least 19 prisoners...
there are just short of half a million possible pairs of bottles, so to get that many possible outcomes with each prisoner only having two possible actions (live or die) you need 19.
Though I haven't yet found a coding that lets you meet that bound.
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Criminal Cupbearers Variant
« Reply #5 on: May 21st, 2006, 1:00pm » |
Quote Modify
|
Honest, I meant Ceiling(log2 C(N,K)). Really, I did. It was just, uhmm, a typo. yeah, that's it, it was a typo. 
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Criminal Cupbearers Variant
« Reply #6 on: May 21st, 2006, 2:15pm » |
Quote Modify
|
As a lower limit you mean?
Because it still doesn't work for finding the single non-poisoned bottle. There is an asymmetry there, because well, dead is dead, no matter how often you're poisoned.
Perhaps it'd be insightfull to start with fewer bottles, say 10 or 20 or so. I'd think that for increasing K you'd need (weakly) increasingly more prisoners up untill K=N, when obviously you don't need any.
|
| « Last Edit: May 21st, 2006, 2:21pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
chetangarg
Newbie
Gender:
Posts: 30
|
|
Re: Criminal Cupbearers Variant
« Reply #7 on: Oct 22nd, 2007, 12:34am » |
Quote Modify
|
on May 19th, 2006, 1:37pm, ChunkTug wrote:
I do not have an answer to this.. |
|
I still don't find any answer to this variant..
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Criminal Cupbearers Variant
« Reply #8 on: Oct 22nd, 2007, 1:30am » |
Quote Modify
|
It evokes my memeories to problem I was solving in my 17 (21 years ago).
How many measuring is required to find two radioactive balls among n of otherwise indistinguishable balls. (You take a set of balls and detect whether there is a radioactivity in the set).
I have spent a lot of time trying to solve the problem exactly ... no success.
Only lower and upper bounds were established.
I dont thing the parallel problem is less comlplex. 
|
| « Last Edit: Oct 22nd, 2007, 1:32am by Hippo » |
IP Logged |
|
|
|
dfeuer
Newbie
Gender:
Posts: 5
|
|
Re: Criminal Cupbearers Variant
« Reply #9 on: Oct 25th, 2007, 2:16pm » |
Quote Modify
|
on Oct 22nd, 2007, 1:30am, Hippo wrote:It evokes my memeories to problem I was solving in my 17 (21 years ago).
How many measuring is required to find two radioactive balls among n of otherwise indistinguishable balls. (You take a set of balls and detect whether there is a radioactivity in the set).
I have spent a lot of time trying to solve the problem exactly ... no success.
Only lower and upper bounds were established.
I dont thing the parallel problem is less comlplex. |
|
I'll take a crack at the radioactive ball problem, starting with a restricted version. Suppose you have 2 balls (k>0), 2 of them radioactive. Divide them in two groups of 2k-1. Either both radioactive balls will be in the same group, or one will be in each. If both are in the same group, the problem reduces to the same one with 2k-1 balls. Otherwise it reduces to two copies of the problem with one radioactive ball. In the worst case, the first trial places one ball in each group of 2k-1 balls. To find the radioactive ball in each group requires k-1 trials. So for the worst case, you need a total of 1+2(k-1)= 2k-1 trials.
Now get rid of the restriction, assuming n balls, and divide them in each step as evenly as possible into two. The worst case is the same: the two radioactive balls are initially put in different groups, and you are left with two one-radioactive-ball problems. So consider the problem of q balls, one of them radioactive. If we always divide as evenly as possible, the worst case will occur when the ball is always in the larger group. I'm not sure how to give a formula for this, but the calculation itself is easy.
The average case is left as an exercise for the reader :-P
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Criminal Cupbearers Variant
« Reply #10 on: Oct 26th, 2007, 7:55am » |
Quote Modify
|
OK, the algorithm works, it gives upper bound around (2log n) for the best searching algorithm for 2 radioactive balls (lower bound log n is obvious).
I am rather sure this is not the best algorithm.
As the answer not radioactive is twice more valuable in your algorithm than radioactive, I would cut only golden ratio of balls and measure it (smaller part) ... just an idea to be computed well.
OK let me continue ... let g=(\sqrt(5)-1)/2 be the goldon ratio. If n is the number of starting balls, measure n.g^2. If not radioactive, you start with n.g. If radioactive, you have 2 groups of sizes n.g^2 and n.g. Measure g^2 part of both groups in one measuring. If not radioactive ... sizes decrease by factor g. If radioactive ... you obtain 4 groups of sizes ones n.g^4, twice n.g^3 and once n.g^2 ... continue. At the end try to use all known results of measurments before you finaly find one radioactive ball. Then consider measurements where this ball was not measured...
Complexity? Let d=log n/-2log g. After 2d steps, there will be groups of 1 element, each marked by a string of was measured as radioactive, was not measured in radioactive measurement, (was measured as not radioactive are discarded, was not measured in non radioactive measurement are not interesting as the rest is discarded) marks.
Groups can be measured in system that each group (ball) is marked with at least d-times not measured mark.
The worst case is when all measurement reults were radioactive.
(Marks of all 4 kinds can be obtained in parallel in the original puzzle).
.... and what now?? ... how to continue with the algorithm??
As the yes result makes more problems, the optimal measured part should be a bit smaller than n.g^2.
|
| « Last Edit: Oct 27th, 2007, 6:57am by Hippo » |
IP Logged |
|
|
|
dfeuer
Newbie
Gender:
Posts: 5
|
|
Re: Criminal Cupbearers Variant
« Reply #11 on: Oct 26th, 2007, 9:29pm » |
Quote Modify
|
on Oct 26th, 2007, 7:55am, Hippo wrote:OK, the algorithm works, it gives upper bound around (2log n) for the best searching algorithm for 2 radioactive balls (lower bound log n is obvious).
I am rather sure this is not the best algorithm. |
|
I haven't read through your algorithm yet, but you seem to have caught me in an error... I didn't think about the fact that each division in my algorithm requires two measurements.
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Criminal Cupbearers Variant
« Reply #12 on: Oct 27th, 2007, 6:54am » |
Quote Modify
|
Actualy I am thinking about this reformulation of the original problem:
Establishing n words of bits of length l in a pattern such that any pair (k) of words when ored gives different result. What is the maximal number n of such words for given word length l? I am not sure the golden ratio of set to unset bits in a word is the best strategy.
For l=3 n=4 (000,001,010,100) (and your algorithm for n=4 makes 4 measurements ... with pattern for the worst run 1010,1000,0101,0100).
First nontrivial (n>l+1) pattern I have found is for l=8 n=11. For this case in serial puzzle there is solution even for n=17 (above mentioned algorithm by dfeuer). For serial puzzle one can modify the condition for bit strings ... unions of pairs can coincide, but the number of pairs in a collision should be bounded by a small "constant". In the second phase the pair is located by algorithm depending on the results from the first phase ... this allows us to find 2 from 22 in 7+2 measurements (l=7, 0 and 2 set bit numbers, conflicts of size 3). But for the serial 2 from 25 case we can start with measuring 8 reducing the problem either to 2 from 17 in 8 rounds or finding one radioactive in 4 rounds and reduce the problem to find one in 24 in 5 rounds.
I have said it's difficult puzzle 
For serial case - the solution with finding one radioactive ball first and than the other seems to be more effective than mixed measuring at least for small n, n>4 ... 2k measurements can find 2 among 2^k+1 starting either with number of balls between 2^{k-2} and 2^{k-1}. 2k+1 measurements can find 2 among 2^k+2^{k-1}+1 starting with 2^{k-1}. Can for any k some system of "parallel" tests improve the bound from 2^k+1 for 2k measurements to say 2^k+2?
And the answer is yes ... for n=2^3+2^2+2^0+1=14 measure 5:
If yes ... known situation ... 7 measurements alltogether.
If not ... measure 1 measured and 4 new balls:
If yes ... known situation ... 9 balls with first measurement 4 yes ... 7 measurements alltogether.
If not ... measure the 1 ball measured twice:
If yes ... find remaining 1 among 13 balls ... 3+4=7 measurements.
If not ... there are 2 groups of size 4 in each of them find 1 ... 3+2+2=7 measurements.
This was "first order" trick ... and for n=19 we can now start either with 5 or 6 balls, reducing to known problem of at least 14 balls for answer no.
With answer yes you have at least 6 balls one of them radioactive increase the group to size 6 arbitrary and call resulting balls measured. Measure 1 of them and 4 nonmeasured balls.
Answer no reduces the problem to previous one (14 balls, 5 of them measured as radioactive).
For the answer yes you have 1 ball measured twice and groups of 5 resp. 4 balls measured once. Measure the 1 ball and if the answer is yes, locate 1 in 18 in 5 measurement ... 2+1+5=8. If the answer is no, locate 1 in 5 and 1 in 4 ... 2+1+3+2=8 measurements.
|
| « Last Edit: Oct 31st, 2007, 5:05am by Hippo » |
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Criminal Cupbearers Variant
« Reply #13 on: Oct 29th, 2007, 12:18pm » |
Quote Modify
|
on Oct 27th, 2007, 6:54am, Hippo wrote:| Establishing n words of bits of length l in a pattern such that any pair (k) of words when ored gives different result. What is the maximal number n of such words for given word length l? |
|
An exhaustive search of the first few gave me enough terms to find Sloane's A054962, which leads to Sloane's A054961 -- not so helpful for 1000 bottles, but it's a start. 
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Criminal Cupbearers Variant
« Reply #14 on: Oct 30th, 2007, 5:12am » |
Quote Modify
|
Hmm, a lot of patterns I didn't find ... the resulting algorithm of complexity 2^\Omega(l)Cn(l).n(l)^2 will find them ... not too practical even when n(l) grows slowly exponentialy.
I hoped the patterns can be described easier.
|
|
IP Logged |
|
|
|
dfeuer
Newbie
Gender:
Posts: 5
|
|
Re: Criminal Cupbearers Variant
« Reply #15 on: Nov 1st, 2007, 1:01pm » |
Quote Modify
|
on Oct 27th, 2007, 6:54am, Hippo wrote:Actualy I am thinking about this reformulation of the original problem:
Establishing n words of bits of length l in a pattern such that any pair (k) of words when ored gives different result. What is the maximal number n of such words for given word length l? I am not sure the golden ratio of set to unset bits in a word is the best strategy.
|
|
I'm having trouble understanding how this is equivalent.
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Criminal Cupbearers Variant
« Reply #16 on: Nov 2nd, 2007, 2:58am » |
Quote Modify
|
For l parallel measuring (wine bottles):
We are trying to create n bottle etiquettes where bit 1 on position i represents present in potion for i-th prisoner, bit 0 represents the opposite.
Dying prisoners pattern is or of the two bottle etiquettes. We want to prepare etiquettes in the way the dying pattern uniquely identifies the bottles.
[edit]etiquettes spelling[/edit]
|
| « Last Edit: Nov 6th, 2007, 12:16am by Hippo » |
IP Logged |
|
|
|
dfeuer
Newbie
Gender:
Posts: 5
|
|
Re: Criminal Cupbearers Variant
« Reply #17 on: Nov 4th, 2007, 3:27pm » |
Quote Modify
|
on Nov 2nd, 2007, 2:58am, Hippo wrote:For l parallel measuring (wine bottles):
We are trying to create n bottle etticets where bit 1 on postion i represents present in potion for i-th prisoner, bit 0 represents the opposite.
Dying prisoners pattern is or of the two bottle etticets. We want to prepare etticets in the way the dying pattern uniquely identifies the bottles. |
|
I'm sorry? I don't understand what you mean here. What is an etticet? Were you drinking some of those bottles of wine when you posted this response?
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Criminal Cupbearers Variant
« Reply #18 on: Nov 5th, 2007, 12:16am » |
Quote Modify
|
OK, OK .... etiquette ... I guessed the spelling wrongly. Sorry ... this is what can happen when you use uncommon words in foreign language.
BTW: I have never been drunken.
on Nov 5th, 2007, 5:45pm, dfeuer wrote:| Sorry, I didn't realize English wasn't your native language. |
|
No problem, thanks 
|
| « Last Edit: Nov 5th, 2007, 11:02pm by Hippo » |
IP Logged |
|
|
|
dfeuer
Newbie
Gender:
Posts: 5
|
|
Re: Criminal Cupbearers Variant
« Reply #19 on: Nov 5th, 2007, 5:45pm » |
Quote Modify
|
Sorry, I didn't realize English wasn't your native language.
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Criminal Cupbearers Variant
« Reply #20 on: Nov 10th, 2007, 9:46am » |
Quote Modify
|
on Oct 29th, 2007, 12:18pm, SMQ wrote:
BTW: For how long labels did you search? 5,6,7 or even 8? What were the running times (roughly). Thanks.
|
| « Last Edit: Nov 10th, 2007, 9:46am by Hippo » |
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Criminal Cupbearers Variant
« Reply #21 on: Nov 12th, 2007, 10:18am » |
Quote Modify
|
on Nov 10th, 2007, 9:46am, Hippo wrote:| BTW: For how long labels did you search? 5,6,7 or even 8? What were the running times (roughly). Thanks. |
|
My search used the fact that, given a set S of values such that any pair of values produces a unique value under OR, any subset of S also has that property; therefore, given all such sets with n values, every such set with n+1 values must be a superset of one of the given sets. This gives a tree of partial results, with the deepest leaves being the desired maximal sets.
I defined a "unique" partial solution to be a set of values such that any pair of values produces a unique value under OR, and that it is the lexicographically least such set resulting from any permutation of the bits of the values. Thus {000, 001, 110} is a unique partial solution, but {000, 010, 101} is not because swapping the two rightmost bits of every value yields a lexicographically lesser set. For each number of bits, I then performed a depth-first search of all unique partial solutions. Having thus discovered the "unique" solutions with maximal number of values, I generated all bit-permutations to find the number of distinct solutions.
My original program, with less aggressive pruning, was doing a breadth-first search, and ran out of memory working on the 7-bit sets. The first six terms were what I used to find the sequence in Sloane's.
Approximate runtimes for my final program were as follows (on a 3.2 GHz P4):
1 to 6 bits: under a second
7 bits: 20 seconds
8 bits: 9 hours
9 bits: estimated at several hundred years
--SMQ
|
| « Last Edit: Nov 12th, 2007, 10:55am by SMQ » |
IP Logged |
--SMQ
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Criminal Cupbearers Variant
« Reply #22 on: Nov 13th, 2007, 12:49am » |
Quote Modify
|
on Nov 12th, 2007, 10:18am, SMQ wrote:
8 bits: 9 hours
9 bits: estimated at several hundred years
--SMQ |
|
I have expected 7 ... to be several hours and 8 ... several days
Well done, so you have proved what was only expected in Sloan's ... the term for 8 bits.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print