Prove that $(k^3)!$ is divisible by $(k!)^{k^2 + k + 1}$. Proof using properties of greatest integer function? 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.
 A: 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.
A: 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}. $$
