Maths Olympiad Prep

Library / /16 of 19

Algebra Difficulty 7.0 National olympiad Prove it Ukraine

Is it possible to write positive integers in the cells of the board 2022×20222022 \times 2022 in such a way that the sum of the numbers in any rectangle RR is a perfect square if and only if RR is a square?
(Arsenii Nikolaiev)

Solution

Yes, you can.

Number the columns from left to right and the rows from top to bottom with the numbers 1,2,,20221, 2, \dots, 2022. Write in the cell (r,c)(r, c), i.e. the one in the rr-th row and cc-th column, the number x2(r+c)x^{2(r+c)}, where the number xx is selected later.

Consider an arbitrary rectangle RR, which lies in rows with numbers s,s+1,,ts, s + 1, \dots, t and columns with numbers u,u+1,,vu, u + 1, \dots, v. By construction, the sum of all numbers in the rectangle RR is equal to
(x2s+x2s+2++x2t)(x2u+x2u+2++x2v)=x2s+2ux2a1x21x2b1x21, (x^{2s} + x^{2s+2} + \dots + x^{2t}) \cdot (x^{2u} + x^{2u+2} + \dots + x^{2v}) = x^{2s+2u} \cdot \frac{x^{2a} - 1}{x^2 - 1} \cdot \frac{x^{2b} - 1}{x^2 - 1},
where a=ts+1a = t - s + 1 and b=vu+1b = v - u + 1. It is immediately clear that if a=ba = b, the sum of numbers in RR is the perfect square of any real number xx. Now it remains to find such an xx that no matter how aba \neq b, where a,b{2,3,,2021}a, b \in \{2, 3, \dots, 2021\}, the number (x2a1)(x2b1)(x^{2a} - 1)(x^{2b} - 1) would not be a perfect square.

Proving. Let P(x)=x2n+a2n1x2n1++a1x+a0P(x) = x^{2n} + a_{2n-1}x^{2n-1} + \dots + a_1x + a_0. We can immediately see that starting from some point P(x)P(x) is positive, because its highest coefficient is 11. In the following, we will consider only xx from this point onwards. First, let's find the following polynomial Q(x)=xn+bn1xn1++b1x+b0Q(x) = x^n + b_{n-1}x^{n-1} + \dots + b_1x + b_0 with rational coefficients such that the degree of the polynomial P(x)Q(x)2P(x) - Q(x)^2 is less than nn. To do this, it is enough to restore the coefficients one by one bn1,,b1,b0b_{n-1}, \dots, b_1, b_0, using identities:
k=n2n1i+j=kbibjxk=akxk. \sum_{k=n}^{2n-1} \sum_{i+j=k} b_i b_j x^k = a_k x^k.
Thus, we can write the equality P(x)=Q(x)2+R(x)P(x) = Q(x)^2 + R(x), degR<n\deg R < n. Let's multiply both parts of this equality by M2M^2 so that the polynomials M2P(x)=P1(x)M^2P(x) = P_1(x), MQ(x)=H(x)MQ(x) = H(x) and M2R(x)=S(x)M^2R(x) = S(x) become integer coefficients. We have that P1(x)=H2(x)+S(x)P_1(x) = H^2(x) + S(x), where again degS<n\deg S < n and all polynomials P1,HP_1, H and SS have integer coefficients. Suppose that what you want to prove is not true. This would mean that S(x)S(x) is not identically zero. We know that there are infinitely many xx such that P1(x)=M2P(x)P_1(x) = M^2P(x) is a perfect square. We will see that since the coefficients of the polynomial S(x)S(x) are integer and nonnegative and S(x)S(x) is not exactly zero, starting from some point S(x)0S(x) \neq 0, and therefore from the same point H(x)2P1(x)H(x)^2 \neq P_1(x). Then consider sufficiently large positive integers tt, of which there are infinitely many, such that P1(t)=w2P_1(t) = w^2, where ww is a positive integer and H(t)2P1(t)H(t)^2 \neq P_1(t). We see
P1(t)H2(t)2w1S(t)2w1=2P(t)12tn1>tn. |P_1(t) - H^2(t)| \geq 2w - 1 \Rightarrow |S(t)| \geq 2w - 1 = 2\sqrt{P(t)} - 1 \geq 2t^n - 1 > t^n.
But since degS<n\deg S < n, the inequality S(t)>tnS(t) > t^n can only hold for a finite number of different tt, which leads to a contradiction.

The lemma implies that for any given aa and bb, there are only a finite number of xx such that (x2a1)(x2b1)(x^{2a} - 1)(x^{2b} - 1) is a perfect square. Indeed, otherwise, there would be a polynomial Q(x)Q(x) with rational coefficients such that (x2a1)(x2b1)=Q2(x)(x^{2a} - 1)(x^{2b} - 1) = Q^2(x). But we can see that there is a complex root e2πiae^{\frac{2\pi i}{a}} on the left-hand side, which has a multiplicity of 11, and this is where we get the contradiction. Alternatively, we can see that (x2a1)=2ax2a1(x^{2a} - 1)' = 2a x^{2a-1}, which has a GCD of 11 with (x2a1)(x^{2a} - 1), and therefore x2a1x^{2a} - 1 has no roots of multiplicity. Therefore, for any given aa and bb, there are only a finite number of xx such that (x2a1)(x2b1)(x^{2a} - 1)(x^{2b} - 1) is a perfect square. And since there are a finite number of ways to choose a pair (a,b)(a, b), it means that there is an x0x_0, for which (x02a1)(x02b1)(x_0^{2a} - 1)(x_0^{2b} - 1) is not a perfect square for any positive integers aa and bb not greater than 20192019. Therefore, we can put x=x0x = x_0 and the statement is proved.

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 and solution reproduced as published; topic and difficulty added by this site.