This site is supported by donations to The OEIS Foundation.

 Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of the OEIS". Other ways to donate

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A160511 Number of weighings needed to find lighter coins among n coins. 0
 1, 2, 3, 3, 4, 4, 5, 6, 6, 7, 7, 8, 9, 9, 10, 11, 11, 12, 13, 13, 14, 14, 15, 16, 16, 17, 18, 18, 19 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1,2 COMMENTS a(n) is the minimal worst-case number of weighings needed by an algorithm to sort a set of n coins of two possible weights into heavy vs. light coins by using a balance; additional known good (heavy, say) coins are available (esp. to distinguish "all heavy" from "all light"). It is known that ceiling(n*log_3(2) + log_3(135/128)) <= a(n) <= ceiling(7n/11) for all n except for n=3. This implies 19 <= a(30) <= 20 and in fact a(n) = ceil(7n/11) for several n <= 187, esp. for all n with n<=50 except n=3, n=30, n=41, n=49. LINKS An-Ping Li, A note on the counterfeit coins problem, arXiv:0902.0841v8 [math.CO] EXAMPLE For n=1, compare the given coin A with a known heavy coin X. If AX is not possible. Since one weighing was needed, we have a(1)=1. For n=3, to sort coins A,B,C, one optimal algorithm is: First compare A:B. If AB is symmetric. If however A=B, compare A:C. If AC. The worst case is A=C, which requires a third weighing, e.g. A:X, against a known heavy coin X. Since no algorithm exists that never uses more than 2 weighings, we have a(3) = 3. CROSSREFS Cf. A156301. [From Jonathan Vos Post, May 18 2009] Sequence in context: A244229 A057355 A171975 * A079952 A055930 A090638 Adjacent sequences:  A160508 A160509 A160510 * A160512 A160513 A160514 KEYWORD hard,more,nonn AUTHOR Hagen von Eitzen, May 16 2009 STATUS approved

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