Maths Olympiad Prep

Library / IMO Shortlist /223 of 365

IMO Shortlist

Number theory Difficulty 8.7 Shortlist Prove it IMO

Let n>1n > 1 be a positive integer. Each cell of an n×nn \times n table contains an integer. Suppose that the following conditions are satisfied:
(i) Each number in the table is congruent to 11 modulo nn;
(ii) The sum of numbers in any row, as well as the sum of numbers in any column, is congruent to nn modulo n2n^{2}.
Let RiR_{i} be the product of the numbers in the ithi^{\text{th}} row, and CjC_{j} be the product of the numbers in the jthj^{\text{th}} column. Prove that the sums R1+⋯+RnR_{1} + \cdots + R_{n} and C1+⋯+CnC_{1} + \cdots + C_{n} are congruent modulo n4n^{4}.

Solutions — 2

Solution 1

Let Ai,jA_{i, j} be the entry in the ithi^{\text{th}} row and the jthj^{\text{th}} column; let PP be the product of all n2n^{2} entries. For convenience, denote ai,j=Ai,j−1a_{i, j} = A_{i, j} - 1 and ri=Ri−1r_{i} = R_{i} - 1. We show that
∑i=1nRi≡(n−1)+P( mod  n4)(1) \sum_{i=1}^{n} R_{i} \equiv (n-1) + P \quad (\bmod\ n^{4}) \tag{1}
Due to symmetry of the problem conditions, the sum of all the CjC_{j} is also congruent to (n−1)+P(n-1) + P modulo n4n^{4}, whence the conclusion.
By condition (i)(i), the number nn divides ai,ja_{i, j} for all ii and jj. So, every product of at least two of the ai,ja_{i, j} is divisible by n2n^{2}, hence
Ri=∏j=1n(1+ai,j)=1+∑j=1nai,j+∑1⩽j1<j2⩽nai,j1ai,j2+⋯≡1+∑j=1nai,j≡1−n+∑j=1nAi,j ( mod  n2)R_{i} = \prod_{j=1}^{n} (1 + a_{i, j}) = 1 + \sum_{j=1}^{n} a_{i, j} + \sum_{1 \leqslant j_{1} < j_{2} \leqslant n} a_{i, j_{1}} a_{i, j_{2}} + \cdots \equiv 1 + \sum_{j=1}^{n} a_{i, j} \equiv 1 - n + \sum_{j=1}^{n} A_{i, j} \ (\bmod\ n^{2})
for every index ii. Using condition (ii), we obtain Ri≡1 ( mod  n2)R_{i} \equiv 1\ (\bmod\ n^{2}), and so n2∣rin^{2} \mid r_{i}.
Therefore, every product of at least two of the rir_{i} is divisible by n4n^{4}. Repeating the same argument, we obtain
P=∏i=1nRi=∏i=1n(1+ri)≡1+∑i=1nri( mod  n4), P = \prod_{i=1}^{n} R_{i} = \prod_{i=1}^{n} (1 + r_{i}) \equiv 1 + \sum_{i=1}^{n} r_{i} \quad (\bmod\ n^{4}),
whence
∑i=1nRi=n+∑i=1nri≡n+(P−1)( mod  n4) \sum_{i=1}^{n} R_{i} = n + \sum_{i=1}^{n} r_{i} \equiv n + (P - 1) \quad (\bmod\ n^{4})
as desired.

Solution 2

