Maths Olympiad Prep

Track / Stage 6 / 172 of 400 #1172 of 1964

Problem 1172

National olympiad, first round
Combinatorics Difficulty 6.3 Prove it

3373 \cdot 37 In an n×6n \times 6 grid table, each cell is filled with the integer 1 or 0(n0(n \geqslant 2). It is known that the integers in each row are not all the same, and for any two rows of numbers (a1,a2,,a6)\left(a_{1}, a_{2}, \cdots, a_{6}\right) and (b1,b2,,b6)\left(b_{1}, b_{2}, \cdots, b_{6}\right), there must be a row in the table that is (a1b1,a2b2,,a6b6)\left(a_{1} b_{1}, a_{2} b_{2}, \cdots, a_{6} b_{6}\right). Prove that there must be a column of integers in the table where the number of 0s is no less than half.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

[Proof] When n=2n=2, the proposition is obviously true. Below, let n>2n>2.
(1) Suppose there is a row in the grid table with exactly 1 zero, without loss of generality, let this row be (0,1,1,1,1,1)(0, 1, 1, 1, 1, 1). Thus, if there is a row of numbers (1,a2,,a6)\left(1, a_{2}, \cdots, a_{6}\right), by the given condition, there must be another row of numbers (0,a2,,a6)\left(0, a_{2}, \cdots, a_{6}\right). 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 (0,0,1,1,1,1)(0,0,1,1,1, 1). Let aija_{ij} denote the number of rows whose first two numbers are i,ji, j, then as in (1), we know that a00a11a_{00} \geqslant a_{11}. Moreover, without loss of generality, let a01a10a_{01} \geqslant a_{10}. Thus, a00+a01a10+a11a_{00} + a_{01} \geqslant a_{10} + a_{11}, 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 (1,1,1,1,1,1)(1,1,1,1,1,1), the rest of the rows have no fewer than 3 zeros. Since n>2n>2, 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 n1n-1 rows is more than the number of 1s. Therefore, in the (n1)×6(n-1) \times 6 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 1984×21984 \times 2.

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
a2j=a1j1a1j+1,1j1984×31, a_{2j} = a_{1j-1} \cdot a_{1j+1}, \quad 1 \leqslant j \leqslant 1984 \times 3 - 1,

where aija_{ij} represents the number filled in the cell at the ii-th row and jj-th column of the grid, and since only white cells are considered, i+ji+j is even. Using the given condition for each black cell in the second row that is not a border cell, we have
a3j=a1ja2j1a2j+1=a1j2a1ja1j+2. a_{3j} = a_{1j} a_{2j-1} \cdot a_{2j+1} = a_{1j-2} a_{1j} a_{1j+2}.

Similarly, from (1) and (2), we have
a4j=a2ja3j1a3j+1=a1j3a1j1a1j+1a1j+3. a_{4j} = a_{2j} a_{3j-1} a_{3j+1} = a_{1j-3} a_{1j-1} a_{1j+1} a_{1j+3}.

Continuing in this manner, we get
a1984j=a1j1983a1j1981a1j1a1j+1a1j+1983. a_{1984j} = a_{1j-1983} a_{1j-1981} \ldots a_{1j-1} a_{1j+1} \ldots a_{1j+1983}.

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
a1984j=1,j=1986,1988,,3966, a_{1984j} = 1, \quad j = 1986, 1988, \cdots, 3966,

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.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.