In an grid table, each cell is filled with the integer 1 or 2). It is known that the integers in each row are not all the same, and for any two rows of numbers and , there must be a row in the table that is . Prove that there must be a column of integers in the table where the number of 0s is no less than half.
Problem 1172
Official solution
[Proof] When , the proposition is obviously true. Below, let .
(1) Suppose there is a row in the grid table with exactly 1 zero, without loss of generality, let this row be . Thus, if there is a row of numbers , by the given condition, there must be another row of numbers . Therefore, the number of 0s in the first column is no less than half.
(2) Suppose there is a row in the table with exactly two 0s, without loss of generality, let this row be . Let denote the number of rows whose first two numbers are , then as in (1), we know that . Moreover, without loss of generality, let . Thus, , which means the number of 0s in the first column is no less than the number of 1s.
(3) In the remaining cases, except for one row of numbers possibly being , the rest of the rows have no fewer than 3 zeros. Since , there must exist two rows with at least 3 zeros, and the positions of the zeros are not all the same. Thus, their product will have at least 4 zeros. In this way, except for the row with all 6 numbers being 1 (if any), the number of 0s in the remaining rows is more than the number of 1s. Therefore, in the table, there is a column where the number of 0s is more than half. Clearly, this column in the original table also has no fewer 0s than half. The proposition is proved. Regarding the two added columns, the middle line is symmetric with the numbers in the original table. It is easy to see that after such an extension, the product of all numbers in the adjacent white cells of each black cell in the table is still 1, and the numbers filled in each row have a period of .
Since each black cell in the first row has 3 adjacent white cells, the product of the 3 numbers filled in these cells is 1, hence
where represents the number filled in the cell at the -th row and -th column of the grid, and since only white cells are considered, is even. Using the given condition for each black cell in the second row that is not a border cell, we have
Similarly, from (1) and (2), we have
Continuing in this manner, we get
It is easy to see that all the factors on the right side of (3) are all the numbers in one period. By symmetry, their product is 1, hence
which means all the white cells in the last row of the original table are filled with 1.
Using the given condition, we can then deduce from bottom to top that all the white cells in each row are filled with 1.