Product of factorials divided by factorial to produce perfect square

Let $ S = 1! ~2!~\dotsm ~100! $. Prove that there exists a unique positive integer $k$ such that $S/k!$ is a perfect square.

I thought this was a cute, fun problem and I did solve it, but any alternative methods that you guys would use?

Solution 1:

More generally:

Theorem 1. Let $n$ be a positive integer divisible by $4$ such that neither $n/2$ nor $n/2+1$ is a perfect square. Let $S = 1! \cdot 2! \cdot \cdots \cdot n!$. There exists a unique positive integer $k$ such that $S / k!$ is a perfect square. This integer $k$ is $n/2$.

The two ingredients that go into the proof of this are the following two lemmas:

Lemma 2. Let $n$ be a nonnegative integer. Then, \begin{align} \dfrac{1! \cdot 2! \cdot \cdots \cdot \left(2n\right)!}{n!} = 2^n \cdot \left(\prod_{i=1}^n \left(\left(2i-1\right)!\right)\right)^2 . \end{align}

Lemma 2 is Exercise 3.5 (c) in my Notes on the combinatorial fundamentals of algebra, version of 10 January 2019, and anyway is easy to prove (e.g., by induction on $n$ if you don't want to match factors).

Lemma 3. Let $u$ and $v$ be two distinct positive integers such that $u!/v!$ is the square of a rational number. Then, we have $\left| u-v \right| = 1$, and the number $\max\left\{u,v\right\}$ is a perfect square.

Proof of Lemma 3. We know that $u!/v!$ is the square of a rational number. In other words, $u! / v! = r^2$ for some rational $r$. Hence, $v! / u! = 1 / \underbrace{\left(u! / v!\right)}_{= r^2} = 1 / r^2 = \left(1/r\right)^2$. Thus, $v! / u!$ is the square of a rational number, too. Hence, our situation is symmetric in $u$ and $v$. Thus, we can WLOG assume that $u \geq v$ (since otherwise, we can swap $u$ with $v$). Assume this.

Hence, $u! / v! = u \left(u-1\right) \cdots \left(v+1\right)$. Thus, $u! / v!$ is an integer. In other words, $r^2$ is an integer (since $u! / v! = r^2$). Thus, $r$ is a square root of an integer, and therefore is either an integer or irrational. Since $r$ is not irrational (because $r$ is rational), we thus conclude that $r$ is an integer. Thus, $r^2$ is a perfect square. In other words, $u! / v!$ is a perfect square (since $u! / v! = r^2$).

We have $u \geq v$, so that $u-v \geq 0$ and thus $\left| u-v \right| = u-v$. Also, $\max\left\{u,v\right\} = u$ (since $u \geq v$).

Let us now prove that $\left| u-v \right| \leq 1$. Indeed, assume the contrary. Thus, $\left| u-v \right| > 1$. Hence, $u-v = \left| u-v \right| > 1$, so that $u > v+1$. Thus, $u \geq v+2$ (since $u$ and $v+1$ are integers). But $u! / v! = u \left(u-1\right) \cdots \left(v+1\right)$. Thus, $u! / v!$ is a product of at least $2$ consecutive positive integers (the "at least $2$" part here comes from the fact that $u \geq v+2$). But a result of Erdos (P. Erdos, Note on products of consecutive integers, J. London Math. Soc. 14 (1939), pp. 194--198) shows that any product of at least $2$ consecutive positive integers is never a perfect square. Hence, we conclude that $u! / v!$ is not a perfect square. This contradicts the fact that $u! / v!$ is a perfect square. This contradiction shows that our assumption was false. Hence, $\left| u-v \right| \leq 1$ is proven.

We have $\left|u-v\right| \neq 0$ (since $u$ and $v$ are distinct). Combining this with $\left| u-v \right| \leq 1$, we obtain $\left| u-v \right| = 1$.

It remains to show that the number $\max\left\{u,v\right\}$ is a perfect square.

Indeed, $u-v = \left|u-v\right| = 1$, and thus $u = v+1$. Hence, $u! / v! = \left(v+1\right)! / v! = v+1 = u$, so that $u = u! / v! = r^2$. Thus, $u$ is a perfect square (since $r$ is an integer). In other words, $\max\left\{u,v\right\}$ is a perfect square (since $\max\left\{u,v\right\} = u$). This completes the proof of Lemma 3. $\blacksquare$

Proof of Theorem 1. We know that $n/4$ is a positive integer (since $n$ is a positive integer divisible by $4$). Hence, $n/2$ is a positive integer as well (since $n/2 = 2 \left(n/4\right)$). Hence, Lemma 2 (applied to $n/2$ instead of $n$) yields \begin{align} \dfrac{1! \cdot 2! \cdot \cdots \cdot \left(2\left(n/2\right)\right)!}{\left(n/2\right)!} = 2^{n/2} \cdot \left(\prod_{i=1}^{n/2} \left(\left(2i-1\right)!\right)\right)^2 = \left(2^{n/4} \prod_{i=1}^{n/2} \left(\left(2i-1\right)!\right)\right)^2 . \end{align} In view of $1! \cdot 2! \cdot \cdots \cdot \left(2\left(n/2\right)\right)! = 1! \cdot 2! \cdot \cdots \cdot n! = S$, this rewrites as \begin{align} \dfrac{S}{\left(n/2\right)!} = \left(2^{n/4} \prod_{i=1}^{n/2} \left(\left(2i-1\right)!\right)\right)^2 . \end{align} The number $2^{n/4} \prod\limits_{i=1}^{n/2} \left(\left(2i-1\right)!\right)$ on the right hand side of this equality is an integer (since $n/4$ is an integer). Thus, the right hand side of this equality is a perfect square. Therefore, the left hand side is a perfect square as well. In other words, $\dfrac{S}{\left(n/2\right)!}$ is a perfect square. Hence, there exists at least one positive integer $k$ such that $S / k!$ is a perfect square, namely $k = n/2$.

It remains to prove that there exists at most one such integer. In other words, it remains to prove that if $w$ is any positive integer $k$ such that $S/k!$ is a perfect square, then $w = n/2$.

We shall first prove a weaker claim:

(1) If $u$ and $v$ are two distinct positive integers $k$ such that $S/k!$ is a perfect square, then $\max\left\{u,v\right\}$ is a perfect square and we have $\left| u-v \right| = 1$.

[Proof of (1): Let $u$ and $v$ be two distinct positive integers $k$ such that $S/k!$ is a perfect square.

We know that $u$ is a positive integer $k$ such that $S/k!$ is a perfect square. In other words, $u$ is a positive integer such that $S/u!$ is a perfect square. Hence, there exists some integer $x$ such that $S / u! = x^2$. Similarly, there exists some integer $y$ such that $S / v! = y^2$. Consider these $x$ and $y$. Note that $S = 1! \cdot 2! \cdot \cdots \cdot n! \neq 0$ (since $1!, 2!, \ldots, n!$ are nonzero). Thus, $S / u! \neq 0$, so that $x^2 = S / u! \neq 0$ and thus $x \neq 0$. Hence, $y/x$ is a well-defined rational number (since $x$ and $y$ are integers). This number satisfies $\left(y/x\right)^2 = \underbrace{y^2}_{=S/v!} / \underbrace{x^2}_{=S/u!} = \left(S/v!\right) / \left(S/u!\right) = u!/v!$. Hence, $u!/v!$ is the square of a rational number (namely, of $y/x$). Thus, Lemma 3 shows that we have $\left| u-v \right| = 1$, and that the number $\max\left\{u,v\right\}$ is a perfect square. This proves (1).]

Now, let $w$ be a positive integer $k$ such that $S/k!$ is a perfect square. We shall prove that $w = n/2$.

Indeed, assume the contrary. Thus, $w \neq n/2$. Hence, $w$ and $n/2$ are distinct. But $w$ and $n/2$ are two positive integers $k$ such that $S/k!$ is a perfect square. Hence, (1) (applied to $u = w$ and $k = n/2$) yields that $\max\left\{w,n/2\right\}$ is a perfect square and that we have $\left| w-n/2 \right| = 1$. We have $\max\left\{w,n/2\right\} \neq n/2$ (since $\max\left\{w,n/2\right\}$ is a perfect square but $n/2$ is not). If we had $w \leq n/2$, then we would have $\max\left\{w,n/2\right\} = n/2$, which would contradict $\max\left\{w,n/2\right\} \neq n/2$. Hence, we cannot have $w \leq n/2$. Thus, we have $w > n/2$. Hence, $\left| w-n/2 \right| = w-n/2$, so that $w-n/2 = \left| w-n/2 \right| = 1$ and thus $w = n/2 + 1$. But $w > n/2$, so that $\max\left\{w,n/2\right\} = w = n/2 + 1$. Thus, $n/2 + 1$ is a perfect square (since $\max\left\{w,n/2\right\}$ is a perfect square). This contradicts the fact that $n/2 + 1$ is not a perfect square.

This contradiction completes our proof of $w = n/2$.

Forget that we fixed $w$. We thus have shown that if $w$ is any positive integer $k$ such that $S/k!$ is a perfect square, then $w = n/2$. As we know, this completes our proof of Theorem 1. $\blacksquare$

Solution 2:

EDIT, Friday morning; testing with changing the 100 to other numbers. It appears that if, as above, $S = 1! \cdot 2! \cdot 3! \cdot \cdots \cdot (4n)!,$ then $S / (2n)!$ is a square.

EEDDIITT TTOOOOO: need the larger number divisible by 4, this thing fails when replacing 100 by 6 or 10. INDUCTION: Given that $$ T = 1! \cdot 2! \cdot 3! \cdot \cdots \cdot (4n - 4)!, $$ and $$ T / (2n-2)! = \; \; \mbox{square}. $$ Let $$ S = 1! \cdot 2! \cdot 3! \cdot \cdots \cdot (4n)!. $$ Then $$ \color{magenta}{ S / (2n)! = \left( T / (2n-2)! \right) \cdot ((4n-4)!)^4 \cdot (4n-3)^4 \cdot (4n-2)^2 \cdot (4n-1)^2 \cdot 4}$$ is still a square. I do not immediately see uniqueness in adequate detail, but we know we cannot perturb the $2n$ as high as the next prime, or lower than the previous prime. Maybe some way to fill in an argument. Or, uniqueness in general could be false, occasionally more than one answer when prime gaps are unusually large. Not sure.

ORIGINAL: Well, it's 50. Because of prime 101, $k$ cannot exceed 100. Because of all the even exponents, actually $k$ cannot exceed 52. Because of the odd exponents just below, $k$ must be at least 47. In brief, because of prime 2, $k$ is at least 50. Because of prime 17, $k$ is at most 50. After that it is a matter of matching in detail and checking that 50 actually works for each prime from 2 to 47, which it does.

Note $$ 50! = 2^{47} \cdot 3^{22} \cdot 5^{12} \cdot 7^8 \cdot 11^4 \cdot 13^3 \cdot 17^2 \cdot 19^2 \cdot 23^2 \cdot 29 \cdot 31 \cdot 37 \cdot 41 \cdot 43 \cdot 47. $$

$S:$

    2        4731    1
    3        2328    0
    5        1124    0
    7         734    0
   11         414    0
   13         343    1
   17         250    0
   19         220    0
   23         174    0
   29         129    1
   31         117    1
   37          91    1
   41          79    1
   43          73    1
   47          61    1
   53          48    0
   59          42    0
   61          40    0
   67          34    0
   71          30    0
   73          28    0
   79          22    0
   83          18    0
   89          12    0
   97           4    0

   47           2   42
   48           2   46
   49           2   46
   50           2   47
   51           2   47
   52           2   49

   47           3   21
   48           3   22
   49           3   22
   50           3   22
   51           3   23
   52           3   23

   47           5   10
   48           5   10
   49           5   10
   50           5   12
   51           5   12
   52           5   12

   47           7    6
   48           7    6
   49           7    8
   50           7    8
   51           7    8
   52           7    8

   47          11    4
   48          11    4
   49          11    4
   50          11    4
   51          11    4
   52          11    4

   47          13    3
   48          13    3
   49          13    3
   50          13    3
   51          13    3
   52          13    4

   47          17    2
   48          17    2
   49          17    2
   50          17    2
   51          17    3
   52          17    3

   47          19    2
   48          19    2
   49          19    2
   50          19    2
   51          19    2
   52          19    2

   47          23    2
   48          23    2
   49          23    2
   50          23    2
   51          23    2
   52          23    2

   47          29    1
   48          29    1
   49          29    1
   50          29    1
   51          29    1
   52          29    1

   47          31    1
   48          31    1
   49          31    1
   50          31    1
   51          31    1
   52          31    1

   47          37    1
   48          37    1
   49          37    1
   50          37    1
   51          37    1
   52          37    1

   47          41    1
   48          41    1
   49          41    1
   50          41    1
   51          41    1
   52          41    1

   47          43    1
   48          43    1
   49          43    1
   50          43    1
   51          43    1
   52          43    1

   47          47    1
   48          47    1
   49          47    1
   50          47    1
   51          47    1
   52          47    1

=================

Solution 3:

Other answers here have given general results, but it seems worthwhile to give a self-contained answer specific to the problem with $S=1!2!3!4!\cdots99!100!$, assuming the OP wants $S/k!$ to be a perfect integer square.

As observed in the other answers,

$$S=1!(1!\cdot2\cdot1)3!(3!\cdot2\cdot2)\cdots99!(99!\cdot2\cdot50)=(1!)^2(3!)^2\cdots(99!)^22^{50}\cdot50!$$

shows that $S/50!=(1!3!99!2^{25})^2$ is a perfect square. It remains that show that $k=50$ is the unique value such that $S/k!$ is a perfect integer square.

Let's assume that $S/k!$ is a perfect integer square. Then $50!/k!=(S/k!)/(S/50!)$ is a rational square. Now, as Will Jagy notes, it's clear we need $k\lt101$, since otherwise $S/k!$ has the prime $101$ in its denominator (and hence is not an integer). But now it's clear we need $47\le k\lt53$: If $k\lt47$, $50!/k!$ will have a single $47$ in its numerator, while if $53\le k\lt101$, it will have a single $53$ in its denominator. And the remaining five cases (other than $k=50$) are easily ruled out:

$$\begin{align} 50!/47!&=50\cdot49\cdot48=2^5\cdot3\cdot5^2\cdot7^2\\ 50!/48!&=50\cdot49=2\cdot5^2\cdot7^2\\ 50!/49!&=50=2\cdot5^2\\ 51!/50!&=51=3\cdot17\\ 52!/50!&=52\cdot51=2^2\cdot3\cdot13\cdot17 \end{align}$$

Remark: If we drop the assumption that the OP wants $S/k!$ to be an integer square, it's still possible to prove that $k=50$ is the only choice, but the simplest proof I can think of invokes Bertrand's Postulate to limit $k\le100$. I'd be pleased to see a proof that doesn't make use of the guaranteed existence of a prime between $k/2$ and $k$.