# Problem Of The Week #408 Mar 13th, 2020

Status
Not open for further replies.

Staff member

#### anemone

##### MHB POTW Director
Staff member
Congratulations to the following members for their correct solution!

1. castor28
2. lfdahl
4. Oxide

Solution from Oxide :

By expanding out the product $$\displaystyle n=1! 2! \cdots 9!$$, we get $$\displaystyle 2^8 3^7 4^6 5^5 6^4 7^3 8^2 9^1$$, which can be factored into primes as $$\displaystyle 2^{30} 3^{13} 5^5 7^3$$. Since a perfect square that divides $$\displaystyle n$$ must be of the form $$\displaystyle 2^a 3^b 5^c 7^d$$ where $$\displaystyle a,b,c,d$$ are even, we can choose $$\displaystyle a,b,c,d$$ from the following sets respectively:
$$\displaystyle \{0,2,\dots, 30\}$$
$$\displaystyle \{0,2,\dots,12\}$$
$$\displaystyle \{0,2,4\}$$
$$\displaystyle \{0,2\}$$
which gives us $$\displaystyle 16 \cdot 7 \cdot 3 \cdot 2 = 672$$ perfect squares that divide $$\displaystyle n$$.

Alternate solution from castor28 :
We factorize $n!=2^\alpha3^\beta5^\gamma7^\delta$ for $2\le n\le9$ as follows (note that each line is easily computed from the previous line):
$$\begin{array}{c|r|r|r|r} n!&\alpha&\beta&\gamma&\delta\\ \hline 2!&1&0&0&0\\ 3!&1&1&0&0\\ 4!&3&1&0&0\\ 5!&3&1&1&0\\ 6!&4&2&1&0\\ 7!&4&2&1&1\\ 8!&7&2&1&1\\ 9!&7&4&1&1\\ \hline \prod{n!}&30&13&5&3 \end{array}$$
The square divisors of the product are of the form $2^x 3^y 5^z7^w$, with $x$, $y$, $z$, $w$ even and $(x,y,z,w)\le (30,13,5,3)$.
Since the number of even integers between $0$ and $k$ is $\left\lfloor\dfrac{k}{2}\right\rfloor+1$, the number of square divisors of the product is $16\times 7\times 3\times 2 = \bf 672$.

Status
Not open for further replies.