Consider an $n \times n$ grid. Let $f(n)$ be the number of ways you can sort numbers from $1$ through $n^2$ so that rows and columns are increasing. Then by hook-length formula, we have \[f(n) = \frac{(n^2)!}{\binom{2n-1}{n-1} \binom{2n-2}{n-1} \cdots \binom{n}{n}} = (n^2)!\prod_{j=0}^{k-1} \frac{j!}{(j+n)!}\]was too lazy to actually prove it though

tenniskidperson3 wrote:

I also used the hook length formula!

This is a very boring problem. Show that for any prime power $P$, we have that \[ \left\lfloor \frac{k^2}{P} \right\rfloor \ge \sum_{j=0}^{k-1} \left( \left\lfloor \frac{j+k}{P} \right\rfloor - \left\lfloor \frac{j}{P} \right\rfloor \right) \]Then the conclusion will follow. One does this by writing $k = aP+r$, where $0 \le r < P$, and then analyzing two cases where either $r \le P/2$ or $r \ge P/2$. In each case one just directly evaluates the sums. They reduce to the inequalities \[ (1+a)\left( k+(P-r) \right) \le \left\lfloor \frac{k^2}{P} \right\rfloor \]and \[ (1+a)\left( k-r \right) + 2a \cdot r \le \left\lfloor \frac{k^2}{P} \right\rfloor \]respectively, and each case is true even without the floor on RHS (which implies the original since the left-hand side is an integer).

Will citing Hook-Length get points? I did it as above.

Like I said, I'd expect 1 at most, since it's hard to prove and trivializes the problem, and there's an easier way to do it.

One can also use Legendre's Formula to calculate the $p$-adic valuation of the numerator and denominator. Then it reduces to AM-GM.

Did anyone have a solution that went along the lines of the expression can be rewritten as $\frac{(k^2)!}{k^k\cdot\prod_{i=1}^{k-1}(k^2-i^2)^{k-i}}$ and counting the $v_p$ of $\prod_{i=1}^{k-1}(k^2-i^2)^{k-i}$? I tried this for an hour and a half but the inequalities were too strong.

I think you should just compute the $v_p$ directly. You can garner from some small sample cases (like $(k,P)=(15,4)$) that it's much more of an equality than an inequality; trying to use bounding is the wrong thing to do.

I tried creating a complicated game with $k$ players and $k^2$ objects. It ended up not working very well.

v_Enhance wrote: This is a very boring problem. Show that for any prime power $P$, we have that \[ \left\lfloor \frac{k^2}{P} \right\rfloor \ge \sum_{j=1}^{k} \left( \left\lfloor \frac{j+k}{P} \right\rfloor - \left\lfloor \frac{j}{P} \right\rfloor \right) \] Darn another fake NT problem. If I wrote this down could I salvage any points or no?

hm i let $w_p$ be the number of factors in the expression that $p$ divides, so like basically $w_p$ + $w_{p^2}$ + ... = $v_p$ and proved that for any integer $i$, $w_{p^i}(numerator) \ge w_{p^i}(denominator)$, so essentially similar to v_Enhance's solution except less elegant

Maybe 1, the computation is no trivial. The key idea is to note that the thing in the brackets repeats modulo P and the result follows upon computation.

Is there a solution that uses the fact that the given value is $\prod_{j=1}^{k-1}\frac{(kj+k)! \cdot j!}{(kj)! \cdot (k+j)!}$ or something like that?

blawho12 wrote: Is there a solution that uses the fact that the given value is $\prod_{j=1}^{k-1}\frac{(kj+k)! \cdot j!}{(kj)! \cdot (k+j)!}$ or something like that? From there I multiplied the top and bottom by $(kj+k+j)!$ and simplified to the ratio of two binomial coefficients. It seemed promising but I couldn't get farther.

Reminded me a ton of this problem http://artofproblemsolving.com/community/q3h1094342p4895796

Let $p$ be a prime. It suffices to show that for every prime $p$, we have $$v_p(k^2!) + \sum_{j=0}^{k-1} v_p(j) \ge \sum_{j=0}^{k-1} v_p(j+k)$$Let $P = p^a$ for some positive integer $a$. It suffices to show that $$\left\lfloor \frac{k^2}{P} \right\rfloor + \sum_{j=0}^{k-1} \left\lfloor \frac{j}{P} \right\rfloor -\sum_{j=0}^{k-1} \left\lfloor \frac{j+k}{P} \right\rfloor \ge 0$$for every possible $a$. If we let $k = Pq + r$ for some $0 \le r < P$, then we have \begin{align*} & Pq^2 + 2qr + \left\lfloor \frac{r^2}{P} \right\rfloor \\ &+ \left[P + 2P + 3P + \cdots + (q-1)P + rq\right] \\ &- \left[q(P-r) + (q+1)P + (q+2)P + \cdots + (2q-1)P + \sum_{m = 0}^{2r-1} 2q + \left\lfloor \frac{m}{P} \right\rfloor\right] \end{align*}and after much cancellation (you can check that all $P$ terms cancel, and then the $qr$ also dies), we get this is equal to $$\left\lfloor \frac{r^2}{P} \right\rfloor - \sum_{m = 0}^{2r-1} \left\lfloor \frac{m}{P} \right\rfloor$$So we just have to prove this is at least $0$. If $2r-1 < P$ then we are done since $\left\lfloor \frac{m}{p}\right\rfloor = 0$ for $0 \le m \le 2r - 1$. Otherwise, let $2r \equiv j \pmod{P}$ so $r = \frac{P+j}{2}$. Then we have $$\left \lfloor \frac{P^2 + 2Pj + j^2}{4P} \right\rfloor - j \ge 0$$And since $j$ is an integer we can move it inside the floor $$\left\lfloor \frac{(P-j)^2}{4P} \right\rfloor \ge 0$$which is true.

