2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ very good, I personally wasn't able to solve it, had you seen this problem before? $\endgroup$ – Jorge Fernández Hidalgo Aug 10 '14 at 4:00
  • $\begingroup$ Not this problem exactly, but problems like this pop up all over the place in areas like error-correcting codes and extremal combinatorics (not to mention contests). $\endgroup$ – jschnei Aug 10 '14 at 4:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.