Maths Olympiad Prep

Library / /40 of 42

Number theory Difficulty 7.3 National olympiad, round 2 Prove it Romania

Let nn be a positive integer. We say that a n×nn \times n table is *special* if:
* each cell of the table contains a 2-digit odd positive integer;
* the numbers of the table are pairwise distinct;
* the products of the numbers of each line and the products of the numbers of each column are perfect squares.
Prove that the largest value of nn for which there exists a n×nn \times n special table is equal to 4.

Solution

Since 112>10011^2 > 100, the table cannot contain numbers divisible by squares of prime numbers pp, with p7p \ge 7.
Suppose that there exists a number of the table (situated on line \ell and column cc) divisible by a prime p17p \ge 17. Then there exists one more number on line \ell (and column ccc' \ne c) divisible by pp. Also, there exists one more number on column cc (and line \ell' \ne \ell) divisible by pp. Therefore, in the cell (,c)(\ell', c') must be a number divisible by pp. In consequence, in the table must appear a number N7p>100N \ge 7p > 100 – impossible.

| 11 | 3113 \cdot 11 | 333^3 | 525^2 |
| --- | --- | --- | --- |
| 5115 \cdot 11 | 7117 \cdot 11 | 353 \cdot 5 | 373 \cdot 7 |
| 727^2 | 3523 \cdot 5^2 | 13 | 3133 \cdot 13 |
| 3253^2 \cdot 5 | 3273^2 \cdot 7 | 5135 \cdot 13 | 7137 \cdot 13 |

It follows that the table cannot contain 2-digit numbers that are odd multiples of 17 – 3 numbers, of 19 – 3 numbers, of 23 – 2 numbers, of 29 – 2 numbers, of 31 – 2 numbers and of 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 – one number each; in total, 26 numbers. On the other hand, there are 45 odd 2-digit numbers, so the table can contain at most 4526=1945 - 26 = 19 numbers. Hence n4n \le 4.
The table from above is an example for n=4n = 4.

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.