4
$\begingroup$

N is not a square number and consists of 2019 factorial multiplication as shown below:

$N=1!\times 2!\times 3!\cdots 2018!\times2019!$

At least how many factorial needed to be removed from the multiplication to make N a square number?

$\endgroup$

3 Answers 3

8
$\begingroup$

Theorem: for any natural number $N$, the expression

$\frac{(1!)(2!)(3!)\dots(4N)!}{(2N)!}$

is a perfect square.

Proof: by induction on $N$. The result is true for $N=1$, since

$(1!)(3!)(4!)=144$ is a square.

Assume the result is true for $N=n-1$. Then we have, for $N=n$,

$\frac{(1!)(2!)(3!)\dots(4n)!}{(2n)!}=\frac{(1!)(2!)(3!)\dots(4n-4)!}{(2n-2)!}\cdot\frac{(4n-3)!(4n-2)!(4n-1)!(4n)!}{(2n-1)(2n)}$.

The extra factor there is

$\frac{(4n-3)!(4n-2)!(4n-1)!(4n)!}{(2n-1)(2n)}=\frac{(4n-2)^3(4n-1)^2(4n)}{(2n-1)(2n)}[(4n-3)!]^4=4(4n-2)^2(4n-1)^2[(4n-3)!]^4$

which is a perfect square. Thus the theorem is proved.


So we can remove

four factorials to get a perfect square: namely $2019!,2018!,2017!,1008!$.


An improvement, thanks to @Neal in a comment: we can actually remove just

three factorials. Starting from the perfect square we already found (with $2019!,2018!,2017!,1008!$ removed), let's re-multiply by $2018!$ and $2017!$ to get $2018$ times a perfect square. Then re-multiply by $1008!$ and divide by $1009!$ to get $2$ times a perfect square (since $2018=1009\times2$). Then finally remove $2!$; we now have a perfect square with just the three factorials $2019!,1009!,2!$ removed.


Can we do any better?

Since 2017 is prime, we must remove an odd number of (either one or three of) the top three $2017!,2018!,2019!$ in order to get an even power of 2017 for a perfect square.

So if we remove just one factor, then it must be

one of $2017!,2018!,2019!$, and that won't give a perfect square.

If we remove just two factors, then one of them must be

one of those top three. But then the perfect square we found above by removing four factorials must be exactly this new perfect square divided by two of $2017!,2018!,2019!$ and divided by $1008!$ and multiplied by one other factorial. Again, that's not going to be a perfect square however we do it.


So the final answer is

three factorials must be removed.

$\endgroup$
2
  • $\begingroup$ Your solution can actually be improved to 3. Note that 2017! * 2018! = 2018 * (2017!)^2, and 2018 = 2 * 1009, so we can remove 2!, 1009!, and 2019!. Also see codeforces.com/contest/1622/problem/F $\endgroup$
    – Neal
    Commented Dec 27, 2021 at 16:41
  • $\begingroup$ @Neal That's really neat, thank you! Sorry for slow response to your comment - I kept this open in a tab until I had time to come back and check the details. $\endgroup$ Commented Apr 19, 2022 at 12:33
0
$\begingroup$

Some thoughts

One reason the given product is not a square is that the prime number $2017$ occurs three times: in $2017!$ and $2018!$ and $2019!$

There needs to be an even number of occurrences of any prime, to enable a square root of their product to be possible.

This applies to every prime factor too.
For example when $N = 6$
$1! \times 2! \times 3! \times 4! \times 5! \times 6! = 2^{12} \times 3^5 \times 5^2$
So the product won't be a perfect square because of the odd power of $3$.

Going back to the three $2017$s, either all three or just one of them must be removed.
But if one: which one? I am tempted to make a program which uses a recursive approach

 Find highest prime factor with an odd power
 Explore permutations of factorials removing 1,3,5 etc occurrences as a factor
 For each one, repeat with next lowest odd-powered prime
 If a solution is found, with fewest removals so far, record the series
But it has to be later, if an answer is still needed.

$\endgroup$
-3
$\begingroup$

Only factorial that would be perfect Square is 1! Therefore, from 2! To 2019! Have to be removed.

$\endgroup$
2
  • 2
    $\begingroup$ Example: $1! \times 3! \times 4! = 6 \times 24 = 144 = 12^2$. $\endgroup$ Commented Jun 7, 2019 at 20:46
  • $\begingroup$ Not my DV, some thoughts in an answer. $\endgroup$ Commented Jun 7, 2019 at 21:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.