Guys, I accidentally cited $v_p(n!)=\sum_{i=1}^\infty\lfloor n/p^i\rfloor$ as lagrange's theorem, will I lose a point?

We use hook length formula jk, I actually don't know the formula. Here's a fairly boring solution. The bulk of the problem is the followng inequality: Claim: For any positive integers $k,a$, we have: $$\left \lfloor \frac{k^2}{a} \right \rfloor+\sum_{j=0}^{k-1} \left \lfloor \frac{j}{a} \right \rfloor \geq \sum_{j=0}^{k-1} \left \lfloor \frac{j+k}{a} \right \rfloor.$$Proof: Observe that this inequality is equivalent to: $$\sum_{j=0}^{k-1}\left(\left\{\frac{k+j}{a}\right\}-\left\{\frac{j}{a}\right\}\right) \geq \left \{\frac{k^2}{a}\right\}.\qquad (1)$$I will first prove $(1)$ when $1 \leq k \leq a$. It is clearly true for $k=a$, since in that case the inequality becomes $a \geq a$. Further, if $2k<a$, then the LHS just becomes $k^2/a$, which is clearly at least $\{k^2/a\}$, hence the inequality holds for $2k<a$. Hence assume $2k \geq a>k$, and write $a=k+n$, where $n$ is a positive integer and $1 \leq n<k$. Then we can split the summation on the LHS as follows: $$\sum_{j=0}^{k-1}\left(\left\{\frac{k+j}{a}\right\}-\left\{\frac{j}{a}\right\}\right)=\sum_{j=0}^{n-1} \left(\left\{\frac{k+j}{a}\right\}-\left\{\frac{j}{a}\right\}\right)+\sum_{j=n}^{k-1} \left(\left\{\frac{k+j}{a}\right\}-\left\{\frac{j}{a}\right\}\right).$$One can easily find that for $0\leq j \leq n-1$, we have $$\left\{\frac{k+j}{a}\right\}-\left\{\frac{j}{a}\right\}=\frac{k}{a},$$and for $n \leq j \leq k-1$: $$\left\{\frac{k+j}{a}\right\}-\left\{\frac{j}{a}\right\}=\frac{k}{a}-1,$$hence: \begin{align*} \sum_{j=0}^{n-1} \left(\left\{\frac{k+j}{a}\right\}-\left\{\frac{j}{a}\right\}\right)+\sum_{j=n}^{k-1} \left(\left\{\frac{k+j}{a}\right\}-\left\{\frac{j}{a}\right\}\right)&=n\cdot \frac{k}{k+n}+(k-n)\cdot \left(\frac{k}{k+n}-1\right)\\ &=\frac{k^2}{k+n}-(k-n). \end{align*}Hence it suffices to show: $$\frac{k^2}{k+n}-(k-n) \geq \left\{\frac{k^2}{k+n}\right\},$$which uppon rearrangement becomes: $$\left \lfloor \frac{k^2}{k+n} \right \rfloor \geq k-n.$$Since the RHS is an integer, it suffices to prove the inequality holds without the floor on the LHS, which is clearly true upon cross-multiplication. Now I claim that if $(1)$ holds for some $k$, then it must hold for $k+a$ as well, where $a$ is fixed. Note that: \begin{align*} \sum_{j=0}^{k+a-1}\left(\left\{\frac{k+a+j}{a}\right\}-\left\{\frac{j}{a}\right\}\right)&=\sum_{j=0}^{k+a-1}\left(\left\{\frac{k+j}{a}\right\}-\left\{\frac{j}{a}\right\}\right)\\ &=\sum_{j=0}^{k-1}\left(\left\{\frac{k+j}{a}\right\}-\left\{\frac{j}{a}\right\}\right)+\sum_{j=k}^{k+a-1}\left(\left\{\frac{k+j}{a}\right\}-\left\{\frac{j}{a}\right\}\right) \end{align*}and that trivially $\{k^2/a\}=\{(k+a)^2/a\}$. Observe that the set $\{2k,2k+1,\ldots,2k+a-1\}$ forms a complete residue set $\pmod{a}$, as does the set $\{k,k+1,\ldots,k+a-1\}$, hence $$\sum_{j=k}^{k+a-1}\left\{\frac{k+j}{a}\right\}=\sum_{j=k}^{k+a-1}\left\{\frac{j}{a}\right\},$$so we have: $$\sum_{j=k}^{k+a-1}\left(\left\{\frac{k+j}{a}\right\}-\left\{\frac{j}{a}\right\}\right)=0.$$Hence it follows that we can add $$\sum_{j=k}^{k+a-1}\left(\left\{\frac{k+j}{a}\right\}-\left\{\frac{j}{a}\right\}\right)$$to the LHS of the inequality without changing whether or not it is true, which means that if $(1)$ holds for $k$ then it must hold for $k+a$ as well. Hence by induction (since $k\leq a$ has already been proven) it follows that $(1)$ is true for all positive integers, proving the claim. $\blacksquare$ Now note that the expression is an integer if its $v_p$ is nonnegative for all primes $p$. By Legendre's formula, we require: $$\sum_{i=0}^\infty \left \lfloor \frac{k^2}{p^i}\right \rfloor+\sum_{j=0}^{k-1}\sum_{i=0}^\infty \left \lfloor \frac{j}{p^i}\right \rfloor \geq \sum_{j=0}^{k-1}\sum_{i=0}^\infty \left \lfloor \frac{j+k}{p^i}\right \rfloor.$$To prove this inequality it is sufficient to consider each prime power $p^i$, after which the inequality becomes: $$\left \lfloor \frac{k^2}{p^i} \right \rfloor+\sum_{j=0}^{k-1} \left \lfloor \frac{j}{p^i} \right \rfloor \geq \sum_{j=0}^{k-1} \left \lfloor \frac{j+k}{p^i} \right \rfloor$$which is true by the claim proven earlier. Thus the $v_p$ of the expression is always nonnegative, so it is an integer as desired. $\blacksquare$

