|
|
A280432
|
|
Maximum size of a set whose integrity can be checked with n weighings.
|
|
0
|
|
|
|
OFFSET
|
1,1
|
|
COMMENTS
|
This sequence arises in the following problem: Given a set of binary elements (e.g., coins that may have one of the two weights), determine whether all of them are the same by weighing equally sized non-overlapping subsets n times. a(n) is the maximum size of a set whose integrity can be checked with n weighings.
The next terms are probably a(7) = 2234 and a(8) = 9966 (from the Kozlov/Vu reference). - Konstantin Knop, Oct 18 2017
((3^n-1)/2)*(n+1)*n^((n-1)/2) >= a(n) >= 2^((1/2)*n*log(n)-n*(2+o(1))) [Alon&Vu]. - Andrey Zabolotskiy, Oct 23 2017
|
|
LINKS
|
Noga Alon, Van H. Vu, Anti-Hadamard Matrices, Coin Weighing, Threshold Gates, and Indecomposable Hypergraphs, Journal of Combinatorial Theory, Series A, Volume 79, Issue 1, July 1997, Pages 133-160.
Dmitry N. Kozlov, Van H. Vu, Coins and Cones, Journal of Combinatorial Theory, Series A, Volume 78, Issue 1, April 1997, Pages 1-14 [gives lower bounds for a(n) up to n=15].
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,more,hard
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|