wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Criminal Cupbearers Variant
        
(Message started by: ChunkTug on May 19^th, 2006, 1:37pm)

Title: Criminal Cupbearers Variant
Post by ChunkTug on May 19^th, 2006, 1:37pm

A variant on the original Criminal Cupbearers (http://www.ocf.berkeley.edu/~wwu/riddles/hard.shtml#criminalCupbearers) 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 (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1027806173).

Title: Re: Criminal Cupbearers Variant
Post by alien on May 19^th, 2006, 3:29pm

In any possible realization, I'd say 2.

Title: Re: Criminal Cupbearers Variant
Post by Icarus on May 19^th, 2006, 7:40pm

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(log₂ (N/K)).

Title: Re: Criminal Cupbearers Variant
Post by towr on May 20^th, 2006, 3:34am

on 05/19/06 at 19:40:58, 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.

Title: Re: Criminal Cupbearers Variant
Post by rmsgrey on May 20^th, 2006, 9:49am

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.

Title: Re: Criminal Cupbearers Variant
Post by Icarus on May 21^st, 2006, 1:00pm

Honest, I meant Ceiling(log₂ C(N,K)). Really, I did. It was just, uhmm, a typo. yeah, that's it, it was a typo. :P

Title: Re: Criminal Cupbearers Variant
Post by towr on May 21^st, 2006, 2:15pm

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.

Title: Re: Criminal Cupbearers Variant
Post by chetangarg on Oct 22^nd, 2007, 12:34am

on 05/19/06 at 13:37:55, ChunkTug wrote:

I do not have an answer to this..

I still don't find any answer to this variant..

Title: Re: Criminal Cupbearers Variant
Post by Hippo on Oct 22^nd, 2007, 1:30am

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

Title: Re: Criminal Cupbearers Variant
Post by dfeuer on Oct 25^th, 2007, 2:16pm

on 10/22/07 at 01:30:50, Hippo wrote:

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 2^k-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 2^k-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 2^k-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

Title: Re: Criminal Cupbearers Variant
Post by Hippo on Oct 26^th, 2007, 7:55am

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.

Title: Re: Criminal Cupbearers Variant
Post by dfeuer on Oct 26^th, 2007, 9:29pm

on 10/26/07 at 07:55:21, Hippo wrote:

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.

Title: Re: Criminal Cupbearers Variant
Post by Hippo on Oct 27^th, 2007, 6:54am

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.

Title: Re: Criminal Cupbearers Variant
Post by SMQ on Oct 29^th, 2007, 12:18pm

on 10/27/07 at 06:54:05, 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 (http://www.research.att.com/~njas/sequences/A054962), which leads to Sloane's A054961 (http://www.research.att.com/~njas/sequences/A054961) -- not so helpful for 1000 bottles, but it's a start. ;)

--SMQ

Title: Re: Criminal Cupbearers Variant
Post by Hippo on Oct 30^th, 2007, 5:12am

Hmm, a lot of patterns I didn't find ... the resulting algorithm of complexity _2^\Omega(l)C_n(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.

Title: Re: Criminal Cupbearers Variant
Post by dfeuer on Nov 1^st, 2007, 1:01pm

on 10/27/07 at 06:54:05, Hippo wrote:

I'm having trouble understanding how this is equivalent.

Title: Re: Criminal Cupbearers Variant
Post by Hippo on Nov 2^nd, 2007, 2:58am

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]

Title: Re: Criminal Cupbearers Variant
Post by dfeuer on Nov 4^th, 2007, 3:27pm

on 11/02/07 at 02:58:19, 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?

Title: Re: Criminal Cupbearers Variant
Post by Hippo on Nov 5^th, 2007, 12:16am

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 11/05/07 at 17:45:28, dfeuer wrote:

Sorry, I didn't realize English wasn't your native language.

No problem, thanks ;D

Title: Re: Criminal Cupbearers Variant
Post by dfeuer on Nov 5^th, 2007, 5:45pm

Sorry, I didn't realize English wasn't your native language.

Title: Re: Criminal Cupbearers Variant
Post by Hippo on Nov 10^th, 2007, 9:46am

on 10/29/07 at 12:18:24, SMQ wrote:

BTW: For how long labels did you search? 5,6,7 or even 8? What were the running times (roughly). Thanks.

Title: Re: Criminal Cupbearers Variant
Post by SMQ on Nov 12^th, 2007, 10:18am

on 11/10/07 at 09:46:04, 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

Title: Re: Criminal Cupbearers Variant
Post by Hippo on Nov 13^th, 2007, 12:49am

on 11/12/07 at 10:18:40, 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.