login
Maximum size of a set whose integrity can be checked with n weighings.
0

%I #29 Oct 28 2017 15:53:56

%S 2,4,10,30,114,454

%N Maximum size of a set whose integrity can be checked with n weighings.

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

%C The next terms are probably a(7) = 2234 and a(8) = 9966 (from the Kozlov/Vu reference). - _Konstantin Knop_, Oct 18 2017

%C ((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

%H Noga Alon, Dmitry N. Kozlov, <a href="https://doi.org/10.1006/jagm.1997.0871">Coins with Arbitrary Weights</a>, Journal of Algorithms, Volume 25, Issue 1, October 1997, Pages 162-176.

%H Noga Alon, Van H. Vu, <a href="https://doi.org/10.1006/jcta.1997.2780">Anti-Hadamard Matrices, Coin Weighing, Threshold Gates, and Indecomposable Hypergraphs</a>, Journal of Combinatorial Theory, Series A, Volume 79, Issue 1, July 1997, Pages 133-160.

%H IBM Research, <a href="https://www.research.ibm.com/haifa/ponderthis/challenges/December2016.html">Ponder This December 2016 challenge</a>

%H IBM Research, <a href="https://www.research.ibm.com/haifa/ponderthis/solutions/December2016.html">Solutions for n=4 and 5</a>

%H Dmitry N. Kozlov, Van H. Vu, <a href="https://doi.org/10.1006/jcta.1996.2724">Coins and Cones</a>, 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].

%K nonn,more,hard

%O 1,1

%A _Serge Batalov_, Jan 02 2017