The OEIS is supported by the many generous donors to the OEIS Foundation.



Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 59th year, we have over 358,000 sequences, and we’ve crossed 10,300 citations (which often say “discovered thanks to the OEIS”).

Other ways to Give
(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)



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) = ceiling(7n/11) for several n <= 187, esp. for all n with n <= 50 except n=3, n=30, n=41, n=49.


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

An-Ping Li, A note on the counterfeit coins problem, arXiv:0902.0841v8 [math.CO]


For n=1, compare the given coin A with a known heavy coin X. If A < X, then A is a light coin; if A=X, then A is a heavy coin; the outcome A > X 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 A < B, we know that A is light and B is heavy and can find out about C by comparing, e.g., B:C in a second weighing. The case A > B is symmetric. If, however, A=B, compare A:C. If A < C, we know that A,B are light and C is heavy and vice versa for A > C. 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.


Cf. A156301. - Jonathan Vos Post, May 18 2009

Sequence in context: A317596 A057355 A171975 * A079952 A055930 A090638

Adjacent sequences: A160508 A160509 A160510 * A160512 A160513 A160514




Hagen von Eitzen, May 16 2009



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

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 3 09:50 EST 2022. Contains 358517 sequences. (Running on oeis4.)