|
%I M1109 #42 Dec 12 2015 04:26:39
%S 1,2,4,8,15,28,51,90
%N Number of coins needed for ApSimon's mints problem.
%C Suppose there are two types of coins (genuine and counterfeit) with different weights, only one of the weights known, and n independent mints each making coins of only one of the two types. Then a(n) is the minimum number of coins needed to determine in two weighings which mints are making counterfeit coins. - _Charles R Greathouse IV_, Jun 16 2014
%C Guy and Nowakowski give a(6) <=38 and a(7)<=74. Li improves this to a(6) <=31 and a(7)<=64. a(6)=28 is given by exhaustive search of all variants up to 27 coins and the solution (0,1,2,1,8,10), (1,2,2,5,5,0) with 1+2+2+5+8+10=28 coins. David Applegate finds a(7)=51 with (12,12,7,7,1,2,0), (12,0,8,2,7,3,2). - _R. J. Mathar_, Jun 20 2014
%C The unique solution for a(8)=90 is (27,1,12,12,6,1,0,4), (3,15,13,3,7,6,6,4) as determined by exhaustive search. There are a total of three solutions for a(7)=51: the one given above, (15,10,6,1,2,1,0), (0,10,9,7,4,4,2), and (15,6,9,1,4,3,1), (0,10,6,7,4,4,2). - _David Applegate_, Jul 03 2014
%D Hugh ApSimon, Mathematical Byways in Ayling, Beeling and Ceiling, Oxford University Press (1991).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H R. K. Guy and R. Nowakowski, <a href="http://dx.doi.org/10.2307/2975631">ApSimon's mints problem</a>, Amer. Math. Monthly, 101 (1994), 358-359.
%H Tanya Khovanova, <a href="http://arxiv.org/abs/1406.3012">Attacking ApSimon's Mints</a>, arXiv:1406.3012 [math.HO], 2014.
%H Tanya Khovanova, <a href="http://blog.tanyakhovanova.com/2014/06/apsimons-mints/">ApSimon’s Mints</a>, Math Blog, June 2014.
%H Tanya Khovanova, <a href="http://blog.tanyakhovanova.com/2014/12/apsimons-mints-investigation/">ApSimon’s Mints Investigation</a>, Math Blog, December 2014.
%H Xue-Wu Li, <a href="http://www.airiti.com/ceps/ec_en/ecjnlarticleView.aspx?jnlcattype=1&jnlptype=4&jnltype=41&jnliid=1222&issueiid=35549&atliid=1752612">A new algorithm for ApSimon's Mints Problem</a>, J. Tianjin Normal University 23 (2) (2003) 39-42.
%H R. J. Mathar, <a href="http://arxiv.org/abs/1407.3613">ApSimon's mint problem with three or more weighings</a>, arXiv:1407.3613 [math.CO], 2014.
%e A pair of coin vectors gives a solution if every nonempty subset sum has a different ratio. (1,2,1,0) and (4,0,1,1) is a solution for 4 mints using 4+2+1+1=8 coins because 1:4, 2:0, 1:1, 0:1, (1+2):(4+0)=3:4, (1+1):(4+1)=2:5, (1+0):(4+1)=1:5, (2+1):(0+1)=3:1, (2+0):(0+1)=2:1, (1+0):(1+1)=1:2, (1+2+1):(4+0+1)=4:5, (1+1+0):(4+1+1)=2:6, (2+1+0):(0+1+1)=3:2, (1+2+0):(4+0+1)=3:5, (1+2+1+0):(4+0+1+1)=4:6 are all distinct ratios.
%K hard,nonn,more,nice
%O 1,2
%A _N. J. A. Sloane_, _Robert G. Wilson v_, Aug 01 1994
%E Solutions for a(6) and a(7) from _Robert Israel_ and _David Applegate_, Jun 20 2014
%E a(8) from _David Applegate_, Jul 03 2014
|
