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!