Steinar H. Gunderson: A286874(14) = 28

There’s a logic puzzle that goes like this: A king has a thousand bottles of
wine, where he knows that one is poisoned. He also has ten disposable
servants that could taste the wine, but for whatever reason (the usual
explanation is that the poison is slow-working and the feast is nearing),
they can only take one sip each, possibly mixed from multiple bottles.
How can he identify the bad bottle?

The solution is well-known and not difficult; you give each bottle a number
0..999 and write it out in binary, and use the ones to assign wines to
servants. (So there’s one servant that drinks a mix of all the odd-numbered
wines, and that tells you if the poisoned bottle’s number is odd or even.
Another servant drinks a mix of bottles 2, 3, 6, 7, 10, 11, etc., and that
tells you the second-lowest bit. And so on.) This works because ten servants
allow you to test 2^10 = 1024 bottles.

It is also easy to extend this to “at most one bottle is poisoned”;
give the wines numbers from 1..1000 instead, follow the same pattern,
and if no servant dies, you know the answer is zero. (This allows you to
test at most 1023 bottles.)

Now, let’s tweak the puzzle: What if there’s zero, one or two poisoned
bottles? How many bottles can the king test with his ten servants?
(If you’re looking for a more real-world application of this, replace
“poisoned bottles” with “COVID tests” and maybe it starts to sound less
arbitrary.) If course, the king can easily test ten bottles by having
each servant test exactly one bottle each, but it turns out you can
get to 13 by being a bit more clever, for instance:

   0123456789 ← Servant number

 0 0000000111
 1 0000011001
 2 0000101010
 3 0000110100
 4 0001001100
 5 0010010010
 6 0011000001
 7 0100100001
 8 0101000010
 9 0110000100
10 1001010000
11 1010100000
12 1100001000

 ↑ Bottle number

It can be shown (simply by brute force) that no two rows here are a subset
of another row, so if you e.g. the “servant death” vector is 0110101110
(servants 1, 2, 4, 6, 7 and 8 die), the only way this could be is if
bottle 2 and 9 are poisoned (and none else). Of course, the solution is
nonunique, since you could switch around the number of servants or wines
and it would stil work. But if you don’t allow that kind of permutation,
there are only five different solutions for 10 servants and 13 wines.

The maximum number of possible wines to test is recorded in
OEIS A286874, and the number of different
solutions in A303977. So for A286874,
a(10) = 13 and for A303977, a(10) = 5.

We’d like to know what these values for higher values, in particular
A286874 (A303977 is a bit more of a curiosity, and also a convenient place
to write down all the solutions). I’ve written before about how we
can create fairly good solutions using error-correcting codes
(there are also other possible constructions), but optimal turns out
to be hard. The only way we know of is some form of brute force.
(I used a SAT solver to confirm a(10) and a(11), but it seemed to get
entirely stuck on a(12).)

I’ve also written about my brute-force search of a(12) and a(13),
so I’m not going to repeat that, but it turned out that with a bunch
of extra optimizations and 210 calendar days of near-continuous
calculation, I could confirm that:

• A286874 a(14) = 28
• A303977 a(14) = 788 (!!)

The latter result is very surprising to me, so it was an interesting
find. I would have assumed that with this many solutions, we’d find
a(14) = 29.

I don’t have enough CPU power to test a(15) or a(16) (do contact me
if you have a couple thousand cores to lend out for some months or more),
but I’m going to do a search in a given subset of the search space (5-uniform
solutions), which is much faster; it won’t allow us to fix more elements of
either of the sequences, but it’s possible that we’ll find some new records
and thus lower bounds for A286874. Like I already posted, we know that
a(15) >= 42. (Someone should also probably go find some bounds for
a(17), a(18), etc.—when the sequence was written, the posted known bounds
were far ahead of the sequence itself, but my verification has caught up
and my approach is not as good in creating solutions heuristically
out of thin air.)