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

 

Logo

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

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

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 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.

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.

License Agreements, Terms of Use, Privacy Policy .

Last modified November 19 06:50 EST 2017. Contains 294915 sequences.