[seqfan] Re: ApSimon's Mints

[Max Alekseyev]

Hi Richard,
Thank you for clarification. It was unclear for me that coins can be
reused in the weightings.
Regards,
Max



On Fri, Jun 13, 2014 at 9:41 AM, Richard J. Mathar
<mathar at mpia-hd.mpg.de> wrote:
> 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
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/