3
$\begingroup$

I came across this problem in a regional Olympiad Exam. I'm giving the outline of my solution and a question related to it.

Problem

Let $k$ be any positive integer. Prove that $(k^3)!$ is divisible by $(k!)^{k^2 + k + 1}$.

Question

My first approach was to use the fact that for any prime $p \leq k$, the highest power of $p$ contained in $k!$ is given by $\sum _{j=1}^{\infty} \big[ \frac{k}{p^j}\big]$, where $[.]$ is the greatest integer (floor) function, then somehow use the properties of this function to show that for every prime $p$ contained in $k!$, it's power in $k^3!$ is at least $k^2+k+1$ times that in $k!$.

However, this approach did not lead me anywhere beyond a couple of steps. The reason might be that I'm missing some properties of the greatest integer function. Please post your proof if you can make this approach work.

I finally gave up this approach and came up with the following solution.

Solution

I somehow managed to prove a generalized statement using induction.

We will prove that $\forall k,n \in \mathbb{Z}^+$, $(k^n)!$ is divisible by $(k!)^{k^{n-1} + k^{n-2} + \cdots + k^2 + k + 1}$.

Let $P(k,n)$ be the statement that $(k!)^{k^{n-1} + k^{n-2} + \cdots + k^2 + k + 1} \mid (k^n)!$.

$P(k,1)$ is obviously true for all $k \in \mathbb{Z}^+$.

Chose any $k$ and assume that $P(k,n)$ is true for some positive integer $n$.

Now, $(k^{n+1})!$ can be written as follows:

$$\begin{eqnarray*} (k^{n+1})! &=& \Big(1 \cdot 2 \cdot 3 \cdots k^n \Big) \cdot % \Big((k^n + 1) \cdot (k^n + 2) \cdots (2k^n) \Big) \cdot % \Big((2k^n + 1) \cdot (2k^n + 2) \cdots (3k^n) \Big) \cdots % \Big(((k - 1)k^n + 1) \cdot ((k-1)k^n + 2) \cdots (k\cdot k^n) \Big) \\ &=& \alpha_1 \cdot \alpha_2 \cdot \alpha_3 \cdots \alpha_k \end{eqnarray*}$$

where

$$\begin{eqnarray*} \alpha_j &=& \big((j - 1)k^n + 1\big) \cdot \big((j-1)k^n + 2\big) \cdots \big(j\cdot k^n \big) \\ &=& \prod \limits_{m = 1}^{k^n} \big((j - 1)k^n + m\big) \\ &=& j \cdot k^n \cdot \prod \limits_{m = 1}^{k^n -1} \big((j - 1)k^n + m\big) \end{eqnarray*}$$

Now, $\; \prod \limits_{m = 1}^{k^n -1} \big((j - 1)k^n + m\big) \;$ is a product of $(k^n - 1)$ consecutive integers. Hence $(k^n - 1)! \;$ divides $\; \prod \limits_{m = 1}^{k^n -1} \big((j - 1)k^n + m\big) \;$. Therefore, $(k^n)! \quad$ divides $\quad k^n \cdot \prod \limits_{m = 1}^{k^n -1} \big((j - 1)k^n + m\big)$. Therefore, $\alpha_j$ can be written as

$$\alpha_j = j \cdot \beta_j \cdot (k^n)!$$ for some $\beta_j \in \mathbb{Z}^+$.

By the inductive hypothesis, $(k^n)! = \nu \cdot (k!)^{k^{n-1} + k^{n-2} + \cdots + k^2 + k + 1}$ for some $\nu \in \mathbb{Z}^+$. Thus,

$$\alpha_j = j \cdot \beta_j \cdot \nu \cdot (k!)^{k^{n-1} + k^{n-2} + \cdots + k^2 + k + 1}$$

Thus,

