Ratio of Factorials

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2376 posts

#1 h Apr 19, 2016, 9:33 PM • 13 Y

Y by Yousef_al-Khwarizmi, math73, Tawan, Davi-8191, Tuhin_wemath3, OlympusHero, a.shyam.25, megarnie, HWenslawski, Adventure10, Mango247, NicoN9, Jack_w

Prove that for any positive integer $k$ , $(k^2)!\cdot\displaystyle\prod_{j=0}^{k-1}\frac{j!}{(j+k)!}$ is an integer.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

tenniskidperson3

2376 posts

tenniskidperson3

#2 h Apr 19, 2016, 9:33 PM • 10 Y

Y by Yousef_al-Khwarizmi, math73, Tawan, M.Unubold, Ultroid999OCPN, OlympusHero, a.shyam.25, HWenslawski, Adventure10, Mango247

My solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

aZpElr68Cb51U51qy9OM

1600 posts

aZpElr68Cb51U51qy9OM

#3 h Apr 19, 2016, 9:34 PM • 11 Y

Y by Yousef_al-Khwarizmi, math73, Tawan, Ultroid999OCPN, OlympusHero, Pluto1708, a.shyam.25, centslordm, HWenslawski, aidan0626, Adventure10

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

This post has been edited 1 time. Last edited by aZpElr68Cb51U51qy9OM, Apr 19, 2016, 9:34 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Shaddoll

688 posts

Shaddoll

#4 h Apr 19, 2016, 9:34 PM • 4 Y

Y by Yousef_al-Khwarizmi, math73, a.shyam.25, Adventure10

tenniskidperson3 wrote:

My solution

I also used the hook length formula!

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

v_Enhance

6876 posts

v_Enhance

#5 h Apr 19, 2016, 9:34 PM • 29 Y

Y by Stens, biomathematics, langkhach11112, Yousef_al-Khwarizmi, mathwhiz16, math73, Tawan, champion999, claserken, neep, Ultroid999OCPN, CALCMAN, Lcz, OlympusHero, Pluto1708, HamstPan38825, a.shyam.25, tigerzhang, khina, centslordm, kante314, skyguy88, Lamboreghini, rayfish, Adventure10, sabkx, NicoN9, Sedro, MathRook7817

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).

This post has been edited 2 times. Last edited by v_Enhance, Oct 30, 2016, 5:42 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

mssmath

977 posts

mssmath

#7 h Apr 19, 2016, 9:52 PM • 4 Y

Y by Yousef_al-Khwarizmi, a.shyam.25, Adventure10, Mango247

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

tenniskidperson3

2376 posts

tenniskidperson3

#8 h Apr 19, 2016, 9:54 PM • 10 Y

Y by Yousef_al-Khwarizmi, v_Enhance, katzrockso, OlympusHero, a.shyam.25, pith0n, jhu08, Adventure10, Mango247, Sedro

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Dukejukem

695 posts

Dukejukem

#9 h Apr 19, 2016, 9:56 PM • 6 Y

Y by v_Enhance, burunduchok, AlastorMoody, a.shyam.25, Adventure10, Mango247

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

Preliminary Lemma

Computation of p-adic valuations

This post has been edited 2 times. Last edited by Dukejukem, May 2, 2016, 2:13 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

shinichiman

3212 posts

shinichiman

#10 h Apr 19, 2016, 9:59 PM • 6 Y

Y by cpma213, langkhach11112, AlastorMoody, a.shyam.25, Adventure10, Mango247

Solution

This post has been edited 3 times. Last edited by shinichiman, Apr 20, 2016, 8:25 AM
Reason: fixed error

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ABCDE

1963 posts

ABCDE

#11 h Apr 19, 2016, 10:02 PM • 3 Y

Y by chenmeister22, a.shyam.25, Adventure10

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

v_Enhance

6876 posts

v_Enhance

#12 h Apr 19, 2016, 10:06 PM • 5 Y

Y by 62861, HamstPan38825, a.shyam.25, Adventure10, Mango247

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

infiniteturtle

1131 posts

infiniteturtle

#13 h Apr 19, 2016, 10:06 PM • 3 Y

Y by a.shyam.25, Adventure10, Mango247

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

DrMath

2130 posts

DrMath

#14 h Apr 19, 2016, 10:06 PM • 4 Y