We present a more straightforward (though lengthier) way to establish (1). We also use the notation of ai,ja_{i, j}.
By condition (i), all the ai,ja_{i, j} are divisible by nn. Therefore, we have
P=∏i=1n∏j=1n(1+ai,j)≡1+∑(i,j)ai,j+∑(i1,j1),(i2,j2)ai1,j1ai2,j2+∑(i1,j1),(i2,j2),(i3,j3)ai1,j1ai2,j2ai3,j3( mod  n4) \begin{aligned} P = \prod_{i=1}^{n} \prod_{j=1}^{n} (1 + a_{i, j}) &\equiv 1 + \sum_{(i, j)} a_{i, j} + \sum_{(i_{1}, j_{1}), (i_{2}, j_{2})} a_{i_{1}, j_{1}} a_{i_{2}, j_{2}} \\ &+ \sum_{(i_{1}, j_{1}), (i_{2}, j_{2}), (i_{3}, j_{3})} a_{i_{1}, j_{1}} a_{i_{2}, j_{2}} a_{i_{3}, j_{3}} \quad (\bmod\ n^{4}) \end{aligned}
where the last two sums are taken over all unordered pairs/triples of pairwise different pairs (i,j)(i, j); such conventions are applied throughout the solution.
Similarly,
∑i=1nRi=∑i=1n∏j=1n(1+ai,j)≡n+∑i∑jai,j+∑i∑j1,j2ai,j1ai,j2+∑i∑j1,j2,j3ai,j1ai,j2ai,j3( mod  n4). \sum_{i=1}^{n} R_{i} = \sum_{i=1}^{n} \prod_{j=1}^{n} (1 + a_{i, j}) \equiv n + \sum_{i} \sum_{j} a_{i, j} + \sum_{i} \sum_{j_{1}, j_{2}} a_{i, j_{1}} a_{i, j_{2}} + \sum_{i} \sum_{j_{1}, j_{2}, j_{3}} a_{i, j_{1}} a_{i, j_{2}} a_{i, j_{3}} \quad (\bmod\ n^{4}) .
Therefore,
P+(n−1)−∑iRi≡∑(i1,j1),(i2,j2)i1≠i2ai1,j1ai2,j2+∑(i1,j1),(i2,j2),(i3,j3)i1≠i2≠i3≠i1ai1,j1ai2,j2ai3,j3+∑(i1,j1),(i2,j2),(i3,j3)i1≠i2=i3ai1,j1ai2,j2ai3,j3( mod  n4). \begin{aligned} P + (n-1) - \sum_{i} R_{i} &\equiv \sum_{\substack{(i_{1}, j_{1}), (i_{2}, j_{2}) \\ i_{1} \neq i_{2}}} a_{i_{1}, j_{1}} a_{i_{2}, j_{2}} \\ &+ \sum_{\substack{(i_{1}, j_{1}), (i_{2}, j_{2}), (i_{3}, j_{3}) \\ i_{1} \neq i_{2} \neq i_{3} \neq i_{1}}} a_{i_{1}, j_{1}} a_{i_{2}, j_{2}} a_{i_{3}, j_{3}} \\ &+ \sum_{\substack{(i_{1}, j_{1}), (i_{2}, j_{2}), (i_{3}, j_{3}) \\ i_{1} \neq i_{2} = i_{3}}} a_{i_{1}, j_{1}} a_{i_{2}, j_{2}} a_{i_{3}, j_{3}} \quad (\bmod\ n^{4}) . \end{aligned}
We show that in fact each of the three sums appearing in the right-hand part of this congruence is divisible by n4n^{4}; this yields (1). Denote those three sums by Σ1,Σ2\Sigma_{1}, \Sigma_{2}, and Σ3\Sigma_{3} in order of appearance. Recall that by condition (ii) we have
∑jai,j≡0( mod  n2)for all indices i \sum_{j} a_{i, j} \equiv 0 \quad (\bmod\ n^{2}) \quad \text{for all indices } i
For every two indices i1<i2i_{1} < i_{2} we have
∑j1∑j2ai1,j1ai2,j2=(∑j1ai1,j1)⋅(∑j2ai2,j2)≡0( mod  n4) \sum_{j_{1}} \sum_{j_{2}} a_{i_{1}, j_{1}} a_{i_{2}, j_{2}} = \left(\sum_{j_{1}} a_{i_{1}, j_{1}}\right) \cdot \left(\sum_{j_{2}} a_{i_{2}, j_{2}}\right) \equiv 0 \quad (\bmod\ n^{4})
since each of the two factors is divisible by n2n^{2}. Summing over all pairs (i1,i2)(i_{1}, i_{2}) we obtain n4∣Σ1n^{4} \mid \Sigma_{1}.
Similarly, for every three indices i1<i2<i3i_{1} < i_{2} < i_{3} we have
∑j1∑j2∑j3ai1,j1ai2,j2ai3,j3=(∑j1ai1,j1)⋅(∑j2ai2,j2)⋅(∑j3ai3,j3) \sum_{j_{1}} \sum_{j_{2}} \sum_{j_{3}} a_{i_{1}, j_{1}} a_{i_{2}, j_{2}} a_{i_{3}, j_{3}} = \left(\sum_{j_{1}} a_{i_{1}, j_{1}}\right) \cdot \left(\sum_{j_{2}} a_{i_{2}, j_{2}}\right) \cdot \left(\sum_{j_{3}} a_{i_{3}, j_{3}}\right)
which is divisible even by n6n^{6}. Hence n4∣Σ2n^{4} \mid \Sigma_{2}.
Finally, for every indices i1≠i2=i3i_{1} \neq i_{2} = i_{3} and j2<j3j_{2} < j_{3} we have
ai2,j2⋅ai2,j3⋅∑j1ai1,j1≡0( mod  n4) a_{i_{2}, j_{2}} \cdot a_{i_{2}, j_{3}} \cdot \sum_{j_{1}} a_{i_{1}, j_{1}} \equiv 0 \quad (\bmod\ n^{4})
since the three factors are divisible by n,nn, n, and n2n^{2}, respectively. Summing over all 4-tuples of indices (i1,i2,j2,j3)(i_{1}, i_{2}, j_{2}, j_{3}) we get n4∣Σ3n^{4} \mid \Sigma_{3}.

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

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.