{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreibnthd7urykarue7slc2mfx2q5xd4rc2sziurwrarbikrhbmtxrkq",
    "uri": "at://did:plc:46ti67tc37qcmwp2vaynk6fq/app.bsky.feed.post/3mghoqgp4bi32"
  },
  "path": "/blog/tech/2026-03-07-10-54_a286874_14_28.html",
  "publishedAt": "2026-03-07T11:07:26.807Z",
  "site": "http://blog.sesse.net",
  "tags": [
    "OEIS A286874",
    "A303977"
  ],
  "textContent": "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?\n\nThe 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.\n\nIt 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.)\n\nNow, 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:\n\n\n       0123456789 ← Servant number\n\n     0 0000000111\n     1 0000011001\n     2 0000101010\n     3 0000110100\n     4 0001001100\n     5 0010010010\n     6 0011000001\n     7 0100100001\n     8 0101000010\n     9 0110000100\n    10 1001010000\n    11 1010100000\n    12 1100001000\n\n     ↑ Bottle number\n\n\nIt 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.\n\nThe 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.\n\nWe'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).)\n\nI'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:\n\n  * A286874 a(14) = 28\n  * A303977 a(14) = 788 (!!)\n\n\n\nThe 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.\n\nI 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.)",
  "title": "Steinar H. Gunderson: A286874(14) = 28",
  "updatedAt": "2026-03-07T09:54:00.000Z"
}