ongelijkheid en diophantische vergelijking

Opgave - USAMO 1975 vraag 1

Als $x,y>0$, bewijs dan dat
$$\lfloor5x\rfloor+\lfloor5y\rfloor\geq\lfloor3x+y\rfloor+\lfloor3y +x\rfloor.$$
Toon ook aan dat
$$\frac{(5a)!(5b)!}{a!b!(3a+b)!(3b+a)!}$$
een natuurlijk getal is voor alle $a,b\in\mathbb N$.

Oplossing

Deel 1

Schrijf $x = n + c$ met $n \in \mathbb{N}$ en $0 \leq c < 1, a \in \mathbb{R}$.
Schrijf $y = m + d$ met $m \in \mathbb{N}$ en $0 \leq d < 1, d \in \mathbb{R}$.
We zullen bewijzen dat
$$\left \lfloor{5x}\right \rfloor + \left \lfloor{5y}\right \rfloor \geq \left \lfloor{x}\right \rfloor + \left \lfloor{y}\right \rfloor + \left \lfloor{3x+y}\right \rfloor + \left \lfloor{3y+x}\right \rfloor$$
Dit impliceert ook dat $\left \lfloor{5x}\right \rfloor + \left \lfloor{5y}\right \rfloor \geq \left \lfloor{3x+y}\right \rfloor + \left \lfloor{3y+x}\right \rfloor$ want $\left \lfloor{x}\right \rfloor + \left \lfloor{y}\right \rfloor \geq 0$. Maak nu de substituties en we krijgen dat
$$\left \lfloor{5n+5c}\right \rfloor + \left \lfloor{5m+5d}\right \rfloor \geq \left \lfloor{n+c}\right \rfloor + \left \lfloor{m+d}\right \rfloor + \left \lfloor{3n+3c+m+d}\right \rfloor + \left \lfloor{3m+3d+n+c}\right \rfloor$$
$$\iff 5n + \left \lfloor{5c}\right \rfloor + 5m + \left \lfloor{5d}\right \rfloor \geq n + \left \lfloor{c}\right \rfloor + m +\left \lfloor{d}\right \rfloor + 3n + m + \left \lfloor{3c+d}\right \rfloor + 3m + n + \left \lfloor{3d+c}\right \rfloor$$
$$\iff \left \lfloor{5c}\right \rfloor + \left \lfloor{5d}\right \rfloor \geq \left \lfloor{3c+d}\right \rfloor + \left \lfloor{3d+c}\right \rfloor$$
want $\left \lfloor{c}\right \rfloor = \left \lfloor{d}\right \rfloor = 0$.
Aangezien we weten dat $0 \leq c,d < 1$, is het eenvoudig na te gaan met gevalsonderzoek (bestudeer $\frac{i}{5} \leq c < \frac{i+1}{5}, i \in [0,1,2,3,4]$) dat $$\left \lfloor{5c}\right \rfloor + \left \lfloor{5d}\right \rfloor \geq \left \lfloor{3c+d}\right \rfloor + \left \lfloor{3d+c}\right \rfloor.$$

Iets preciezer;
zonder verlies van algemeenheid kan men $c \le d$ veronderstellen en dat $5c, 5d$ bijna een geheel getal is, i.e. als er een tegenvoorbeeld bestaat, bestaat er een waarbij $c$ en $d$ beide van de vorm $\frac i5 - \epsilon$ zijn voor een kleine waarde $\epsilon>0.$
Indien $5c \ge 3c+d$, dan is het resultaat duidelijk daar $5d \ge 3d+c.$
Dus $d>2c.$
Een tegenvoorbeeld voldoet aan $\left \lfloor{5c}\right \rfloor = \left \lfloor{3c+d}\right \rfloor -1.$
Indien $ 2d-c>1$, is $\left \lfloor{5d}\right \rfloor = \left \lfloor{3d+c}\right \rfloor +1$ en zou de conclusie ook terug volgen.
Dit betekent dat $3c\le 2d-c \le 1$ en dus $c=\frac 15 - \epsilon$.
Nu kunnen we $d= \frac 25- \epsilon$ or $\frac 35-\epsilon$ nemen en in beide gevolgen opnieuw concluderen.

Deel 2

We zullen het vorige deel gebruiken om deel $2$ van de vraag op te lossen. We willen bewijzen dat het aantal keer dat een priemfactor $p$ in de teller voorkomt, meer is dan dat hij in de noemer voorkomt, en dus $$v_p((5a)!) + v_p((5b)!) \geq v_p(a!) + v_p(b!) + v_p((3a+b)!) + v_p((3b+a)!)$$
voor een willekeurig priemgetal $p$. Wegens de formule/stelling van Legendre kunnen we $v_p(x!)$ precies tellen en hebben we de vraag opgelost als we kunnen bewijzen dat:
\[\left \lfloor{\frac{5a}{p^k}}\right \rfloor + \left \lfloor{\frac{5b}{p^k}}\right \rfloor \geq \left \lfloor{\frac{a}{p^k}}\right \rfloor + \left \lfloor{\frac{b}{p^k}}\right \rfloor + \left \lfloor{\frac{3a+b}{p^k}}\right \rfloor + \left \lfloor{\frac{3b+a}{p^k}}\right \rfloor\]
voor alle $k \in \mathbb{N}_0$. Merk echter op dat als we $\frac{a}{p^k}$ nu vervangen door $x$, en $\frac{b}{p^k}$ vervangen door $y$, we krijgen dat we moeten bewijzen dat
\[\left \lfloor{5x}\right \rfloor + \left \lfloor{5y}\right \rfloor \geq \left \lfloor{x}\right \rfloor + \left \lfloor{y}\right \rfloor + \left \lfloor{3x+y}\right \rfloor + \left \lfloor{3y+x}\right \rfloor\]
Dit fenomeen hebben we echter al bewezen in deel $1$ en zijn we klaar. Q.E.D.