Anurag Bishnoi wrote this beautiful post on a problem going back to a 1988 paper of Körner and Marton, and on a recent lovely paper by Anurag Bishnoi, Jozefien D’haeseleer, Dion Gijswijt, and Aditya Potukuchi, Blocking sets, minimal codes and trifferent codes.
What is the largest possible size of a set $latex C$ of ternary strings of length $latex n$, with the property that for any three distinct strings in $latex C$, there is a position where they all differ?
Let $latex T(n)$ denote this largest size. Trivially, $latex T(1) = 3^1 = 3$, and after some playing around you can perhaps prove that $latex T(2) = 4$ (I encourage you to try it so that you understand the problem). With a bit more effort, and perhaps the help of a computer, you might also be able to show that $latex T(3) = 6$, and $latex T(4) = 9$. For example, here is a set of nine ternary strings showing that $latex T(4) geq 9$: $latex 0000, 0111, 2012, 2201, 2120, 0111, 1012, 1101, 1210$. You should check that for any three strings from these nine, there is at least one position…
View original post 872 more words