Maths Olympiad Prep

Track / Stage 6 / 254 of 400 #1734 of 2444

Problem 1734

National Olympiad, first round
Algebra Difficulty 6.4 Prove it THE 73rd ROMANIAN MATHEMATICAL OLYMPIAD - FINAL ROUND · Romania

Let the numbers r,s[1,)r, s \in [1, \infty) with the property that for every positive integers a,ba, b, with aa dividing bb, it results that [ar][ar] divides [bs][bs].
a) Prove that sr\frac{s}{r} is a positive integer.
b) Show that rr and ss are positive integers.
Remark. By [x][x] we denote the floor of the real number xx.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Next problem →

Official solution

a) We suppose that srN\frac{s}{r} \notin \mathbb{N}. Then, there exists kNk \in \mathbb{N} such that k<sr<k+1    kr<s<(k+1)rk < \frac{s}{r} < k+1 \iff kr < s < (k+1)r. Choosing b=aNb = a \in \mathbb{N}^*, arbitrary, we obtain [ar][as][ar] \mid [as] and thus [ar][as]k[ar][ar] \mid [as] - k[ar]. (1)
From s>krs > kr, we obtain that there exists u>0u > 0 such that us>ukr+2us > ukr + 2 and thus, for every a>ua > u we get as>akr+2    [as][akr]+2>akr+1>k[ar]as > akr + 2 \implies [as] \ge [akr] + 2 > akr + 1 > k[ar], so [as]>k[ar][as] > k[ar].
From (1) we obtain [as]k[ar][ar]    [as](k+1)[ar][as] - k[ar] \ge [ar] \iff [as] \ge (k+1)[ar], so,
as>(k+1)(ar1)    k+1>a((k+1)rs), as > (k+1)(ar - 1) \iff k+1 > a((k+1)r - s),
for every a>ua > u.
Thus, a<k+1(k+1)rsa < \frac{k+1}{(k+1)r-s}, for every a>ua > u, which is a contradiction, so the assumption is false.

b) Let us show that ss is a positive integer.
We will show that for every aNa \in \mathbb{N} such that ar2ar \ge 2, we get asNas \in \mathbb{N}.
If asNas \notin \mathbb{N}, then there exists nNn \in \mathbb{N}^* such that 1n+1{as}<1n\frac{1}{n+1} \le \{as\} < \frac{1}{n}, so 1(n+1){as}<n+1n21 \le (n+1)\{as\} < \frac{n+1}{n} \le 2, thus [(n+1){as}]=1[(n+1)\{as\}] = 1.
We obtain
[(n+1)as]=[(n+1)[as]+(n+1){as}]=(n+1)[as]+[(n+1){as}]=(n+1)[as]+1. [(n+1)as] = [(n+1)[as] + (n+1)\{as\}] = (n+1)[as] + [(n+1)\{as\}] = (n+1)[as] + 1.
Since [ar][as][ar] \mid [as] and [ar][(n+1)as][ar] \mid [(n+1)as], we obtain that [ar]1    [ar]=1[ar] \mid 1 \implies [ar] = 1, which is a contradiction.
Thus asNas \in \mathbb{N}, for every aNa \in \mathbb{N} with ar2ar \ge 2, from which we get (a+1)sN(a+1)s \in \mathbb{N}, so (a+1)sas=sN(a+1)s - as = s \in \mathbb{N}.

Let us prove that rr is a positive integer.
Let pp be an arbitrary prime number with p[r]>sp[r] > s and m=[p{r}]m = [p\{r\}]. Since p{r}<pp\{r\} < p, we get m<pm < p.
If m0m \ne 0, then (m,p)=1(m, p) = 1. Since
[pr]ps    [p([r]+{r})]ps    p[r]+mps. [pr] \mid ps \implies [p([r] + \{r\})] \mid ps \implies p[r] + m \mid ps.
Since (p[r]+m,p)=1    p[r]+ms(p[r] + m, p) = 1 \implies p[r] + m \mid s, we obtain a contradiction as p[r]>sp[r] > s.
Thus, m=0    p{r}<1    {r}<1pm = 0 \implies p\{r\} < 1 \implies \{r\} < \frac{1}{p}, for every prime number pp, with p>s[r]    {r}=0p > \frac{s}{[r]} \implies \{r\} = 0 and thus, rNr \in \mathbb{N}.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.