# combinatorics board with digits neat problem

this is a problem I wanted to share with you that I just saw today. There is a board square board (think of chess) with $10$ columns and $n$ rows. Each square contains a digit (an integer between $0$ and $9$.The board satisfies the property that for any row $c$ and any columns $a$ and $b$ there is another row $d$ which is different from row $c$ exactly in columns $a$ and $b$ (so they have the same digits in all columns, except for columns $a$ and $b$ in which they are different. Prove the board has at least $512$ rows.

This problem is from an olympiad from my university, called the Galois-Noether competition.

Given a row $r$, define the pattern of the row to be the set of indices $i$ such that the $i$th number in row $r$ is different from the $i$th number in the first row. Clearly, the first row has pattern $\emptyset$, and if two rows have different patterns, they must be different.
We claim that, given your constraints, if $p$ is a pattern with an even number of elements, then there must be a row on the board with pattern $p$. Indeed, let $p$ be the pattern $\{i_1, i_2, \dots, i_{2k-1}, i_{2k}\}$. By choosing the first row, $a=i_1$ and $b=i_2$, there must exist a row with pattern $\{i_1, i_2\}$. By choosing this row, $a=i_{3}$, $b=i_{4}$, there must exist a row with pattern $\{i_1, i_2, i_3, i_4\}$. Continuing inductively, it follows there must exist a row with pattern $p$, as desired.
The number of subsets of $\{1, 2, 3, \dots, 10\}$ with an even number of elements is $2^{10-1} = 512$, so this proves there must be at least 512 rows.
(Note that 512 is tight; if you choose the board whose rows are all $10$-bit strings with an even number of $1$s, this board satisfies the constraints and has exactly $512$ rows).