Maths Olympiad Prep

Library / /184 of 299

Algebra Difficulty 6.7 National Olympiad Prove it Iran

In a n×nn \times n table, consider the main diagonal and the cells below. We call these cells a triangular grid of length nn.

We want to place a real number in each cell of a triangular table of length nn such that for each cell (i,j)(i, j), the sum of the numbers in all cells of its row ii and all cells of its column jj (including xi,jx_{i,j} itself, which is counted once) is zero. For example, for the cells with circles in them, the sum of all cells marked with a circle is zero. We know that the cells at the top-most and left-most positions contains the number 11. Find the number of possible ways to fill the remaining cells.

Assume the triangular grid consists of cells (i,j)(i, j) where 1jin1 \leq j \leq i \leq n (lower triangle), and for a cell (i,j)(i, j), the sum condition is (k=1ixi,k)+(k=jnxk,j)xi,j=0\left(\sum_{k=1}^i x_{i,k}\right) + \left(\sum_{k=j}^n x_{k,j}\right) - x_{i,j} = 0.

Solution

Consider the top-left cell, it follows that the sum of the numbers in the first row is zero. Considering the cells in the first row and summing them up, it follows that the sum of the numbers in the table is zero. Analogously, it follows that the sum of the numbers in the first column is zero. Using this and writing the relation for the top-right cell, it follows that the top-right cell is zero. We claim that the sum of the four vertices of any rectangle is zero. To see this, consider all cells in the two columns corresponding to the vertices of the rectangle. Add up the resulting relations and use the fact that the sum of the cells in the table is zero. Now, if the numbers in the first row are indexed from right to left as a1=0,a2,,an=1a_1 = 0, a_2, \dots, a_n = 1, and the numbers in the first column are indexed from top to bottom as b1,,bn=1b_1, \dots, b_n = 1, we have: xijx_{ij} (cell ii row, jj column)

xij=aibj x_{ij} = -a_i - b_j

By writing the relation for the cells in the first row, we get:
(s+1)ans=b2++b2+s (s + 1)a_{n-s} = b_2 + \cdots + b_{2+s}
which implies:
ansmax(b2,,b2+s) a_{n-s} \le \max(|b_2|, \dots, |b_{2+s}|)
Similarly,
bnsmax(a2,,b2+s) |b_{n-s}| \le \max(|a_2|, \dots, |b_{2+s}|)
Consider the cell with the maximum absolute value in the row and column. By symmetry, we must have ans=b2+s==b2a_{n-s} = |b_{2+s}| = \dots = |b_2|. Considering b2b_2, all aia_i must have the same sign, and all bib_i must have the same sign. By writing the relation for the first row, we have ai=n/2a_i = -n/2, bi=1/nb_i = 1/n.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.