Weird but this problem feels like pure computation. I'm not really getting an "olympiad" type vibe. We begin with the following lemma: Lemma 1: For some positive integers $m, k \ge 2$, let $f(n)$ denote the remainder when $n$ is divided by $m$. Then we have that $$f(k^2) \le \sum_{j=0}^{k-1} [f(j+k) - f(j)]$$Proof. Clearly, both sides are congruent modulo $m$. Thus we just have to prove that the RHS is nonnegative. If $k \ge m$, then all the terms after the first $f(k)$ terms of the RHS cancel out. This implies that we only have to consider $k < m$. If $k \le m/2$, then all of the bracketed terms of the RHS are positive, so we are done. Else, if $k > m/2$, observe the first (m-k) bracketed terms are equal to $k$, while the last (k - (m-k)) bracketed terms are equal to $k-m$. This yields a sum of $$k^2-m(k-(m-k)) = k^2-m(2k-m) = k^2 - 2km + m^2 = (k-m)^2 \ge 0$$So the RHS is nonnegative, as desired. Now, back to the problem, it suffices to prove that for all primes $p$, $$\nu_p((k^2)!) \ge \sum_{j=0}^{k-1} [\nu_p((j+k)!) - \nu_p((j!)]$$By Legendre's formula, this is equivalent to proving that $$\sum_{i=1}^{\infty} \left\lfloor \frac{k^2}{p^i} \right\rfloor \ge \sum_{i=1}^{\infty} \sum_{j=0}^{k-1} \left\lfloor \frac{j+k}{p^i} \right\rfloor - \left\lfloor \frac{j}{p^i} \right\rfloor$$Taking the fractional parts of each side yields $$\sum_{i=1}^{\infty} \left\{ \frac{k^2}{p^i} \right\} \le \sum_{i=1}^{\infty} \sum_{j=0}^{k-1} \left\{ \frac{j+k}{p^i} \right\} - \left\{ \frac{j}{p^i} \right\}$$From Lemma 1, we have that for $m = p^i$, $$f(k^2) \le \sum_{j=0}^{k-1} [f(j+k) - f(j)]$$Dividing by $p^i$ gives $$\left\{ \frac{k^2}{p^i} \right\} \le \sum_{j=0}^{k-1} \left\{ \frac{j+k}{p^i} \right\} - \left\{ \frac{j}{p^i} \right\}$$So summing over all $p^i$ gives us the desired result. $\square$

