wu :: forums - Print Page


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

        riddles >> hard >> biggest N for 2 radioactive coins
        
(Message started by: inexorable on Oct 31^st, 2007, 1:30pm)

Title: biggest N for 2 radioactive coins
Post by inexorable on Oct 31^st, 2007, 1:30pm

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.

Title: Re: biggest N for 2 radioactive coins
Post by Hippo on Oct 31^st, 2007, 2:26pm

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:D ) attempt:
[hideb]
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 log₂ 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 log₃ (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.[/hideb]

Seccond attempt:
[hideb]
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?
[/hideb]

Third attempt:
[hideb] 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?
[/hideb]

Title: Re: biggest N for 2 radioactive coins
Post by towr on Oct 31^st, 2007, 3:34pm

I think with 10 tests, I could test among up to about 3⁵ coins.
If the coins are numbered (or otherwise distinguishable), I might be able to do better.

Title: Re: biggest N for 2 radioactive coins
Post by Hippo on Oct 31^st, 2007, 3:37pm

on 10/31/07 at 15:34:44, towr wrote:

I think with 10 tests, I could go test among up to about 3⁵ coins; and one test would go unused..

Are you sure? 3¹⁰<₂S_3⁹!

Wow, I was sure there was 3⁹ :) ... this 3⁵ 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.5^k/4 coins. Oops, the first attempt beats this bound ... I should think a little more ;(

Title: Re: biggest N for 2 radioactive coins
Post by towr on Oct 31^st, 2007, 3:41pm

on 10/31/07 at 15:37:28, Hippo wrote:

Are you sure? 3^10<₂S_3^9!

Wow, I was sure there was 3^9 :) ... this 3^5 is possible.

I've changed my mind a couple of times :P

Title: Re: biggest N for 2 radioactive coins
Post by Hippo on Nov 10^th, 2007, 9:53am

on 10/31/07 at 15:41:19, towr wrote:

I've changed my mind a couple of times :P

Can you explain your method/computation a little bit?
So far I didn't beat my first attempt ...

Title: Re: biggest N for 2 radioactive coins
Post by towr on Nov 12^th, 2007, 10:02am

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.

Title: Re: biggest N for 2 radioactive coins
Post by badoubei on Nov 21^st, 2007, 5:06pm

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.

Title: Re: biggest N for 2 radioactive coins
Post by Hippo on Nov 22^nd, 2007, 5:30am

on 11/21/07 at 17:06:18, 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.

Title: Re: biggest N for 2 radioactive coins
Post by badoubei on Nov 26^th, 2007, 8:46am

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.

Title: Re: biggest N for 2 radioactive coins
Post by Hippo on Nov 27^th, 2007, 10:08am

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.

Title: Re: biggest N for 2 radioactive coins
Post by badoubei on Nov 27^th, 2007, 10:44am

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.

Title: Re: biggest N for 2 radioactive coins
Post by Hippo on Nov 27^th, 2007, 2:30pm

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.

Title: Re: biggest N for 2 radioactive coins
Post by badoubei on Nov 30^th, 2007, 12:29pm

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.

Title: Re: biggest N for 2 radioactive coins
Post by Hippo on Nov 30^th, 2007, 4:34pm

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
.
.

Title: Re: biggest N for 2 radioactive coins
Post by coren on Dec 11^th, 2007, 6:51pm

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.

Title: Re: biggest N for 2 radioactive coins
Post by Hippo on Dec 12^th, 2007, 8:07am

on 12/11/07 at 18:51:46, 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 ;)

Title: Re: biggest N for 2 radioactive coins
Post by Icarus on Jan 4^th, 2008, 8:55pm

You have 10 trials with 3 possible outcomes each, or 3¹⁰ 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*3¹⁰. 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

Title: Re: biggest N for 2 radioactive coins
Post by Icarus on Jan 5^th, 2008, 8:11am

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.)

Title: Re: biggest N for 2 radioactive coins
Post by Hippo on Jan 5^th, 2008, 10:36am

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").

