Author |
Topic: biggest N for 2 radioactive coins (Read 3476 times) |
|
inexorable
Full Member
Posts: 211
|
 |
biggest N for 2 radioactive coins
« on: Oct 31st, 2007, 1:30pm » |
 Quote  Modify
|
You have N coins, 2 of them are radioactive. You have a radioactivity detector which can test any amount of coins at a time, and return the number of radioactive coins in the group (i.e. it returns 0, 1 or 2).You have to find the radioactive coins, using not more than 10 tests. What is the biggest N for which it's possible?
PS:- Excuse me if this has been already discussed. I coud not find a post on this.
|
|
 IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender: 
Posts: 919
|
|
Re: biggest N for 2 radioactive coins
« Reply #1 on: Oct 31st, 2007, 2:26pm » |
Quote Modify
|
I don't think so that the variant with detector returning the number of radioactive coins was discussed.
In this case measuring x coins is as valuable as measuring N-x coins (its complement).
First (not so bad ) attempt:
| hidden: |
If we number the coins in binary and in i-th measuring measure those with 1 in i-th bit, the less information we obtain with all results are 1 and than we know after log2 N measurings the solution is pair (k, bitneg k) (remove the bits that were determined by 0 or 2 answers).
Finding this pair requires at most log3 (N/2) queries, as we can divide pairs in thirds, measure 0 form first of them, 1 from second and 2 from third.
Resulting in [log N/log 2]+[log N/log 3-log 2/log 3] measurements, where [] rounds up.
We don't have a problem with incomplete pairs. |
Seccond attempt:
| hidden: |
Assymetric approach can be better. The result 1 is more valuable when we don't measure exact half of coins. Let the number M of measured coins is at most half of potentialy radioactive coins (N).
The result 2 corresponds to M*(M-1) cases,
the result 1 corresponds to M*(N-M) cases and the result 0 corresponds to (N-M)*(N-M-1) cases.
If we try to minimize the number of remaining cases in the worst case we choose M=N/3 (4:4:1 ratias instead of 1:2:1).
The description of the algorithm becames more complicated ... if you want to continue with 4:4:1 ratias, the description with coins nubered in ternary and measuring those with 2 on i-th position during i-th measuring results in situation a bit more complicated than for binary strings.
Remove digits where the result was either 0 or 2 (and discard nonradioactive balls). The remaining coins are partitioned to at most 2^(log N/log 3) pairs of sets. In each set there are coins whose numbers differ by replacing some 0's and 1's, letting 2's on their positions (And some numbers differed before removing digits). There is 2^(log N/log 3) possibilities of pairs in a pair of sets.
So how to finish the algorithm? We have to locate which pair of sets contain the radioactive pair and we have to locate the radioactive pair.
Even now we can use ternary division during location of pair of sets. But as the resulting two sets can be of different sizes (1 to 2^(log N/log 3)) is the worst ratio, we cannot force ternary division in the last step.
May be the last two phases can be done together to decrease the maximal possible size of the bigger set in the cost of slower detection of paitr of sets...
It seems that finding the same number of pairs in a lot of pairs of sets is easier than in one big set.
This is why measuring amount between N/3 and N/2 may be better.... but what is the optimum?
|
Third attempt:
| hidden: | What about ratio 2/5 ... this will give better results than log(N)(1/log(2)+1/log(3)) for answer 0.
It even improves the number of remaining pairs for the answer 1 compared with the first attempt. ... Does it lead to better solution?
|
|
| « Last Edit: Nov 10th, 2007, 9:54am by Hippo » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: biggest N for 2 radioactive coins
« Reply #2 on: Oct 31st, 2007, 3:34pm » |
Quote Modify
|
I think with 10 tests, I could test among up to about 35 coins.
If the coins are numbered (or otherwise distinguishable), I might be able to do better.
|
| « Last Edit: Oct 31st, 2007, 3:43pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: biggest N for 2 radioactive coins
« Reply #3 on: Oct 31st, 2007, 3:37pm » |
Quote Modify
|
on Oct 31st, 2007, 3:34pm, towr wrote:| I think with 10 tests, I could go test among up to about 35 coins; and one test would go unused.. |
|
Are you sure? 310<2S39!
Wow, I was sure there was 39  ... this 35 is possible. ... Now I expect there would be problems to achieve 2log N/log 3 bound, but it's close. I would expect something near 2log N/(log 9-log 4)=log N/(log 3-log 2).
Alternatively .... with k measurements 2 in around 1.5k/4 coins. Oops, the first attempt beats this bound ... I should think a little more ;(
|
| « Last Edit: Nov 1st, 2007, 11:49am by Hippo » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: biggest N for 2 radioactive coins
« Reply #4 on: Oct 31st, 2007, 3:41pm » |
Quote Modify
|
on Oct 31st, 2007, 3:37pm, Hippo wrote:Are you sure? 3^10<2S3^9!
Wow, I was sure there was 3^9 ... this 3^5 is possible. |
|
I've changed my mind a couple of times 
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: biggest N for 2 radioactive coins
« Reply #5 on: Nov 10th, 2007, 9:53am » |
Quote Modify
|
on Oct 31st, 2007, 3:41pm, towr wrote:
I've changed my mind a couple of times
|
|
Can you explain your method/computation a little bit?
So far I didn't beat my first attempt ...
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: biggest N for 2 radioactive coins
« Reply #6 on: Nov 12th, 2007, 10:02am » |
Quote Modify
|
I think I may have stayed up too late when I arrived at that answer.. It seems to depend on continuously splitting up the balls in groups of three and then eliminating two. But in the end you'd be likely to have two groups of three, each with one ball; and then two measurements aren't enough to reduce both groups a further step.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
badoubei
Newbie
Posts: 4
|
|
Re: biggest N for 2 radioactive coins
« Reply #7 on: Nov 21st, 2007, 5:06pm » |
Quote Modify
|
Can anyone tell me the number to beat for 10 tests? I used Hippo's method in his first attempt and made some minor improvements. I got 91.
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: biggest N for 2 radioactive coins
« Reply #8 on: Nov 22nd, 2007, 5:30am » |
Quote Modify
|
on Nov 21st, 2007, 5:06pm, badoubei wrote:| Can anyone tell me the number to beat for 10 tests? I used Hippo's method in his first attempt and made some minor improvements. I got 91. |
|
Yes this corresponds to the first solution ... you take 7 bit numbers an make as much incomplete pairs as possible ... you create 3^3 complete pairs and 2^6-3^3 incomplete pairs. This results in 2^6+3^3=91 coins. (Btw: the natural counting does that)
Oops: natural labeling is not so good when the last answer isn't 1 ... it's better to divide each part with so far equal labels into 2 "equaly sized" and make appropriate rounding ... so the measured size is almost half the coins and write labels according the process. ... this is probably the mentioned improvement.
I will made a table of maximal number of coins for k measuremets ...
I will thing about it a little bit more, but so far it seems to me 2^9+3^0 labeling scheme is possible leading to 513 coins ... of course ... this was nonsense  ...
It seemed (not proved yet) to me the n for k measuremets are:
0:2
1:2
2:3=2^1+3^0
3:5=2^2+3^0
4:7=2^2+3^1
5:11=2^3+3^1
6:17=2^3+3^2
7:25=2^4+3^2
8:41=2^5+3^2
9:59=2^5+3^3
10:91=2^6+3^3
11:145=2^6+3^4
12:209=2^7+3^4
13:337=2^8+3^4
14:499=2^8+3^5
For ((i+1)+j):2^i+3^j the critical is the (i+1)-th measurement. For each of 3 possible results there should be at most 3^j remaining pairs..... there are
2^i - 3^j singles and 3^j pairs of coins with the same label so far.
Therefore there are at least 2^{i-1}+3^j complement pairs so far and we want to divide them to 3 groups of at least 3^{j} complement pairs. It requires 2^{i-1}+3^j<=3^{j+1}. Therefore 2^{i-1}<=2.3^j and j>=(i-2)/log_{2}3.
If a previous measurement ends with result different from 1, the problem reduces to an already known solution for smaller n.
The results correspond to expected behaviour of the "first attempt". For k=4 actually there is solution for 8 coins.
(Starting divisions 5/3, 3/2/2/1 so there will be 2 labels 000, and no label 111 ... just 3 complementary pairs.)
Simillarly for k=5 there is a solution with 12 coins.
|
| « Last Edit: Nov 25th, 2007, 7:50am by Hippo » |
IP Logged |
|
|
|
badoubei
Newbie
Posts: 4
|
|
Re: biggest N for 2 radioactive coins
« Reply #9 on: Nov 26th, 2007, 8:46am » |
Quote Modify
|
Hippo,
Here is my thoughts on 10 tests. Using your two staged approach. In the first stage, use 6 tests to test 96 coins. At most two coins are tested in the same way. In the case where all answers are 1, we would end up with 32 pairs. Each pair would have 3 coins: ((k0, k1), bitneg k). k0 and k1 are the two coins that shares the testing sequence k. In the second stage, use 4 tests to find the two bad coins.
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: biggest N for 2 radioactive coins
« Reply #10 on: Nov 27th, 2007, 10:08am » |
Quote Modify
|
badoubei: unfortunately I don't understand your last post well. Do it mean you beat the 91 record with 96?
Can you write the used labels with their frequences?
The problem with the method description is the 3 possible reduce steps ... results 0/1/2...
Currently I am trying to find optimal n by hand, I hope I will understand the problem better to be able to code it. So far I have found two nonisomorph methods to solve 8 coins on 4 measurements. I hope 12 is best for 5 measurements and I have found method to solve 19 on 6 measurements.
|
|
IP Logged |
|
|
|
badoubei
Newbie
Posts: 4
|
|
Re: biggest N for 2 radioactive coins
« Reply #11 on: Nov 27th, 2007, 10:44am » |
Quote Modify
|
Yes, I think I can get 96 with 10 tests and 46 with 8 tests. Let's label the coins 0 through 95. Use the lower 6 bits to determine whether it participates in the 6 tests at the first stage. Consider the case where all answers are 1: we would end up with 32 pairs, each with 3 coins. For example, ((0, 64), 63). So if the bad coins are in this pair, one would be either 0 or 64, and the other would be 63. At the second stage, use the first 2 tests to narrow the pairs down to 4. We have ((a0, a1), a2), ((b0, b1), b2), ((c0, c1), c2), ((d0, d1), d2). Weigh d0, d1, d2, c2, b0 in the 3rd test. If the result is 0, we have ((a0, a1), a2), (b1, b2). If the result is 1, we have (b0, b2), ((c0, c1), c2). If the result is 2, we have ((d0, d1), d2). In any case, we can use the last test to determine the two bad coins.
However, we would run into trouble if the result in last test at the first stage is 0. To overcome this, we need to replace 1000001 with 1111110, 1000010 with 1111101, 1000100 with 1111011, 1001000 with 1110111, 1010000 with 1101111.
|
| « Last Edit: Nov 27th, 2007, 10:56am by badoubei » |
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: biggest N for 2 radioactive coins
« Reply #12 on: Nov 27th, 2007, 2:30pm » |
Quote Modify
|
Nice work  . Of course you cannot work only with the 1 result (especially when the parts are of rather different sizes).
New result, new notation:
13 on 5 measurements. (Fibonacci??)
Notation: division, resulting "pair sizes" counts
13->8/5 (8/5 or 8 or 5), 5<8, 8 known;
8/5->5+3/3+2 (5/2,3/3 or 5/3 or 3/2), 3/2<5/3, 5/3 known
5/2,3/3->3+2/1+1,2+1/2+1 (3/1,3*2/1 or 3/1,2/2 or 2/1,1/1) 2/1,1/1<3/1,2/2 known
3/1,3*2/1->2+1/1+0,1+1/1+0,1+1/0+1,0+2/0+1 (3*1/1 or 2/1,1/1 or 2/1,1/1) all 3 known ...
I am rather sure the Fibonacci numbers are the limiting number of coins. ... its probably only lower bound.
I have algorithms for following cases:
6:21
7:34
8:55
9:89
10:144
... now it's time for making some code expecting to beat even the Fibonacci bound (approaching 3^{k/2} decreased a bit).
Finding an easy condition such that division to equal sized thirds is possible will be helpful.
|
| « Last Edit: Nov 29th, 2007, 4:23pm by Hippo » |
IP Logged |
|
|
|
badoubei
Newbie
Posts: 4
|
|
Re: biggest N for 2 radioactive coins
« Reply #13 on: Nov 30th, 2007, 12:29pm » |
Quote Modify
|
Excellent work! The Fibonacci bound definitely looks achievable. Do you actually have an example where you can beat the Fibonacci bound? That would be awesome.
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: biggest N for 2 radioactive coins
« Reply #14 on: Nov 30th, 2007, 4:34pm » |
Quote Modify
|
Yes, I can do 22 in 6:
13/9
8+5/5+4(8/4,5/5|known|known)
3+2/3+2,3+5/1+3(*|known|known)
3+0/2+1,0+3/0+2,2+1/1+1,3+2/0+1
.
.
|
|
IP Logged |
|
|
|
coren
Newbie
Posts: 4
|
|
Re: biggest N for 2 radioactive coins
« Reply #15 on: Dec 11th, 2007, 6:51pm » |
Quote Modify
|
To Hippo:
Hi,
can u explain how u solve 5 balls in 3 weighings?
the expression u have given for method 1 for n=5 gives 4 weighings, and reply#8 seems to contradict that.
thanks.
|
| « Last Edit: Dec 11th, 2007, 6:53pm by coren » |
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: biggest N for 2 radioactive coins
« Reply #16 on: Dec 12th, 2007, 8:07am » |
Quote Modify
|
on Dec 11th, 2007, 6:51pm, coren wrote:To Hippo:
Hi,
can u explain how u solve 5 balls in 3 weighings?
the expression u have given for method 1 for n=5 gives 4 weighings, and reply#8 seems to contradict that.
thanks. |
|
Notation a+b/c+d,e+f/g+h .... measure a,c,e,g
result k) ... k radioactive in the measurement
time:
k: ... k more measurements were allowed so far
states:
a/b,c/d ... there is one radioactive among a and one among b or one radioactive among c and one among d.
a ... there are two radioactive among the a.
3: 5=3+2
2) 3 1) 3/2 0) 2 ... easier than 2)
2: 3=2+1
2) 2 1) 2/1 0) 1 ... cannot appear
1: 2 ... already solved
1: 2/1=1+1/1+0
2) 1/1 1) 1/1 0) 1/0 ... cannot appear
0: 1/1 ... already solved
2: 3/2=2+1/1+1
2) 2/1 already known 1) 2/1,1/1 0) 1/1 already known
1: 2/1,1/1=1+1/1+0,0+1/0+1
2) 1/1 already known 1) 1/1 already known 0) 1/1 already known
BTW: The balls are coins in this thread
|
| « Last Edit: Dec 12th, 2007, 8:08am by Hippo » |
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: biggest N for 2 radioactive coins
« Reply #17 on: Jan 4th, 2008, 8:55pm » |
Quote Modify
|
You have 10 trials with 3 possible outcomes each, or 310 possible outcomes total. This is the maximum number of situations that you can reliably distinguish between.
If you have n coins and 2 are radioactive, then there are C(n,2) = n(n-1)/2 ways the radioactive coins can be distributed = number of situations that you need to distinguish between.
So n(n-1) <= 2*310. A little algebra gives n <= 344.
So 344 is an upper bound on the number of coins you can have and still pull this off. While this analysis doesn't suggest a way to meet this bound, I think it is likely that one exists.
For lower numbers of measurements:
Measurement : No. of Coins
1 : 3
2 : 4
3 : 7
4 : 13
5 : 22
6 : 38
7 : 66
8 : 115
9 : 198
10: 344
|
| « Last Edit: Jan 4th, 2008, 9:09pm by Icarus » |
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
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: biggest N for 2 radioactive coins
« Reply #18 on: Jan 5th, 2008, 8:11am » |
Quote Modify
|
I take it back about the bounds being reachable. Looking at the case of making only 3 measurements, if I have 7 coins, then there are 21 possible cases. If I test 3 coins, then I get 3 cases giving me a result of "2"; 12 cases giving a result of "1"; and 6 cases giving me a result of "0". If I test 4 coins on my first test, then it is 2: 6 cases; 1: 12 cases; 0: 3 cases. Testing other numbers of coins gives worse results.
So the best I can be guaranteed is that the first test will leave me with up to 12 cases to differentiate between with the remaining 2 tests. This is not sufficient. The remaining 2 tests can only differentiate up to 9 different cases.
Thus, you cannot find the coins in only 3 tests, if N = 7. And more generally, my bounds of the previous post are not obtainable.
(Actually, it is fairly easy to see that even with 3 coins, one measurement is not always going to be sufficient to find the radioactives.)
|
|
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
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: biggest N for 2 radioactive coins
« Reply #19 on: Jan 5th, 2008, 10:36am » |
Quote Modify
|
Welcome back Icarus, I am prety sure I get optimal results for the first 6 measurements. I have started to code some heuristic search but I have delayed it, I hope I will return to it (As so as I plan to code "How far can a track go").
|
|
IP Logged |
|
|
|
coren
Newbie
Posts: 4
|
|
Re: biggest N for 2 radioactive coins
« Reply #20 on: Jan 18th, 2008, 4:01pm » |
Quote Modify
|
On lower bound on the number of measurements:
one can find a stronger lower bound than the numbers above; basically, if we choose k out of N coins for weighing, the probabilities (p0,p1,p2) of seeing 0 radioactive, 1 radioactive and 2 radioactive coins are related. In order to minimize the number of weighings, we need to choose k s.t. H(p0,p1,p2) is maximized (H is the entropy, given p0,p1 and p2). With that done, below are the lower bounds on # of weighings:
# of weighings # of coins
3 6
4 10
5 18
6 31
7 53
8 89
9 151
10 254
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: biggest N for 2 radioactive coins
« Reply #21 on: Jan 19th, 2008, 10:54am » |
Quote Modify
|
The lower bounds on measurements ... upper bounds for measured coins can be obtained by iterative multiplication by sqrt(3) and rounding down. But I cannot remember the reasoning ;(
2:3
3:5
4:8
5:13
6:22
7:38
8:65
9:112
10:193
but I am sure the 7:38 is not achievable (and the preceding are).
|
| « Last Edit: Jan 19th, 2008, 11:03am by Hippo » |
IP Logged |
|
|
|
coren
Newbie
Posts: 4
|
|
Re: biggest N for 2 radioactive coins
« Reply #22 on: Feb 2nd, 2008, 2:19am » |
Quote Modify
|
Hippo,
Can u try and figure out the reasoning for sqrt(3) and round down? I thought about it, but I don't see why it is so.
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: biggest N for 2 radioactive coins
« Reply #23 on: Feb 12th, 2008, 2:31am » |
Quote Modify
|
Sorry, I know about the question, ... I hope I will reply later.
It was from my "understanding" of the problem when I was creating "complete" tree of possibilities of around 38 coins. I did it as a help to code it to understand the problem better.
Unfortunately when I had a week of "free time", I was not able to finish the code (I want to study only rather small cases). I have never run the code.
I hoped the run will show that after starting say 3-4 divisions the parts can be almost everywhen combined together well so the bound 3^k of informations obtained by query result becames tight.
I hope I will return to it somewhen later.
To the lower bound ... there is one argument I have may be applied ... when you are in situation after k measurements, the ordering of these measurements is not important.
|
| « Last Edit: Feb 12th, 2008, 2:32am by Hippo » |
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: biggest N for 2 radioactive coins
« Reply #24 on: Feb 22nd, 2008, 3:39am » |
Quote Modify
|
I would like to revive this thread (I am not sure we've done with this wonderful problem).
Hippo, could you please show how you identify 2 coins out of 8 in 4 tests?
I've found your notation a bit cryptic, so apologize if this was already presented here.
Ok, I do see how to make this.
The question is now: do we an inductive step here? That is: if Fn coins are tested by probes, and Fn+1 coins are tested by (t+1) probes, can we prove that Fn+2 coins may be tested by (t+2) probes?
|
| « Last Edit: Feb 22nd, 2008, 6:40am by Barukh » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print