login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual Appeal: Today, Nov 11 2014, is the 4th anniversary of the launch of the new OEIS web site. 70,000 sequences have been added in these four years, all edited by volunteers. Please make a donation (tax deductible in the US) to help keep the OEIS running.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A007673 Number of coins needed for ApSimon's mints problem.
(Formerly M1109)
0
1, 2, 4, 8, 15, 28, 51, 90 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

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

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

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

REFERENCES

Hugh ApSimon, Mathematical Byways in Ayling, Beeling and Ceiling, Oxford University Press (1991).

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

LINKS

Table of n, a(n) for n=1..8.

R. K. Guy and R. Nowakowski, ApSimon's mints problem, Amer. Math. Monthly, 101 (1994), 358-359.

Tanya Khovanova, Attacking ApSimon's Mints, arXiv:1406.3012, 2014.

Xue-Wu Li, A new algorithm for ApSimon's Mints Problem, J. Tianjin Normal University 23 (2) (2003) 39-42.

R. J. Mathar, ApSimon's mint problem with three or more weighings, arXiv:1407.3613, 2014.

EXAMPLE

A pair of coin vectors gives a solution if every non-empty 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.

CROSSREFS

Sequence in context: A036615 A006808 A006727 * A182725 A029907 A005682

Adjacent sequences:  A007670 A007671 A007672 * A007674 A007675 A007676

KEYWORD

hard,nonn,more,nice

AUTHOR

N. J. A. Sloane, Robert G. Wilson v, Aug 01 1994

EXTENSIONS

Solutions for a(6) and a(7) from Robert Israel and David Applegate, Jun 20 2014

a(8) from David Applegate, Jul 03 2014

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified December 20 09:43 EST 2014. Contains 252241 sequences.