Let $P = (k^2)!\cdot\displaystyle\prod_{j=0}^{k-1}\frac{j!}{(j+k)!}$. I will prove $v_p(P) \ge 0$ for all primes $p$, which means it must be an integer. Let $P' = \prod_{j=0}^{k-1}\frac{(j+k)!}{j!}$, so $P = \frac{(k^2)!}{P'}$. Also, let $f_p(x)$ be a function which is equal to $1$ if $p \mid x$, and $0$ otherwise. Claim: $f_p(P') \le \left\lfloor\frac{k^2}{p}\right\rfloor$. Proof: $$P' = \prod_{j=0}^{k-1}\frac{(j+k)!}{j!} = (2k-1)^1(2k-2)^2(2k-3)^3\ldots k^k(k-1)^{k-1}(k-2)^{k-2}\ldots 2^21^10^0.$$Let $c$ be the greatest integer such that $cp < k$. Now we have $2$ cases. Case 1: $2cp < 2k \le (2c+1)p$. For the numbers $q$ greater than or equal to $k$, we see their exponent in $P'$ is $(2k-q)$, while the exponents for the numbers $r$ less than $k$ are just $r$ itself. This means $$f_p(P') = [(2k-2cp)+(2k-(2c-1)p)+\ldots +(2k-(c+1)p)]+[cp+(c-1)p+\ldots +1p+0p] = c(2k-cp).$$Now let $k = mp+n$ for some nonnegative integers $m$ and $n$ with $n < p$. This means $c = m$ so we have $$c(2k-cp) = m(2(mp+n)-mp) = m^2p+2mn < \frac{m^2p^2+2mpn+n^2}{p} = \frac{(mp+n)^2}{n} = \frac{k^2}{p}.$$Because the LHS is an integer, $c(2k-cp) \le \left\lfloor\frac{k^2}{p}\right\rfloor$ as desired. Case 2: $(2c+1)p < 2k \le (2c+2)p$. This is more or less the same, so I will try not to repeat myself. We have $f_p(P') = (c+1)(2k-(c+1)p)$, and denoting $k = mp+n$ gives $c = m$, so $$(c+1)(2k-(c+1)p) = (m+1)(2(mp+n)-(m+1)p) = (m+1)((m-1)p+2n) = m^2p+2mn+1-p < \frac{(mp+n)^2}{p} = \frac{k^2}{p},$$$$\implies f_p(P') \le \left\lfloor\frac{k^2}{p}\right\rfloor$$as desired, so our claim is proven. With this claim, because we have $f_p((k^2)!) = \left\lfloor\frac{k^2}{p}\right\rfloor$, for primes $p$: $$v_p(P) = f_p(P)+f_{p^2}(P)+f_{p^3}(P)+\ldots = [f_p((k^2)!)-f_p(P')]+[f_{p^2}((k^2)!)-f_{p^2}(P')] + \ldots \ge 0$$so we are done. $\blacksquare$ Remarks: Kinda bashy, and you have to not get tricked and not use induction. I wonder if there is a nice counting argument though.

Posting for storage... We need to prove that $\nu_p((k^2)!)+\sum_{j=0}^{k-1} \nu_p(j!)\geq \sum_{j=0}^{k-1} \nu_p((j+k)!)$ or $\lfloor \frac{k^2}{m} \rfloor +\sum_{j=0}^{k-1} \lfloor \frac{j}{m} \rfloor \geq \sum_{j=0}^{k-1} \lfloor \frac{j+k}{m} \rfloor$. Since, $x>\lfloor x \rfloor$. So, $\frac{k^2}{m}> \sum_{j=0}^{k-1} \lfloor \frac{j+k}{m} \rfloor - \sum_{j=0}^{k-1} \lfloor \frac{j}{m} \rfloor$. Now, we may start inducting on $k$ by assuming the above thing is true for $k$. Therefore, it must be true for $k+1$ also. So, $\frac{(k+1)^2}{m}=\frac{k^2}{m}+\frac{2k+1}{m}\geq (\sum_{j=0}^{k-1} \lfloor \frac{j+k}{m} \rfloor - \sum_{j=0}^{k-1} \lfloor \frac{j}{m} \rfloor) +1+ \frac{2k+1}{m}$ = $(\sum_{j=0}^{k} \lfloor \frac{j+k+1}{m} \rfloor - \sum_{j=0}^{k} \lfloor \frac{j}{m} \rfloor)+ \frac{2k+1}{m} - \lfloor \frac{2k+1}{m} \rfloor + 2\lfloor \frac{k}{m}\rfloor - \lfloor \frac{2k}{m} \rfloor +1 > (\sum_{j=0}^{k} \lfloor \frac{j+k+1}{m} \rfloor - \sum_{j=0}^{k} \lfloor \frac{j}{m} \rfloor)$ which we wanted. $\blacksquare$

