Skip to main content
OlympiadHQ

Browse · MathNet

Print

Problems from Ukrainian Authors

Ukraine algebra

Problem

Is it possible to write positive integers in the cells of the board in such a way that the sum of the numbers in any rectangle is a perfect square if and only if 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 . Write in the cell , i.e. the one in the -th row and -th column, the number , where the number is selected later.

Consider an arbitrary rectangle , which lies in rows with numbers and columns with numbers . By construction, the sum of all numbers in the rectangle is equal to where and . It is immediately clear that if , the sum of numbers in is the perfect square of any real number . Now it remains to find such an that no matter how , where , the number would not be a perfect square.

Proving. Let . We can immediately see that starting from some point is positive, because its highest coefficient is . In the following, we will consider only from this point onwards. First, let's find the following polynomial with rational coefficients such that the degree of the polynomial is less than . To do this, it is enough to restore the coefficients one by one , using identities: Thus, we can write the equality , . Let's multiply both parts of this equality by so that the polynomials , and become integer coefficients. We have that , where again and all polynomials and have integer coefficients. Suppose that what you want to prove is not true. This would mean that is not identically zero. We know that there are infinitely many such that is a perfect square. We will see that since the coefficients of the polynomial are integer and nonnegative and is not exactly zero, starting from some point , and therefore from the same point . Then consider sufficiently large positive integers , of which there are infinitely many, such that , where is a positive integer and . We see But since , the inequality can only hold for a finite number of different , which leads to a contradiction.

The lemma implies that for any given and , there are only a finite number of such that is a perfect square. Indeed, otherwise, there would be a polynomial with rational coefficients such that . But we can see that there is a complex root on the left-hand side, which has a multiplicity of , and this is where we get the contradiction. Alternatively, we can see that , which has a GCD of with , and therefore has no roots of multiplicity. Therefore, for any given and , there are only a finite number of such that is a perfect square. And since there are a finite number of ways to choose a pair , it means that there is an , for which is not a perfect square for any positive integers and not greater than . Therefore, we can put and the statement is proved.

Techniques

Polynomial operationsSums and products