Separating indices

Question

Let $S\subseteq A^n$ for some finite alphabet $A$. I'm interested in finding a minimum subset $I\subseteq\{1,...,n\}$ such that for any two distinct $x, y \in S$, there exists an $i \in I$ for which $x[i]\neq y[i]$. I'm pretty sure this is a well known combinatorics problem but can't find any reference to it. Thank you!

Answer 1

You can solve it as a set covering problem as follows. For each $i\in\{1,\dots,n\}$, let binary decision variable $z_i$ indicate whether $i\in I$. The problem is to minimize $\sum_{i=1}^n z_i$ subject to linear constraints $$\sum_{i: x_i \not= y_i} z_i \ge 1 \quad \text{for all $x,y\in S$ such that $x\not= y$}.$$