suppose we are given an $n+1\times n+1$ square grid colored with black and white such that none of its rows are the same. Prove you can select a row and a column, and paint both of them blue so there are still none of its rows are the same.

I can prove the stronger result you can select a column and paint it blue so no two rows are the same but I'd like to know if this problem can be attacked differently. The reason why I ask this is that I need to grade a homework and the person used the weaker version (He didn't prove it, he thought it was obvious but later couldn't prove it) to prove the stronger result. But I don't know if the weaker result is significantly easier to prove.

Proof it works by deleting only one column. Make the simple graph where the vertices are the rows and two rows are adjacent if ad only if there is a column that makes those two rows the same when it is colored blue. Label each of the edges according to the column that must be painted blow to make the rows the same.

If one of the columns is not the label of any edge we can paint that column blue and no two rows are the same. We shall prove not all labels appear, suppose all the labels appear,select an edge for each label and consider the spanning subgraph with the selected edges then there is $n$ edges and $n$ vertices, thus there is a cycle. Note that cycle does not have repeated labels, this is a contradiction, since traversing a cycle should take us back to the same vertex, but to do that we would have to go through an even number of edges of each label!

  • $\begingroup$ Can you post your proof that it works if you only change a column? $\endgroup$ – NoName Oct 4 '14 at 3:14
  • $\begingroup$ Of course, I had hesitated to do so since I didn't want to make people biased towards a specific solution $\endgroup$ – Jorge Fernández Hidalgo Oct 4 '14 at 3:24

Of course, if you can delete a column to get the desired result, then that is sufficient because deleting a row can't make things worse. I worked this out and found that it's always possible to delete a column too. If someone wishes to prove a weaker version, I suggest not reading this. (I would guess the problem is stated as it is because it leads to a later problem where you need an $n \times n$ matrix.)

If two rows are the same except for their entries on one column, call them "paired". Note that since our entries are black and white, three or more rows cannot be "paired" together.

We will build our matrix a row at a time. The first row obviously has no pairings with the rows above it. The second row could be paired with the first row. If they are paired, then the third row could be paired with one of the above rows by differing by one entry, but not both, because that would imply rows 1 and 2 are the same. If they are not paired, the third row could be paired with rows 1 and 2, but this is still only 2 pairings among our 3 rows.

In general, if two rows are paired, then a row under them can be paired with one or the other, but not both. And if you have a collection of $m$ unpaired rows, you can add another row beneath them to make $m+1$ rows with $m$ pairings among them.

Thus on our $n + 1 \times n + 1$ matrix, there are at most $n$ pairings. The column without pairings is the one we delete.


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.