Y by a.shyam.25, Adventure10, Mango247, Jack_w

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?

This post has been edited 1 time. Last edited by DrMath, Apr 19, 2016, 10:06 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

stephcurry

2095 posts

stephcurry

#15 h Apr 19, 2016, 10:13 PM • 4 Y

Y by rafayaashary1, a.shyam.25, Adventure10, Mango247

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

mssmath

977 posts

mssmath

#16 h Apr 19, 2016, 10:14 PM • 3 Y

Y by a.shyam.25, Adventure10, Mango247

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

jeteagle

480 posts

jeteagle

#113 h Jul 7, 2021, 9:26 PM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ALM_04

85 posts

ALM_04

#114 h Feb 1, 2022, 2:01 PM

Y by

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

asdf334

7585 posts

asdf334

#115 h Apr 23, 2022, 12:42 PM • 1 Y

Y by math31415926535

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$

This post has been edited 1 time. Last edited by asdf334, Apr 23, 2022, 1:35 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

john0512

4184 posts

john0512

#117 h Mar 5, 2023, 2:13 AM • 1 Y

Y by OronSH

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.

This post has been edited 1 time. Last edited by john0512, Mar 5, 2023, 2:15 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

bever209

1522 posts

bever209

#118 h Mar 12, 2023, 7:11 PM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

EthanWYX2009

855 posts

EthanWYX2009

#119 h Apr 1, 2023, 12:14 AM • 1 Y

Y by Geometry285

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

YaoAOPS

1530 posts

YaoAOPS

#120 h Apr 13, 2023, 5:00 PM

Y by

storage

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

cj13609517288

1893 posts

cj13609517288

#121 h May 1, 2023, 3:10 PM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

huashiliao2020

1292 posts

huashiliao2020

#122 h Aug 23, 2023, 12:16 AM

Y by

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$

This post has been edited 1 time. Last edited by huashiliao2020, Aug 23, 2023, 12:16 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

pikapika007

297 posts

pikapika007

#123 h Aug 25, 2023, 10:53 PM • 7 Y

Y by EpicBird08, GrantStar, mathboy100, YaoAOPS, kn07, RedFireTruck, mathmax12

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.

This post has been edited 3 times. Last edited by pikapika007, Aug 26, 2023, 12:03 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

club52

724 posts

club52

#124 h Aug 25, 2023, 10:59 PM

Y by

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.

spoiler to the solution of the first letter of each sentence

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

shendrew7

794 posts

shendrew7

#125 h Sep 1, 2024, 3:48 AM

Y by

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

bjump

1002 posts

bjump

#126 h Dec 24, 2024, 1:32 AM • 2 Y

Y by Leo.Euler, Mathandski

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

Attachments:

This post has been edited 1 time. Last edited by bjump, Dec 24, 2024, 1:33 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Mathandski

748 posts

Mathandski

#127 h Mar 6, 2025, 3:22 AM • 1 Y

Y by bjump

@above omg I remember seeing your post about this

Subjective Rating (MOHs)
Please contact westskigamer@gmail.com if there is an error with my solution for cash bounties by 3/18/2025.

Warning: Solution was transcribed by ChatGPT so there may be typoes.
Solution

This post has been edited 2 times. Last edited by Mathandski, Mar 11, 2025, 10:11 PM
Reason: fix j+1 typo

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

cursed_tangent1434

602 posts

cursed_tangent1434

#128 h Apr 16, 2025, 1:00 AM

Y by

Consider a prime $p \mid \prod_{i=k}^{2k-1}i!$ . We show that $\nu_p\left(\prod_{i=k}^{2k-1}i!\right) \ge \nu_p\left((k^2)!\cdot \prod_{i=0}^{k-1}i!\right)$ , which will imply the result. Note that by Legendre's Formula,
$\nu_p\left(\prod_{i=k}^{2k-1}i!\right) = \left(\lfloor \frac{k}{p}\rfloor + \lfloor \frac{k}{p^2}\rfloor+\dots \right) + \dots + \left(\lfloor \frac{2k-1}{p}\rfloor + \lfloor \frac{2k-1}{p^2}\rfloor + \dots \right)$ Further,
$\nu_p\left((k^2)!\cdot \prod_{i=0}^{k-1}i!\right) = \left(\lfloor \frac{k^2}{p} \rfloor + \lfloor \frac{k^2}{p^2}\rfloor + \dots \right) + \left(\lfloor \frac{k^2}{p}\rfloor + \lfloor \frac{k}{p}\rfloor\right)$ The following key claim is sufficient.

