Veit: I'm starting to see why we need so many bottles before this puzzle is interesting! We can bound the number of rejected bottles R by R <= 2 ceiling( 1000/M(10) ) --Hey, the letter R was already taken! Use U (for unsafe) or B (for bad bottle)? where M(10) is the maximum size "perfect union code" on 10 symbols. I'm making up the name of these codes, which I believe are very interesting. Here's the definition: Describe binary codewords of length N in terms of subsets of N symbols. A "perfect union code" is a set of codewords such that if A, B, C are any distinct codewords in the code, then it never happens that A is contained in the union of B and C. The maximum sizes of perfect union codes starts out being very boring: M(3) = 3 M(4) = 4 M(5) = 5 M(6) = 6 These codes are just the N singleton subsets. But we can do better for large N... --ok, let me produce a general theorem about perfect-union-codes using a randomizing argument. Simply select from n items, random subsets of cardinality q each. Keep going until you've selected m such subsets. The chance that a particular subset A is contained in the union of two particular others B,C, is chance = 2q * (2q-1) * (2q-2) *...* (q+1) / ( n * (n-1) * (n-2) *...* (n+1-q) ) and hence the expected number of violations is expectednumber = m * (m-1) * (m-2) * chance / 2 hence if expectednumber < 1 then there must exist a random-choice-configuration with actually zero violations, i.e. a perfect-union code. So M(n) obeys M(n)>=m if m^3 * (2*q)^q < 2 * (n+1-q)^q that is if 3 * log(m) < log(2) + q * log(n-q) - q * log(2*q) choose q=0.1358*n to find EXPONENTIAL GROWTH THEOREM: M(n) > 2^(0.3333 + 0.07558*n).