Browse · MathNet
PrintIMO Team Selection Contest
Estonia counting and probability
Problem
On a square board with rows and columns, where , some squares are colored black in such a way that no two rows are alike. Find the biggest integer such that for every possible coloring to start with one can always color columns entirely red in such a way that no two rows are still alike.
Answer: .
Answer: .
Solution
Prove that if , one of the columns can always be colored red. Then, when excluding this column, we can continue the process until the number of columns is smaller than the number of rows, i.e. times. Suppose we cannot color a single column red such that no two rows still appear alike. Then, for every column there are at least two rows that differ by only one square in that column. Consider those two rows for every column. Now consider a graph with its vertices being the rows and its edges being the pairs of rows of interest. As this graph has at least as many edges as vertices, the graph contains a cycle. Consider an arbitrary row (i.e. vertex) of the cycle. Then the row it is followed by differs from row exactly by one square, assume this square is located at the column . Every next row differs from the previous one in exactly one column. As all these columns differ from column , all the other edges of this cycle correspond to passing from one row to another such that the square in column remains the same. Therefore, the square in column remains the same in all the rows after and it has to remain the same at the last passage which takes us back to the row . This, however, means that all squares in row have to be of the same color as the square at the row after , a contradiction.
In general, no more rows can be colored red. Assume that all the squares are colored black to start with, apart from the diagonal of an -subsquareboard. If we color columns red, there are always at least 2 columns which lie in that subsquareboard. But this means that we will over-color the only two white squares in two rows and thus we end up with two equally colored rows.
---
Alternative solution.
Consider the columns of the squareboard one by one. The first column divides the set of all the rows into two subsets: one of them consists of the rows which have the square at the first column white and the other consists of those rows that have their first square black. If the first column has all its squares white or all its squares black, then we can color it red. Similarly, for every next column divide the subsets even further depending on whether there is a black or a white square in that row in that column. If no subsets are divided further at a particular step, we can color that column red. Therefore, for all columns, either the number of subsets increases by at least one or this column is colored red. As we started off with one set and ended up with subsets each containing one row only, there has to be no more than columns that were not colored red and thus at least that were. All these rows are still different from each other because we colored only those columns which had no new information about the differences between rows compared with previous columns.
Similarly to Solution 1 we can show that there always exists a coloring for which no more columns can be colored red.
---
Alternative solution.
Prove by induction on the number of rows that we can always color at least columns red. If then we can color all the columns red, i.e. . Assume that for we can color at least columns red such that no two rows appear alike. Assume now that . Following from the induction hypothesis we can color at least columns red such that the first rows remain different. If after that coloring process the last row is different from the rest, all the conditions required are satisfied and we can color at least columns red. If the last row however is similar to any of the rows above it (there can be only one of those) then as these rows were all different to start with, there should exist a column at which the last row and the row that appears similar after coloring actually differ. If we do not color this column, all the rows will appear different and we can color columns red.
Similarly to Solution 1 we can show that there always exists a coloring for which no more columns can be colored red.
In general, no more rows can be colored red. Assume that all the squares are colored black to start with, apart from the diagonal of an -subsquareboard. If we color columns red, there are always at least 2 columns which lie in that subsquareboard. But this means that we will over-color the only two white squares in two rows and thus we end up with two equally colored rows.
---
Alternative solution.
Consider the columns of the squareboard one by one. The first column divides the set of all the rows into two subsets: one of them consists of the rows which have the square at the first column white and the other consists of those rows that have their first square black. If the first column has all its squares white or all its squares black, then we can color it red. Similarly, for every next column divide the subsets even further depending on whether there is a black or a white square in that row in that column. If no subsets are divided further at a particular step, we can color that column red. Therefore, for all columns, either the number of subsets increases by at least one or this column is colored red. As we started off with one set and ended up with subsets each containing one row only, there has to be no more than columns that were not colored red and thus at least that were. All these rows are still different from each other because we colored only those columns which had no new information about the differences between rows compared with previous columns.
Similarly to Solution 1 we can show that there always exists a coloring for which no more columns can be colored red.
---
Alternative solution.
Prove by induction on the number of rows that we can always color at least columns red. If then we can color all the columns red, i.e. . Assume that for we can color at least columns red such that no two rows appear alike. Assume now that . Following from the induction hypothesis we can color at least columns red such that the first rows remain different. If after that coloring process the last row is different from the rest, all the conditions required are satisfied and we can color at least columns red. If the last row however is similar to any of the rows above it (there can be only one of those) then as these rows were all different to start with, there should exist a column at which the last row and the row that appears similar after coloring actually differ. If we do not color this column, all the rows will appear different and we can color columns red.
Similarly to Solution 1 we can show that there always exists a coloring for which no more columns can be colored red.
Final answer
n - m + 1
Techniques
Coloring schemes, extremal argumentsInvariants / monovariantsInduction / smoothingPigeonhole principleGraph Theory