[seqfan] Re: ApSimon's Mints

[Richard J. Mathar]

http://list.seqfan.eu/pipermail/seqfan/2014-June/013134.html says

ma> I do not understand how "the minimum total of coins you need to
ma> request from the mints" results in minimizing SUM max(P_r,Q_r).
ma> ...

This is part of the original problem. In the first weighting, P_1 from mint 1,
P_2 from mint 2 and so on are used. In the second weighting Q_1 from mint 1,
Q_2 from mint 2 and so on. Since one needs to draw only max(P_r,Q_r) from mint r
to conduct both weightings, the total number of different coins that are ever
on the scale is sum_{mints r} maximum(both weights).

Example for the solution in http://www.jstor.org/stable/2975631 
for n=6 mints: if P={1,1,2,3,5,8} (Fibonacci !) and Q=[11,6,5,3,1,1],
we need from mint 1 the maximum of 1 and 11 (11), from mint 2 the maximum 
of 1 and 6 (6), from mint 3 max(2,5)=5, from mint 4 max(3,3)=3, from mint 
5 max(5,3)=5 and from mint 5 max(8,1)=8. Total number of coints from all
6 mints is 11+6+5+3+5+8=38.

Example for n=8:
P=[1,1,2,3,5,8,13,21] and Q=[38,19,22,10,64,83,2,4] 
are a solution with 270 coins (obtained by using a randon number generator
for the elements of Q).

Example for n=9:
P=[1,1,2,3,5,8,13,21,34]
and
Q = [149,40,254,72,81,207,2,69,28]
are a solution with 919 coins.

R. Mathar