Maths Olympiad Prep

Library / /235 of 462

Number theory Difficulty 5.8 AIME, harder Prove it Ireland

A Sudoku grid is a 9×99 \times 9 table in which each row and each column contains each of the numbers 1,2,3,4,5,6,7,8,91, 2, 3, 4, 5, 6, 7, 8, 9 in some order. In addition, the nine 3×33 \times 3 subgrids contain each of the numbers 1,2,3,4,5,6,7,8,91, 2, 3, 4, 5, 6, 7, 8, 9 exactly once. Suppose the product of all nine numbers on one diagonal is MM and the product of all nine numbers on the other diagonal is NN.
Prove that it is possible for the product MNMN to be divisible by 202532025^3 but it is not possible for MNMN to be divisible by 202542025^4.

Solution

Because 2025=34⋅522025 = 3^4 \cdot 5^2, we have 20253=312⋅562025^3 = 3^{12} \cdot 5^6 and 20254=316⋅582025^4 = 3^{16} \cdot 5^8. Each diagonal can have at most three 55s. Therefore, MNMN can have at most six factors 55, and this only happens when the number in the centre of the grid is 55. Hence MNMN might be divisible by 202532025^3 but not by 202542025^4. One then has to arrange that 3123^{12} is a factor of MNMN, to which the 99s, 66s and 33s can all contribute. Here are two examples of suitable Sudoku grids with relevant numbers on the diagonals highlighted. In the first example, we have MN=210⋅312⋅56MN = 2^{10} \cdot 3^{12} \cdot 5^6, and in the second MN=2⋅316⋅56MN = 2 \cdot 3^{16} \cdot 5^6.

Figure 1
Figure 2

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 reproduced verbatim; metadata (topic, difficulty) added by this project.