(a) Prove that \[ [5x]+[5y] \ge [3x+y] + [3y+x],\] where $ x,y \ge 0$ and $ [u]$ denotes the greatest integer $ \le u$ (e.g., $ [\sqrt{2}]=1$). (b) Using (a) or otherwise, prove that \[ \frac{(5m)!(5n)!}{m!n!(3m+n)!(3n+m)!}\] is integral for all positive integral $ m$ and $ n$.
Problem
Source: 1975 USAMO Problem 1
Tags: floor function, inequalities, modular arithmetic, number theory
12.06.2010 14:39
No solution for this very beautiful question??? I think the question must be moved to Number Theory because it is very difficult for pre-olympiad level.
30.06.2010 06:21
we only need consider in case that $x,y\ge 0$ we consider $0 \le x <1/5 $ ... $4/5\le x <5/5$ and $ x=1$ in the case that $0 \le x <1/5 $ we consider $0\le y <1/5$ ... $0\le y <5/5$ $y=5$ All a result of them are correct. eg: $0 \le x <1/5 $ ; $0\le y <1/5$ we have $0 = [5x]+[5y] \ge 0= [3/5+1/5]+[3/5+1/5] >[3x+y]+[3y+x]$
30.06.2010 09:55
b. Let $p$ be prime. Power of $p$ for $(5m)!(5n)!$ $\left\lfloor \frac{5m}{p} \right\rfloor + \left\lfloor \frac{5n}{p} \right\rfloor$. Power of $p$ for $m!n!(3m+n)!(3n+m)!$ $\left\lfloor \frac{m}{p} \right\rfloor + \left\lfloor \frac{n}{p} \right\rfloor + \left\lfloor \frac{3m+n}{p} \right\rfloor + \left\lfloor \frac{3n+m}{p} \right\rfloor$ $\frac{m}{p}=x , \frac{n}{p}=y$. It suffices to prove that $\lfloor 5x \rfloor + \lfloor 5y \rfloor \ge \lfloor x \rfloor + \lfloor y \rfloor + \lfloor 3x+y \rfloor + \lfloor 3y+x \rfloor$ $\{x\}=a , \{y\}=b$. $\lfloor 5a \rfloor + \lfloor 5b \rfloor \ge \lfloor 3a+b \rfloor + \lfloor 3b+a \rfloor$ and minhphuc.v proved it(a. case).
30.06.2010 12:15
A detailed proof for part $a)$: If $(x,y)$ satisfies this inequality, then it is easy to see that $(x+1,y)$ and $(x,y+1)$ also satisfy. So we can assume that $x,y \in [0,1)$ $\frac{k-1}{5} \leq x < \frac{k}{5} \: , \: \frac{l-1}{5} \leq y < \frac{l}{5}$ where $k,l \in \{1,2,3,4,5\}$ $3k+l \equiv u \pmod{5} \: , \: k+3l \equiv v \pmod{5} \: , \: u,v \in \{1,2,3,4,5\}$ $\Longrightarrow \; \lfloor 5x \rfloor = k-1 \; , \; \lfloor 5y \rfloor = l-1$ and $ \lfloor 3x+y \rfloor = \frac{3k+l-u}{5} \; , \; \lfloor x+3y \rfloor = \frac{k+3l-v}{5}$ The inequality is equivalent to $k+l+u+v \geq 10$ $3k+l \equiv u \pmod{5} \: , \: k+3l \equiv v \pmod{5} \; \Longrightarrow$ $k+l+u+v \equiv 0 \pmod{5} \; , \; k+l+u+v>0$ $k+l+u+v=5 \; \Longrightarrow \; (k,l,u,v)$ is some permutation of $(1,1,1,2)$ $k=l=1 \; \Longrightarrow \; u \equiv 4 \pmod{5}$ $k=1\; , \; l=2 \; \Longrightarrow \; u \equiv 0 \pmod{5}$ $k=2 \; , \; l=1 \; \Longrightarrow \; v \equiv 0 \pmod{5}$ $\Longrightarrow \; k+l+u+v \neq 5$ and solution is done.
10.06.2017 04:11
Anyone got a solution for b?
10.06.2017 06:55
Delray wrote: Anyone got a solution for b? http://artofproblemsolving.com/wiki/index.php?title=1975_USAMO_Problems/Problem_1
13.04.2023 20:35
gold46 wrote: b. Let $p$ be prime. Power of $p$ for $(5m)!(5n)!$ $\left\lfloor \frac{5m}{p} \right\rfloor + \left\lfloor \frac{5n}{p} \right\rfloor$. Power of $p$ for $m!n!(3m+n)!(3n+m)!$ $\left\lfloor \frac{m}{p} \right\rfloor + \left\lfloor \frac{n}{p} \right\rfloor + \left\lfloor \frac{3m+n}{p} \right\rfloor + \left\lfloor \frac{3n+m}{p} \right\rfloor$ $\frac{m}{p}=x , \frac{n}{p}=y$. It suffices to prove that $\lfloor 5x \rfloor + \lfloor 5y \rfloor \ge \lfloor x \rfloor + \lfloor y \rfloor + \lfloor 3x+y \rfloor + \lfloor 3y+x \rfloor$ $\{x\}=a , \{y\}=b$. $\lfloor 5a \rfloor + \lfloor 5b \rfloor \ge \lfloor 3a+b \rfloor + \lfloor 3b+a \rfloor$ and minhphuc.v proved it(a. case). Umm, power of p in (5m)! is not floor 5m/p, because a number in the factorial could have p^2, which then you need Legendre’s formula. Can someone give a different solution?
20.05.2023 08:27
huashiliao2020 wrote: Umm, power of p in (5m)! is not floor 5m/p, because a number in the factorial could have p^2, which then you need Legendre’s formula. Can someone give a different solution? All cases of $p^i$ are symmetric; hence simply show $$(\left\lfloor \frac{5m}{p^i} \right\rfloor + \left\lfloor \frac{5n}{p^i} \right\rfloor) - (\left\lfloor \frac{m}{p^i} \right\rfloor + \left\lfloor \frac{n}{p^i} \right\rfloor + \left\lfloor \frac{3m+n}{p^i} \right\rfloor + \left\lfloor \frac{3n+m}{p^i} \right\rfloor)$$is positive for all integer values of $i \ge 1$. Here we set $x = \frac{m}{p^i}$ and $y = \frac{n}{p^i}$, and utilize the proven result from part (a) to finish.