Maths Olympiad Prep

Library / /4 of 11

Number theory Difficulty 5.9 AIME, harder Prove it Romania

The integers from 11 to 4949 are written in a 7×77 \times 7 table, such that for any k{1,2,...,7}k \in \{1, 2, ..., 7\}, the product of the numbers in the kk-th row equals the product of the numbers in the (8k)(8-k)-th row.

a) Prove that there exists a row such that the sum of the numbers written on it is a prime number.

Solution

a) Let p1,p2,...,p7p_1, p_2, ..., p_7 be the products of the elements of the rows 1,2,...,71, 2, ..., 7. We have p1=p7p_1 = p_7, p2=p6p_2 = p_6 and p3=p5p_3 = p_5, so 49!=(p1p2p3)2p449! = (p_1 p_2 p_3)^2 \cdot p_4, (1).

Note that 49!=2463225107811413317219223229313741434749! = 2^{46} \cdot 3^{22} \cdot 5^{10} \cdot 7^8 \cdot 11^4 \cdot 13^3 \cdot 17^2 \cdot 19^2 \cdot 23^2 \cdot 29 \cdot 31 \cdot 37 \cdot 41 \cdot 43 \cdot 47. From (1) we infer that the primes which have odd exponents in the prime factorization of 49!49! must appear in the prime factorization of one of the numbers situated on the 44-th row, thus 13293137414347p413 \cdot 29 \cdot 31 \cdot 37 \cdot 41 \cdot 43 \cdot 47 \mid p_4. The product of any two of the primes 13,29,31,37,41,4313, 29, 31, 37, 41, 43 and 4747 exceeds 4949, therefore each of these primes divides exactly one of the 77 numbers situated on the 44-th row.

The number 49!p4\frac{49!}{p_4} is a perfect square, hence if p4>13293137414347p_4 > 13 \cdot 29 \cdot 31 \cdot 37 \cdot 41 \cdot 43 \cdot 47, we have that p42213293137414347p_4 \ge 2^2 \cdot 13 \cdot 29 \cdot 31 \cdot 37 \cdot 41 \cdot 43 \cdot 47, thus one of the numbers written in the cells of the table will be at least equal to min{2213,229}>49\min\{2^2 \cdot 13, 2 \cdot 29\} > 49, false.

Therefore, the 44-th row contains the numbers 13,29,31,37,41,43,4713, 29, 31, 37, 41, 43, 47, whose sum is the prime 241241.

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.