Title: Re: biggest N for 2 radioactive coins
Post by coren on Jan 18^th, 2008, 4:01pm

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

Title: Re: biggest N for 2 radioactive coins
Post by Hippo on Jan 19^th, 2008, 10:54am

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).

Title: Re: biggest N for 2 radioactive coins
Post by coren on Feb 2^nd, 2008, 2:19am

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.

Title: Re: biggest N for 2 radioactive coins
Post by Hippo on Feb 12^th, 2008, 2:31am

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.

Title: Re: biggest N for 2 radioactive coins
Post by Barukh on Feb 22^nd, 2008, 3:39am

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 F_n coins are tested by probes, and F_n+1 coins are tested by (t+1) probes, can we prove that F_n+2 coins may be tested by (t+2) probes?

Title: Re: biggest N for 2 radioactive coins
Post by Icarus on Feb 22^nd, 2008, 3:34pm

on 02/22/08 at 03:39:10, 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.

Title: Re: biggest N for 2 radioactive coins
Post by Barukh on Feb 23^rd, 2008, 4:56am

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 F_t+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 = F₆ 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 (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1193862608;start=0#12), 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

Title: Re: biggest N for 2 radioactive coins
Post by Hippo on Feb 24^th, 2008, 12:40pm

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.
a₁xb₁, a₂xb₂, ... , a_kxb_k.

Such that all possible pairs of radioactive coins are organized into k "rectangles" of sizes a_ixb_i. (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 ...

Title: Re: biggest N for 2 radioactive coins
Post by Hippo on Mar 15^th, 2008, 8:28pm

OK here it is ... the Fibonacci bound proof (F₀=F₁=1).

Lemma: F_k (*) as so as F_kxF_k-1, F_k-1xF_k-3, 2*F_k-2xF_k-2 (**) and F_kxF_k-2, F_k-1xF_k-1, F_k-1xF_k-2, F_k-2xF_k-3, F_k-2xF_k-4, F_k-3xF_k-3 (***)
are positions solvable on k-1 measurements for k http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ge.gif5 (actually (*) holds for each k, (**) for k http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ge.gif4).

The induction step:
(measured+unmeasured)
F_k=(F_k-1+F_k-2)
0: by induction http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lessdot.gif (*) 1: F_k-1xF_k-2 by induction http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lessdot.gif (**) 2: by induction http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lessdot.gif (*)

F_kxF_k-1, F_k-1xF_k-3, 2*F_k-2xF_k-2 = (F_k-1+F_k-2)x(F_k-2+F_k-3), (0+F_k-1)x(0+F_k-3), (F_k-2+0)x(F_k-4+F_k-3), (0+F_k-2)x(0+F_k-2)
0:by induction http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lessdot.gif (**) 1:by induction http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lessdot.gif (***) 2: by induction http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lessdot.gif (**)

F_kxF_k-2, F_k-1xF_k-1, F_k-1xF_k-2, F_k-2xF_k-3, F_k-2xF_k-4, F_k-3xF_k-3 = (F_k-1+F_k-2)x(F_k-2+0), (F_k-3+F_k-2)x(0+F_k-1), (F_k-3+F_k-2)x(F_k-3+F_k-4), (F_k-3+F_k-4)x(F_k-4+F_k-5), (F_k-2+0)x(F_k-4+0), (0+F_k-3)x(0+F_k-3)
0:by induction http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lessdot.gif (**) 1:by induction http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lessdot.gif (***) 2: by induction http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lessdot.gif (**)

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 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lessdot.gif 3x1, 2x2, 2x1
0.1:3x1, 2*2x1, 2*1x1 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lessdot.gif 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 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lessdot.gif 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 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lessdot.gif 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 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lessdot.gif 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 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lessdot.gif 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 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lessdot.gif 5x1, 3*3x2, 3x1, 1x1
1: 5x2, 3x3, 2x1, 2x1 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lessdot.gif 5x2, 3x3, 3x2, 2x1
2: 5x3, 2*2x2 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lessdot.gif 5x3, 3x1, 2*2x2