Author |
Topic: biggest N for 2 radioactive coins (Read 3473 times) |
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender: 
Posts: 4863
|
 |
Re: biggest N for 2 radioactive coins
« Reply #25 on: Feb 22nd, 2008, 3:34pm » |
 Quote  Modify
|
on Feb 22nd, 2008, 3:39am, Barukh wrote:| I've found your notation a bit cryptic, |
|
I have to agree, other than with the "bit" part. I couldn't make any sense of it.
|
|
 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
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: biggest N for 2 radioactive coins
« Reply #26 on: Feb 23rd, 2008, 4:56am » |
Quote Modify
|
Today, I talked to my friend who was working on this problem for a few weeks, and he told me he managed to develop a proof that t measurements are sufficient to classify Ft+2 coins. After brief discussion, I got convinced that his argument is perfectly sound.
The argument is constructive, and in fact major steps were already presented in previous Hippo’s posts, but there is a certain twist that makes the whole proof to work smoothly. I am going to present it here later, and currently to give a solution for 8 = F6 coins in 4 measurements. I will use a notation that will hopefully be easier to understand.
The notation is as follows. The “Branch” column represents the history of measurements until the current measure, where every number means the outcome of the corresponding measurement, starting from first. For instance, branch “1.2” means there were already two measurements, first of which showed 1 radioactive coin, while the second 2 radioactive coins. (If we build the solution as a 3-nary tree, as it is custom with coin weightings, then it is simply a branch in this tree). The branch “*” is the first measurement (the root of the tree).
The “Measurement” column shows which coins are put in the detector at a certain branch. For instance, the branch 1.2 puts coins 1,2,6 in the detector; while branch 1.1 measures coins 3,5,6,7.
The “Pairs” column shows the possible pairs of radioactive coins as a result of different outcomes of the last measurement. For instance, if at the branch 1.1 the measurement (of coins 3,5,6,7) showed a single radioactive coin, the possible pairs are (3,8), (4,6) or (4.7).
I present only a part of the full solution tree. It is (deliberately) slightly different from Hippo’s solution outlined here, and has all the essential parts of the general solution.
Branch Measurment Pairs
12345678
2345678
* +++++--- 1 2222111
2 222111
3 22111
4 2111
5 111
6 00
7 0
678
1 +++--++- 1 221
2 221
3 221
4 110
5 110
67
1.2 ++---+-- 1 21
2 21
3 10
678
1.1 --+-+++- 1 0
2 0
3 1
4 11
5 22
678
1.1.1 ---+-+-- 3 0
4 21
|
| « Last Edit: Feb 23rd, 2008, 5:00am by Barukh » |
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: biggest N for 2 radioactive coins
« Reply #27 on: Feb 24th, 2008, 12:40pm » |
Quote Modify
|
Barukh: Sorry, I was a week of for skiing ...
About the notation: I was thinking about such a representation such that the results can be reused as often as possible.
If all measurements so far gave result either 0 or 2 the situation can be described by one number ... the number of radioactivity candidate coins.
If a measurement gave result 1 the situation can be described by several pairs of numbers.
a1xb1, a2xb2, ... , akxbk.
Such that all possible pairs of radioactive coins are organized into k "rectangles" of sizes aixbi. (Actually in my notation I have used / instead x, but I can swith it....)
In your example the result 1 of * measurement gives 5x3. The measurement 1 will be described by (3+2)x(2+1) with results 2) 3x2 1) 3x1,2x2 0) 2x1
The measurement 1.2 (actually only 6 coins are important) (2+1)x(1+1) with results 2) 2x1 1) 2x1,1x1 0) 1x1
The measurement 1.1 (1+2)x(0+1),(1+1)x(2+0) with results 2) 1x2(2x1) 1) 1x1,1x2(2x1,1x1) 0) 2x1
The difference in notation is only its compactness.
I have used 3*5/3 to denote 3 rectangles 5x3 so 3*5x3 would be used now.
Actually this solution for 8 coins was outlined 4 posts earlier (at the and). There is other solution for 8 coins starting with 4+4 measurement.
(4x4,2x2,2*3x1,1x1 can be done on 3 measurements, as well as 5x3,2*2x2,3x1,1x1)
Yes, if I remember it well, I have had proof for Fibonacci, but as this bound is beaten ... the 22 example ... If you will not present the Fibonacci proof, I hope I will return to it ...
|
| « Last Edit: Feb 24th, 2008, 1:23pm by Hippo » |
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: biggest N for 2 radioactive coins
« Reply #28 on: Mar 15th, 2008, 8:28pm » |
Quote Modify
|
OK here it is ... the Fibonacci bound proof (F0=F1=1).
Lemma: Fk (*) as so as FkxFk-1, Fk-1xFk-3, 2*Fk-2xFk-2 (**) and FkxFk-2, Fk-1xFk-1, Fk-1xFk-2, Fk-2xFk-3, Fk-2xFk-4, Fk-3xFk-3 (***)
are positions solvable on k-1 measurements for k  5 (actually (*) holds for each k, (**) for k 4).
The induction step:
(measured+unmeasured)
Fk=(Fk-1+Fk-2)
0: by induction  (*) 1: Fk-1xFk-2 by induction (**) 2: by induction (*)
FkxFk-1, Fk-1xFk-3, 2*Fk-2xFk-2 = (Fk-1+Fk-2)x(Fk-2+Fk-3), (0+Fk-1)x(0+Fk-3), (Fk-2+0)x(Fk-4+Fk-3), (0+Fk-2)x(0+Fk-2)
0:by induction (**) 1:by induction (***) 2: by induction (**)
FkxFk-2, Fk-1xFk-1, Fk-1xFk-2, Fk-2xFk-3, Fk-2xFk-4, Fk-3xFk-3 = (Fk-1+Fk-2)x(Fk-2+0), (Fk-3+Fk-2)x(0+Fk-1), (Fk-3+Fk-2)x(Fk-3+Fk-4), (Fk-3+Fk-4)x(Fk-4+Fk-5), (Fk-2+0)x(Fk-4+0), (0+Fk-3)x(0+Fk-3)
0:by induction (**) 1:by induction (***) 2: by induction (**)
Remains to proove initial conditions: (***)
8x3, 5x5, 5x3, 3x2, 3x1, 2x2 = (5+3)x(2+1), (3+2)x(3+2), (1+4)x(0+3), (3+0)x(2+0), (2+1)x(1+0), (0+2)x(0+2)
0:4x3, 3x1, 2*2x2
1:5x1, 3*3x2, 3x1, 1x1
2:5x2, 3x3, 3x2, 2x1
4x3, 3x1, 2x2, 2x2 = (3+1)x(2+1), (0+3)x(0+1), (2+0)x(1+1), (1+1)x(1+1)
0.0:3x1, 2*1x1 3x1, 2x2, 2x1
0.1:3x1, 2*2x1, 2*1x1 3x1, 2x2, 2x1
0.2:3x2, 2x1, 1x1
5x1, 3x2, 3x2, 3x2, 3x1, 1x1 = (3+2)x(0+1), (3+0)x(2+0), (0+3)x(0+2), (2+1)x(1+1), (3+0)x(0+1), (1+0)x(1+0)
1.0:3x2, 2x1, 1x1
1.1:3x1, 2x1, 3x1 3x2, 2x1, 1x1
1.2:3x2, 2x1, 1x1
5x2, 3x3, 3x2, 2x1 = (3+2)x(1+1), (2+1)x(2+1), (0+3)x(0+2), (2+0)x(1+0)
2.0:3x2, 2x1, 1x1
2.1:3x1, 2x1, 2x1, 2x1 3x1, 2x2, 2x1
2.2:3x1, 2x2, 2x1
cases (0.2, 1.0, 1.1, 1.2, 2.0) 3x2, 2x1, 1x1 = (2+1)x(1+1), (0+2)x(0+1), (1+0)x(1+0)
*.*.0: 2x1,1x1
*.*.1: 2x1,1x1
*.*.2: 2x1,1x1
cases (0.0, 0.1, 2.1, 2.2) 3x1, 2x2, 2x1 = (2+1)x(1+0), (1+1)x(1+1), (0+2)x(0+1)
*.*.0: 2x1, 1x1
*.*.1: 3*1x1 2x1, 1x1
*.*.2: 2x1, 1x1
cases *.*.* 2x1,1x1 = (1+1)x(1+0), (0+1)x(0+1)
*.*.*.0: 1x1
*.*.*.1: 1x1
*.*.*.2: 1x1
Uff, fortunatelly the table was filled correctly, just the correct division was not mentioned.
(**)
5x3, 3x1, 2*2x2 = (3+2)x(2+1), (0+3)x(0+1), (0+2)x(0+2), (2+0)x(1+1)
0: 3x1, 2x2, 2x1
1: 3x1, 2x2, 2x1
2: 3x2, 2x1 3x2, 2x1, 1x1
8x5, 5x2, 2*3x3 = (5+3)x(3+2), (0+5)x(0+1), (2+1)x(2+0), (2+1)x(2+0)
0: 5x1, 3x2 5x1, 3*3x2, 3x1, 1x1
1: 5x2, 3x3, 2x1, 2x1 5x2, 3x3, 3x2, 2x1
2: 5x3, 2*2x2 5x3, 3x1, 2*2x2
|
| « Last Edit: Mar 17th, 2008, 6:23am by Hippo » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print