Maths Olympiad Prep

Library / /236 of 462

Number theory Difficulty 5.8 AIME, harder Prove it Ireland

Let N=15!=151413321N = 15! = 15 \cdot 14 \cdot 13 \cdots 3 \cdot 2 \cdot 1. Prove that NN can be written as a product of nine different integers all between 16 and 30 inclusive.

Solution

There is a unique such representation:
15!=28×27×26×25×22×21×20×18×16. 15! = 28 \times 27 \times 26 \times 25 \times 22 \times 21 \times 20 \times 18 \times 16.
All solutions start by factorising 15!15! into primes:
15!=211×36×53×72×11×13. 15! = 2^{11} \times 3^6 \times 5^3 \times 7^2 \times 11 \times 13.
This can be obtained manually or by Legendre's formula for the highest power of pp that divides n!n! viz.
np+np2+np3+ \left\lfloor \frac{n}{p} \right\rfloor + \left\lfloor \frac{n}{p^2} \right\rfloor + \left\lfloor \frac{n}{p^3} \right\rfloor + \dots
Systematic Solution
As there is only one multiple of 1111 and one multiple of 1313 between 1616 and 3030 inclusive, two of the factors in the product must be 2222 and 2626.
There are two multiples of 77, and no multiples of 727^2 between 1616 and 3030, so both 2121 and 2828 must feature in the product.
There are three multiples of 55 between 1616 and 3030, one of which is 525^2. So the multiples of 55 in the product must be either 2020 and 2525, or 2525 and 3030.
Taking out the factors already considered:
15!22×26×21×28×25=27×35×5=155520. \frac{15!}{22 \times 26 \times 21 \times 28 \times 25} = 2^7 \times 3^5 \times 5 = 155520.
To finish the problem we seek four further factors between 1616 and 3030 (inclusive) excluding those already used.
Of the remaining numbers between 1616 and 3030, only {18,24,27,30}\{18, 24, 27, 30\} are multiples of 33. If we do not choose 2727, then we can reach at most 343^4 in the product, which is short of the 353^5 we need. Therefore, 2727 must be in the list of factors. Dividing through by 2727, we are left to find three factors of:
15!22×26×21×28×25×27=27×32×5=5760. \frac{15!}{22 \times 26 \times 21 \times 28 \times 25 \times 27} = 2^7 \times 3^2 \times 5 = 5760.
The feasible factors must only have prime factors of 22, 33 and/or 55. Excluding factors already used, we have the following list:

IncludeFactorPrime factorisation
YES1624×30×502^4 \times 3^0 \times 5^0
YES1821×32×502^1 \times 3^2 \times 5^0
YES2022×30×512^2 \times 3^0 \times 5^1
NO2423×31×502^3 \times 3^1 \times 5^0
NO3021×31×512^1 \times 3^1 \times 5^1
Product576027×32×512^7 \times 3^2 \times 5^1

Start with 15!15! and starting from 3030, divide repetitively by the largest remaining number that is a factor.
Taking the largest possible number at each stage
15!=30×28×27×26×25×24×22×21×8 15! = 30 \times 28 \times 27 \times 26 \times 25 \times 24 \times 22 \times 21 \times 8
This has nearly worked, but the final factor of 88 is problematic.
So we tweak a bit, first replacing 88 and 3030 by 2020 and 1212
15!=28×27×26×25×24×22×21×20×12 15! = 28 \times 27 \times 26 \times 25 \times 24 \times 22 \times 21 \times 20 \times 12
This is still not a solution, but our smallest factor has increased a bit. As a final step, replace 2424 and 1212 by 1818 and 1616 which gives the solution stated.

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.