$$\begin{eqnarray*} (k^{n+1})! &=& \alpha_1 \cdot \alpha_2 \cdots \alpha_k \\ &=& \nu^k \cdot \Big(\prod \limits_{j = 1}^{k} \beta_j \Big) % \cdot \Big(\prod \limits_{j = 1}^{k} j \Big) \cdot % \Big( (k!)^{k^{n-1} + k^{n-2} + \cdots + k^2 + k + 1} \Big)^k \\ &=& \nu^k \cdot \Big(\prod \limits_{j = 1}^{k} \beta_j \Big) % \cdot (k!) \cdot % \Big( (k!)^{k^{n} + k^{n-1} + \cdots + k^3 + k^2 + k} \Big) \\ &=& \nu^k \cdot \Big(\prod \limits_{j = 1}^{k} \beta_j \Big) % \cdot % \Big( (k!)^{k^{n} + k^{n-1} + \cdots + k^3 + k^2 + k + 1} \Big) \end{eqnarray*}$$

Thus $P(k,n+1)$ is true if $P(k,n)$ is true.

$\endgroup$
2
  • $\begingroup$ I am curious if there is a way to prove the divisibility relation with group actions. Perhaps ${\rm Sym}([k]^3)$ acts freely on some structure like ${\rm Map}([k]^3,[k^2+k+1])$. Or there might be a group-theoretic proof when we restrict to $k=p$ prime, in which case $p$, $p^3$, $p^2+p+1$ represent $\Bbb F_p$, $\Bbb F_p^3$, $\Bbb P(\Bbb F_p^3)$ respectively. $\endgroup$ Jul 3, 2017 at 21:07
  • $\begingroup$ @arctictern I think there might be a similar approach by noting that $\frac{(k^3)!}{(k!)^{k^2}}$ is a multinomial coefficient and then exploiting its symmetries to show that it's divisible by $(k!)^{k+1}$. $\endgroup$ Jul 3, 2017 at 21:38

2 Answers 2

4
$\begingroup$

Look at $G=S_{k^3}$ which has order $n=k^3!$. Look at the subgroup $H$ of $G$ isomorphic to $(S_k)^{k^2}$ which has order $m=(k!)^{k^2}$. Now you can "permute" the $k^2$ different copies of $S_k$ in $H$ in $l=(k^2)!$ ways, which gives you a supgroup $I$ with order $ml$ with $H\subset I$, so we established $ml|n$. Now looking at $S_{k^2}$ and using the exact same idea gives you $(k!)^{k+1}|(k^2)!=l$. Now combine these results to complete the proof.

$\endgroup$
1
  • $\begingroup$ While your solution is very slick, I don't think most people participating in the olympiad will have knowledge of some basic group theory. $\endgroup$
    – Mastrem
    Jul 3, 2017 at 21:55
2
$\begingroup$

In the interval $[1,k^3]$ there are $k^3-k^2$ numbers $\not\equiv 0\pmod{k}$, $k^2-k$ numbers that are $\equiv 0\pmod{k}$ but $\not\equiv 0\pmod{k^2}$, $k-1$ numbers that are $\equiv 0\pmod{k^2}$ but $\not\equiv 0\pmod{k^3}$ and just $1$ element that is a multiple of $k^3$. In particular $(k^3)!$ is for sure a multiple of

$$ k^3 \cdot k^{2(k-1)} \cdot k^{k^2-k} =k^{k^2+k+1}.$$ The product of $(k-1)$ consecutive numbers $\neq 0\pmod{k}$ is always a multiple of $(k-1)!$, since $$ \frac{1}{(k-1)!}\prod_{j=1}^{k-1}(a+j) = \binom{a+k-1}{k-1} = \binom{a+k-1}{a}\in\mathbb{Z}. $$ It follows that the product of the elements of $[1,k^3]$ that are not $\equiv 0\pmod{k}$ is a multiple of $(k-1)!^{k^2}$ and the claim simply follows by rearranging the remaining terms and applying the considerations above. It is enough to consider that $$(k!)^{k^2+k+1} = k^{k^2+k+1}\cdot (k-1)!^{k^2+k+1}. $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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