Let $N = 15! = 15\cdot 14\cdot 13 ... 3\cdot 2\cdot 1$. Prove that $N$ can be written as a product of nine different integers all between $16$ and $30$ inclusive.
Problem
Source: 2021 Irish Mathematical Olympiad P1
Tags: number theory, factorial
mo.s.k14142
30.05.2021 21:07
Just keep testing (splitting factors and such) until something works
$N=28\cdot 27\cdot 26 \cdot 25 \cdot 22 \cdot 21 \cdot 20 \cdot 18 \cdot 16$
circlethm
27.07.2021 23:42
Solution. We note that the prime factorisation of $15!$ is $$ 15! = 2^{11} \cdot 3^6 \cdot 5^3 \cdot 7^2 \cdot 11 \cdot 13. $$With this, we claim that $15!$ is the product of the nine distinct integers $16, 18, 20, 21, 22, 25, 26, 27, 28$. Indeed, we can find the prime factorisation of their product which is \begin{align*} &16\cdot 18\cdot 20\cdot 21\cdot 22\cdot 25\cdot 26\cdot 27\cdot 28 \\ =\ &(2^4) \cdot (2 \cdot 3^2) \cdot (2^2 \cdot 5) \cdot (3 \cdot 7) \cdot (2 \cdot 11) \cdot (5^2) \cdot (2 \cdot 13) \cdot (3^3) \cdot (2^2 \cdot 7) \\ =\ &2^{11} \cdot 3^6 \cdot 5^3 \cdot 7^2 \cdot 11 \cdot 13 \\ =\ &15!. \end{align*}
OlympusHero
28.07.2021 00:06
Note that $15!=2^{11} \cdot 3^6 \cdot 5^3 \cdot 7^2 \cdot 11 \cdot 13$. Now notice that we obviously cannot use the primes, so $17, 19, 23, 29$ are eliminated. This leaves $16, 18, 20, 21, 22, 24, 25, 26, 27, 28, 30$. We must have factors of $13$ and $11$, so we need a $22 \cdot 26 = 2^2 \cdot 13 \cdot 11$. After dividing out this number, our new expression is $2^9 \cdot 3^6 \cdot 5^3 \cdot 7^2$. We must have two factors of $7$, so we use $21 \cdot 28 = 2^2 \cdot 3 \cdot 7^2$. After dividing out this number, our new expression is $2^7 \cdot 3^5 \cdot 5^3$. We've used $21,22,26,28$ and can still use $16,18,20,24,25,27,30$. If we do not use the $25$, we can only have a maximum of $2$ factors of $5$, so we must use $25=5^2$. After dividing out this number, our new expression is $2^7 \cdot 3^5 \cdot 5$. If we do not use the $27$, we can only have a maximum of $3$ factors of $5$, so we must use $27=3^3$. After dividing out this number, our new expression is $2^7 \cdot 3^2 \cdot 5$. We've used $21, 22, 25, 26, 27, 28$ and can still use $16,18,20,24,30$. If we do not use the $16$, we can only have a maximum of $4$ factors of $2$, so we must use $16=2^4$. After dividing out this number, our new expression is $2^3 \cdot 3^2 \cdot 5$. We've used $16, 21, 22, 25, 26, 27, 28$ and can still use $18,20,24,30$. Note that $2^3 \cdot 3^2 \cdot 5 = 360 = 18 \cdot 20$, and using $18, 20$ reaches the requisite number of $9$ different integers. We've shown that $16 \cdot 18 \cdot 20 \cdot 21 \cdot 22 \cdot 25 \cdot 26 \cdot 27 \cdot 28 = 15!$, so we're done.