Competition problem — Combinatorics

Library / /21 of 30

Combinatorics Difficulty 6.4 National Olympiad Prove it Italy

Problem:

Let $m, n$ be two integers greater than or equal to $2$ . Of a table with $m$ rows and $n$ columns it is known that every cell contains either the number $1$ or the number $-1$ , and that the total sum of all the cells is greater than or equal to zero. Genoveffa considers paths that join a cell of the first column (her choice) to a cell of the last column (again her choice) and that always move from one cell to an adjacent one, horizontally or vertically, without ever passing twice over the same cell. The value of a path is the sum of the numbers present in the cells that it passes through.

a. Prove that for every $m, n \geq 2$ there exist tables with $m$ rows and $n$ columns with no paths of value $2$ or more.

b. Prove that it is always possible to find a path of value greater than or equal to $1$ .

Solution

Solution:

a. Suppose that the table contains $1$ and $-1$ arranged in a "checkerboard" pattern (so that the cells horizontally and vertically adjacent to a cell containing $1$ contain $-1$ , and vice versa), in such a way that the cell in the top left corner contains the number $1$ (this guarantees that the sum of the numbers present in the table is greater than or equal to $0$ ). In any path on this table, a $1$ is always followed by a $-1$ , unless it is the content of the last cell of the path; the value of every path is therefore at most $1$ .

b. If there is a row with strictly positive sum, this constitutes a path of value at least $1$ . We may therefore suppose that each row has sum at most $0$ , and hence, since the sum of the content of all the cells is at least $0$ , that all the rows have sum equal to zero.

Let us now consider the cell in the top left corner of the table. If it contains a $+1$ , the path that starts from the cell in question and traverses the entire second row has value exactly $1$ . If instead it contains a $-1$ , it suffices to consider a path that fills the entire table, except for the cell in question (for example by traversing the columns in alternating directions, starting however from the second cell of the first column). Since we have supposed that a path covering the entire table has value $0$ , the path described above has value $0-(-1)=1$ . In every case, therefore, it is possible to find a path of value at least $1$ .

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from it; metadata (topic, difficulty) added by this project.