Claim: For any positive integers $k$ and $n$ ,
$\lfloor \frac{k^2}{n}\rfloor + \lfloor \frac{0}{n}\rfloor + \lfloor \frac{1}{n}\rfloor + \dots + \lfloor \frac{k-1}{n}\rfloor \ge \lfloor \frac{k}{n}\rfloor + \lfloor \frac{k+1}{n}\rfloor + \dots + \lfloor \frac{2k-1}{n}\rfloor$
Proof : Let $k=ln+m$ for some non-negative integers $l$ and $0 \le m < n$ . Note,
$\lfloor \frac{0}{n}\rfloor + \lfloor \frac{1}{n}\rfloor + \dots + \lfloor \frac{k-1}{n}\rfloor = 0 + p + \dots + (l-1)p + lm = \frac{l(l-1)n}{2}+lm$ and
$\lfloor \frac{k^2}{n}\rfloor = \lfloor \frac{l^2n^2 + 2lnm+m^2}{n}\rfloor = l^2n + 2lm + \lfloor \frac{m^2}{n}\rfloor$ Now we have two possibilities. If $2m \le n$ ,
$\lfloor \frac{k}{n}\rfloor + \lfloor \frac{k+1}{n}\rfloor + \dots + \lfloor \frac{2k-1}{n}\rfloor = l(n-m) + (l+1)n + \dots + 2lm = \frac{3l(l-1)n}{2}+ln+lm$ So,
$\begin{align*} \lfloor \frac{k^2}{n}\rfloor + \lfloor \frac{0}{n}\rfloor + \lfloor \frac{1}{n}\rfloor + \dots + \lfloor \frac{k-1}{n}\rfloor &\ge \frac{l(l-1)n}{2}+lm + l^2n + 2lm \\ &= \frac{(3l^2-l)n}{2}+3lm \\ &= \frac{3l(l-1)n}{2}+3lm+ln \\ &\ge \frac{3l(l-1)n}{2}+ln+lm \\ &= \lfloor \frac{k}{n}\rfloor + \lfloor \frac{k+1}{n}\rfloor + \dots + \lfloor \frac{2k-1}{n}\rfloor \end{align*}$ If $2m > n$ ,
$\lfloor \frac{k}{n}\rfloor + \dots + \lfloor \frac{2k-1}{n}\rfloor = l(n-m) + (l+1)n + \dots + 2ln + (2l+1)(2m-n) = \frac{l(3l-1)n}{2}+3lm+2m-n$ Also note that,
$\begin{align*} (m-n)^2 & \ge 0 \\ m^2 - 2mn + n^2 &\ge 0 \\ m^2 & \ge n(2m-n) \end{align*}$ So,
$\begin{align*} \lfloor \frac{k^2}{n}\rfloor + \lfloor \frac{0}{n}\rfloor + \lfloor \frac{1}{n}\rfloor + \dots + \lfloor \frac{k-1}{n}\rfloor & = l^2n + 2lm + \lfloor \frac{m^2}{n}\rfloor + \frac{l(l-1)n}{2}+lm \\ & \ge l^2n+2lm + 2m-n + \frac{l(l-1)n}{2}+lm\\ & = \frac{l(3l^2-1)n}{2}+ 3lm + 2m-n \\ & = \lfloor \frac{k}{n}\rfloor + \dots + \lfloor \frac{2k-1}{n}\rfloor \end{align*}$ which proves the claim.

Summing the claim across all $p^i$ for $i \ge 1$ we have that
$\sum_{i=1}^\infty \left \lfloor \frac{k^2}{p^i}\rfloor + \lfloor \frac{0}{p^i}\rfloor + \lfloor \frac{1}{p^i}\rfloor + \dots + \lfloor \frac{k-1}{p^i}\rfloor \right) \ge \sum_{i=1}^\infty \left(\lfloor \frac{k}{p^i}\rfloor + \lfloor \frac{k+1}{p^i}\rfloor + \dots + \lfloor \frac{2k-1}{p^i}\rfloor \right)$ which finishes the proof.

Z K Y