It suffices to show that for all prime powers $p$, we have $$\left\lfloor \frac{k^2}{p}\right\rfloor \geq \sum_{j=0}^{k-1}\left(\left\lfloor \frac{j+k}{p}\right\rfloor - \left\lfloor \frac{j}{p}\right\rfloor\right).$$Note that the RHS is equal to the number of multiples of $p$ in the matrix below (for visualization purposes) $$\begin{bmatrix} 1 & 2 & 3 & \cdots & k \\ 2 & 3 & & & k+1 \\ 3 & & \ddots & & \vdots \\ \vdots & & & & 2k-2 \\ k & k+1 & \cdots & 2k-2 & 2k-1 \\ \end{bmatrix}$$Now set $k=np+r$ where $0\leq r<p$. The LHS then becomes $$n^2p+2nr+\left\lfloor \frac{r^2}{p}\right\rfloor$$and the RHS becomes $$(p+2p+3p+\dots+np)+((np-p+2r)+(np-2p+2r)+\dots+2r)+\text{max}(2r-p,0).$$Then the RHS is equal to $$n(np+2r)+\text{max}(2r-p,0)$$so it suffices to show that for all $0\leq r<p$, we have $$\left\lfloor \frac{r^2}{p}\right\rfloor\geq \text{max}(2r-p,0).$$Then for $r<\frac{p}{2}$ we are done so assume that $\frac{p}{2}\leq r<p$. Then we can substitute $r=p-k$ to obtain $$\left\lfloor \frac{p^2-2pk+k^2}{p}\right\rfloor\geq p-2k$$which is true. $\blacksquare$

aaa this took me 2 hours to do without hook length also only 15 MOHS? it felt more like 20-25, but probably hook length brought it down a lot Define $f_m(k)$ to be the remainder when $k$ is divided by $m$. Main Claim 1: For all $m,k$, we have $$f_m(k)+f_m(k+1)+f_m(k+2)\cdots +f_m(2k-1)\geq f_m(0)+f_m(1)+f_m(2)\cdots +f_m(k-1)+(f_m(k^2)).$$(I put parenthesis around the last term to emphasize that it's irregular). We can interpret that inequalty as follows: start with the first $k$ nonnegative integers modulo $m$. Shift all of them up by $k$. Then the resulting increase is at least the remainder when $k^2$ is divided by $m$. We will then show this. Obviously, the new sum of mods after shifting up by $k$ is greater than or equal to the original sum of mods (since originally we started at 0, now we start at $f_m(k)$). Also, note that each term either increased by $k\pmod m$, or "increased" by $(k\pmod m)-m.$ Therefore, the total increase is $k^2-sm$ for some nonnegative integer $s$. The smallest possible nonnegative value of this expression is the same as the remainder when $k^2$ is divided by $m$, which is $f_m(k^2)$, which shows the claim. Main Claim 2: For all positive integers $k$ and $m$, we have $$(\lfloor \frac{k^2}{m}\rfloor)+\lfloor \frac{0}{m}\rfloor+\lfloor \frac{1}{m}\rfloor\cdots +\lfloor \frac{k-1}{m}\rfloor\geq \lfloor \frac{k}{m}\rfloor+\lfloor \frac{k+1}{m}\rfloor\cdots \lfloor \frac{2k-1}{m}\rfloor.$$Using fractional parts, this is also $$\frac{(3k^2-k)/2}{m}-((\{k^2/m\})+\{0/m\}+\{1/m\}+\{2/m\}\cdots +\{(k-1)/m\})$$$$\geq \frac{(3k^2-k)/2}{m}-(\{k/m\}+\{(k+1)/m\}+\{(k+2)/m\}\cdots +\{(2k-1)/m\})$$which rearranges to $$\{k/m\}+\{(k+1)/m\}+\{(k+2)/m\}\cdots +\{(2k-1)/m\}\geq (\{k^2/m\})+\{0/m\}+\{1/m\}+\{2/m\}\cdots +\{(k-1)/m\},$$which is just Main Claim 1 after multiplying by $m$. We are now ready to tackle the problem. Consider an arbitrary prime $p$. We wish to show that $$v_p((k^2)!)+\sum_{i=0}^{k-1} v_p(i!)\geq \sum_{i=0}^{k-1}v_p((k+i)!).$$Using Legendre's, we can write this as $$\sum_{s=1}^\infty \lfloor \frac{k^2}{p^s}\rfloor+\sum_{i=0}^{k-1} \sum_{s=1}^\infty \lfloor \frac{i}{p^s}\rfloor\geq \sum_{i=0}^{k-1}\sum_{s=1}^\infty \lfloor \frac{k+i}{p^s}\rfloor.$$Of course, we can also swap the order of summation: $$\sum_{s=1}^\infty \lfloor \frac{k^2}{p^s}\rfloor+\sum_{s=1}^{\infty} \sum_{i=0}^{k-1} \lfloor \frac{i}{p^s}\rfloor\geq \sum_{s=1}^{\infty} \sum_{i=0}^{k-1} \lfloor \frac{k+i}{p^s}\rfloor,$$which can be rewritten as $$\sum_{s=1}^\infty(\lfloor \frac{k^2}{p^s}\rfloor +\sum_{i=0}^{k-1} \lfloor \frac{i}{p^s}\rfloor)\geq \sum_{s=1}^{\infty} \sum_{i=0}^{k-1} \lfloor \frac{k+i}{p^s}\rfloor.$$However, by Main Claim 2, we have $$\lfloor \frac{k^2}{p^s}\rfloor +\sum_{i=0}^{k-1} \lfloor \frac{i}{p^s}\rfloor\geq \sum_{i=0}^{k-1} \lfloor \frac{k+i}{p^s}\rfloor,$$so we are finally done.

By Legendre's, it suffices to show that \[ \lfloor \frac{k^2}{p^s}\rfloor +\sum_{i=0}^{k-1} \lfloor \frac{i}{p^s}\rfloor\geq \sum_{i=0}^{k-1} \lfloor \frac{k+i}{p^s}\rfloor \]for all $p,s$ where $p$ is prime. First, note that the sum of the numerators on both sides are equal, so it suffices to look at the fractional components to find: \[ \sum_{i=k}^{2k-1} (i \pmod{p^s}) \geq (k^2 \pmod{p^s}) + \sum_{i=0}^{k-1} (i \pmod{p^s})\]We focus on showing that \[ \sum_{i=k}^{2k-1} (i \pmod{p^s}) - \sum_{i=0}^{k-1} (i \pmod{p^s}) \geq (k^2 \pmod{p^s}) \] Imagine writing out two rows of numbers, the first $0$ to $k-1$ modulo $p^s$ and the second $k$ to $2k-1$ modulo $p^s$. Then, the LHS above is the sum of the numbers in the bottom row minus the sum of the numbers in the top row. Now, note that sum prefix of the first row equals some suffix of the second row. So we can ignore those numbers and look at the others that aren't the same. Let $k=ap^s+b$ with $0 \leq b < p^s$. If $b=0$, then both rows are the same and $k^2 \equiv 0 \pmod{p^s}$ so we assume otherwise. If $2k-1<p$, then the result is also obvious, so we also assume otherwise (so some prefix and suffix overlap). Then, the number of numbers that are different is $(p^s-b)$ as we need to hit $0$ in the bottom row. The difference between corresponding terms is a constant $p^s-1-(b-1)$ as the final term in the second sequence is $p^s-1$ whereas in the first it is $b-1$. Thus, we have that the difference is $(p^s-b)^2$. We need to show \[(p^s-b)^2 \geq (b^2 \pmod{p^s}) = ((p^s-b)^2 \pmod{p^s})\]which is obvious so we are done.

We only need to prove that for any prime number ${p}$, $$v_p\left((k^2)!\prod\limits_{j=0}^{k-1}j!\right)\geqslant v_p\left(\prod\limits_{j=0}^{k-1}(j+k)!\right)$$We have $$v_p\left((k^2)!\prod\limits_{j=0}^{k-1}j!\right)=\sum\limits_{i=1}^{+\infty}\left(\left\lfloor\frac{k^2}{p^i}\right\rfloor +\sum\limits_{j=0}^{k-1}\left\lfloor\frac{j}{p^i}\right\rfloor\right)$$$$v_p\left(\prod\limits_{j=0}^{k-1}(j+k)!\right) =\sum\limits_{i=1}^{+\infty}\sum\limits_{j=0}^{k-1}\left\lfloor\frac{j+k}{p^i}\right\rfloor$$So we only need to prove that for any prime number ${p}$ and positive integer ${i}$, let $\mathcal{P}=p^i$, then $$\left\lfloor\frac{k^2}{\mathcal{P}}\right\rfloor\geqslant\sum\limits_{j=0}^{k-1}\left(\left\lfloor\frac{j+k}{\mathcal{P}}\right\rfloor -\left\lfloor\frac{k}{\mathcal{P}}\right\rfloor\right)$$$$\Leftrightarrow\left\lfloor\frac{k^2}{\mathcal{P}}\right\rfloor >-1+\sum\limits_{j=0}^{k-1}\left(\left\lfloor\frac{j+k}{\mathcal{P}}\right\rfloor -\left\lfloor\frac{k}{\mathcal{P}}\right\rfloor\right)$$$$\Leftrightarrow\frac{k^2}{\mathcal{P}}-\left\{\frac{k^2}{\mathcal{P}}\right\}>-1+\sum\limits_{j=0}^{k-1}\left(\frac{j+k}{\mathcal{P}}-\left\{\frac{j+k}{\mathcal{P}}\right\}-\frac{j}{\mathcal{P}}+\left\{\frac{j}{\mathcal{P}}\right\}\right)$$$$\Leftrightarrow -\left\{\frac{k^2}{\mathcal{P}}\right\}>-1-\sum\limits_{j=0}^{k-1}\left\{\frac{j+k}{\mathcal{P}}\right\}+\sum\limits_{j=0}^{k-1}\left\{\frac{j}{\mathcal{P}}\right\}$$$$\Leftrightarrow 1+\sum\limits_{j=0}^{k-1}\left\{\frac{j+k}{\mathcal{P}}\right\}>\left\{\frac{k^2}{\mathcal{P}}\right\}+\sum\limits_{j=0}^{k-1}\left\{\frac{j}{\mathcal{P}}\right\}$$which is true bercause $$1>\left\{\frac{k^2}{\mathcal{P}}\right\}$$$$\sum\limits_{j=0}^{k-1}\left\{\frac{j+k}{\mathcal{P}}\right\}\geqslant\sum\limits_{j=0}^{k-1}\left\{\frac{j}{\mathcal{P}}\right\} .\blacksquare$$

Consider any prime $p$. Then take $\nu_p$ of the whole expression. By Legendre's, \[\nu_p\left((k^2)!\cdot\displaystyle\prod_{j=0}^{k-1}\frac{j!}{(j+k)!}\right)= \sum_{m=1}^{\infty}\left[ \left\lfloor\frac{k^2}{p^m}\right\rfloor +\sum_{j=0}^{k-1}\left\lfloor\frac{j}{p^m}\right\rfloor -\sum_{j=k}^{2k-1}\left\lfloor\frac{j}{p^m}\right\rfloor \right].\] Let $k-1=ap^m+b$ where $a,b$ are nonnegative integers and $b<p^m$. Then \begin{align*} &\sum_{j=k}^{2k-1}\left\lfloor\frac{j}{p^m}\right\rfloor -\sum_{j=0}^{k-1}\left\lfloor\frac{j}{p^m}\right\rfloor \\ =&k\cdot\left(\left\lfloor\frac{k-1}{p^m}\right\rfloor+1\right) +(p^m-1-((k-1)\%p^m))\left\lfloor\frac{k-1}{p^m}\right\rfloor -\sum_{j=2k}^{2k+(p^m-1-((k-1)\%p^m))-1}\left\lfloor\frac{j}{p^m}\right\rfloor \\ =& (ap^m+b+1)(a+1) +a(p^m-1-b) -\sum_{j=2ap^m+2b+2}^{(2a+1)p^m+b}\left\lfloor\frac{j}{p^m}\right\rfloor \\ =& (ap^m+b+1)(a+1) +a(p^m-1-b) -\left( \sum_{j=2ap^m+2b+2}^{(2a+1)p^m-1}\left\lfloor\frac{j}{p^m}\right\rfloor +\sum_{j=(2a+1)p^m}^{(2a+1)p^m+b}\left\lfloor\frac{j}{p^m}\right\rfloor \right) \\ =& (ap^m+b+1)(a+1)+a(p^m-1-b)-\left(\text{max}(p^m-1-2b-2+1,0)(2a)+(b+1)(2a+1)\right) \\ =& a^2p^m+ab+a+ap^m+b+1+ap^m-a-ab-2ab-2a-b-1-\text{max}(p^m-1-2b-2+1,0)(2a) \\ =& a^2p^m+2ab+2a(p^m-2b-1)-\text{max}(p^m-2b-2,0)(2a) \\ \le & a^2p^m+2ab+2a. \end{align*} Since \[\left\lfloor\frac{k^2}{p^m}\right\rfloor\ge a^2p^m+2ab+2a,\]we are done.

oops solved with hint to compare respective things in legendres cuz i never thought of respective things lol also typing floor takes SUCH A LONG TIME so i refuse to latex properly and will denote [] as floor, \{\} as fractional Rephrased, for any prime power q^r=s we'll show that $$[\tfrac{k^2}s]+\sum_{i=0}^{k-1}[\tfrac is]>\sum_{i=0}^{k-1}[\tfrac{i+k}s]-1\iff\{\tfrac{k^2}q\}<1+\sum_{i=0}^{k-1}\{\tfrac is\}.$$Indeed, we prove that the sum in LHS$\le$sum in RHS by looking at the remainders of 0,1,...,k-1 vs. k,k+1,...,2k-1 mod s: If s<k, the claim is evident since the LHS covers all smallest remainders up to k-1, while RHS is also a consecutive block of k length, which at least covers 0->k-1; if k-1<s<2k-1, the problem is still evident by same reasoning; if s>2k-1, no reductions are done and the claim is evident. To finish, $\{\frac{k^2}q\}<1$, as desired. $\blacksquare$

i have just crafted the stupidest thing of all time How may we solve this problem? Of course, we use $\nu_p$. Obviously, our equality evaluates to \[ \sum_{i=1} \left\lfloor \frac{k^2}{p^i} \right\rfloor \ge \sum_{i=1} \sum_{j = 0}^{k-1} \left( \left\lfloor \frac{j+k}{p^i} \right\rfloor - \left\lfloor \frac{j}{p^i} \right\rfloor \right). \]Known it is that if we check this inequality for each prime power, we will be done. Let us fix a prime $p$ and power $a$. Each of these powers of primes will satisfy our property if we have \[ \left\{ \frac{k^2}{p^a} \right\} \le \sum_{j=0}^{k-1} \left( \left\{\frac{j+k}{p^a} \right\} - \left\{ \frac{j}{p^a} \right\} \right).\]Now we may consider $r \equiv k \pmod{p^a}$ - the inequality holds for $r$ iff it holds for $k$, which can be easily checked. Great - if $r < \frac{p^a}{2}$ we are done, since both sides are equal. Therefore, we have to prove the result for $\frac{p^a}{2} \le r < p^a$ - but we have \begin{align*} \sum_{j=0}^{r-1} \left( \left\{\frac{j+r}{p^a} \right\} - \left\{ \frac{j}{p^a} \right\} \right) &= (p^a-r) \cdot \frac{r}{p^a} + (r - (p^a - r)) \cdot \left( \frac{r}{p^a} - 1 \right) \\ &= \frac{r^2}{p^a} - (2r - p^a) \\ &= \frac{(p^a - r)^2}{p^a} \\ &\le \frac{r^2}{p^a} \\ &\implies \sum_{j=0}^{r-1} \left( \left\{\frac{j+r}{p^a} \right\} - \left\{ \frac{j}{p^a} \right\} \right) \ge \left\{ \frac{r^2}{p^a} \right\} \end{align*}as desired. However, if one wants an alternative solution, read the first letters of each sentence.

pikapika007 wrote: i have just crafted the stupidest thing of all time How may we solve this problem? Of course, we use $\nu_p$. Obviously, our equality evaluates to \[ \sum_{i=1} \left\lfloor \frac{k^2}{p^i} \right\rfloor \ge \sum_{i=1} \sum_{j = 0}^{k-1} \left( \left\lfloor \frac{j+k}{p^i} \right\rfloor - \left\lfloor \frac{j}{p^i} \right\rfloor \right). \]Kindly, if we check this inequality for each prime power, we will be done. Let us fix a prime $p$ and power $a$. Each of these powers of primes will satisfy our property if we have \[ \left\{ \frac{k^2}{p^a} \right\} \le \sum_{j=0}^{k-1} \left( \left\{\frac{j+k}{p^a} \right\} - \left\{ \frac{j}{p^a} \right\} \right).\]Now we may consider $r \equiv k \pmod{p^a}$ - the inequality holds for $r$ iff it holds for $k$, which can be easily checked. Great - if $r < \frac{p^a}{2}$ we are done, since both sides are equal. Therefore, we have to prove the result for $\frac{p^a}{2} \le r < p^a$ - but we have \begin{align*} \sum_{j=0}^{r-1} \left( \left\{\frac{j+r}{p^a} \right\} - \left\{ \frac{j}{p^a} \right\} \right) &= (p^a-r) \cdot \frac{r}{p^a} + (r - (p^a - r)) \cdot \left( \frac{r}{p^a} - 1 \right) \\ &= \frac{r^2}{p^a} - (2r - p^a) \\ &= \frac{(r - p^a)^2}{p^a} \\ &\ge \frac{r^2}{p^a} \\ &\implies \sum_{j=0}^{r-1} \left( \left\{\frac{j+r}{p^a} \right\} - \left\{ \frac{j}{p^a} \right\} \right) \ge \left\{ \frac{r^2}{p^a} \right\} \end{align*}as desired. However, if one wants an alternative solution, read the first letters of each sentence.

Choosing an arbitrary prime $p$, it suffices to show \[\sum_{i=0}^{\infty} \left(\left\lfloor \frac{k^2}{p^i} \right\rfloor - \sum_{j=0}^{k-1} \left(\left\lfloor \frac{j+k}{p^i} \right\rfloor - \left\lfloor \frac{j}{p^i} \right\rfloor\right)\right)\] is nonnegative, or each individual summand is nonnegative. It also suffices to prove the result for all positive integers $a$ (in place of $p^i$). It's not hard to prove that the value of the desired expression is equal for each residue $k \pmod a$, so we can assume $0 \leq k \leq a-1$. Then we require \[\left\lfloor \frac{k^2}{a} \right\rfloor \ge \sum_{j=0}^{k-1} \left\lfloor \frac{j+k}{a} \right\rfloor - \sum_{j=0}^{k-1} \left\lfloor \frac{j}{a}\right\rfloor = \sum_{j=0}^{k-1} \left\lfloor \frac{j+k}{a} \right\rfloor = \max(0, 2k-a).\] If $2k \leq a$, we're done. Otherwise, suppose $a = k+m$. The desired is equivalent to \[\left\lfloor \frac{k^2}{k+m} \right\rfloor \ge 2k-(k+m) \iff (k-m) + \left\lfloor \frac{m^2}{a} \right\rfloor \ge (k-m),\] which is true. $\blacksquare$

I dont really feel like deciphering my work from 3 weeks ago and writing this up. But the backstory is, I was in a boring meeting at church, so then i pulled up otis and did this problem on a tiny piece of paper. Here is a photo