Maths Olympiad Prep

Library / /15 of 15

Algebra Difficulty 9.1 IMO level Prove it IMO

Determine all sequences a1,a2,a_{1}, a_{2}, \ldots of positive integers such that, for any pair of positive integers mnm \leqslant n, the arithmetic and geometric means
am+am+1++annm+1 and (amam+1an)1nm+1 \frac{a_{m}+a_{m+1}+\cdots+a_{n}}{n-m+1} \quad \text{ and } \quad \left(a_{m} a_{m+1} \cdots a_{n}\right)^{\frac{1}{n-m+1}}
are both integers.

Solutions — 3

Solution 1

Solution 1. Without loss of generality, we may divide all elements of S\mathcal{S} by any common factor, after which they cannot all be even. As ab+2ca \nmid b+2 c for aa even and bb odd, the elements of S\mathcal{S} are all odd.
We now divide into three cases:
Case 1: S=1|\mathcal{S}|=1.
The set S={t}\mathcal{S}=\{t\} clearly works.
Case 2: S=2|\mathcal{S}|=2.
Say S={r,s}\mathcal{S}=\{r, s\} with r<sr<s, so either sr+2rs \mid r+2 r or sr+2ss \mid r+2 s, and in either case s3rs \mid 3 r. We cannot have s=3r/2s=3 r / 2 as we assumed that rr is odd, so s=3rs=3 r and S={r,3r}\mathcal{S}=\{r, 3 r\}, which clearly works by examining cases for aa and bb.
Case 3: S3|\mathcal{S}| \geqslant 3.
If all elements of S\mathcal{S} are odd then for any b,cS,b+2c≢b(mod4)b, c \in \mathcal{S}, b+2 c \not \equiv b(\bmod 4). If ab+2ca \mid b+2 c with ab(mod4)a \equiv b(\bmod 4), this means there exists kk with b+2c=kab+2 c=k a and k3(mod4)k \equiv 3(\bmod 4), so k3k \geqslant 3. If aa is the greatest element of S\mathcal{S} and b<ab<a, we have b+2c<3ab+2 c<3 a, a contradiction. Thus when aa is the greatest element, no b<ab<a has ba(mod4)b \equiv a(\bmod 4) (and thus all elements other than the greatest are congruent modulo 4).
Let dd and ee be the largest and second largest element of S\mathcal{S} respectively. Let fd,ef \neq d, e be any other element of S\mathcal{S}. There is some cSc \in \mathcal{S} with ef+2ce \mid f+2 c, and e≢f+2c(mod4)e \not \equiv f+2 c(\bmod 4), so f+2c3ef+2 c \geqslant 3 e, so c>ec>e. Since ee is the second largest element of S,c=d\mathcal{S}, c=d, so ef+2de \mid f+2 d, and this holds for all fSf \in \mathcal{S} with f<ef<e, but can only hold for at most one such ff. So S3|\mathcal{S}| \leqslant 3.
Hence the elements of S\mathcal{S} are d>e>fd>e>f, and by the discussion above without loss of generality we may suppose these elements are all odd, ef(mod4)e \equiv f(\bmod 4) and d≢e(mod4)d \not \equiv e(\bmod 4). We have above that ef+2de \mid f+2 d. Furthermore, there exists some cSc \in \mathcal{S} with df+2cd \mid f+2 c, and cdc \neq d as d>fd>f so dfd \nmid f, so cec \leqslant e; as f+2e<3ef+2 e<3 e, we have e>d/3e>d / 3. Since f+2cf+2 c is odd and f+2c<3df+2 c<3 d, we have f+2c=df+2 c=d.
Subcase 3.1: c=fc=f.
Here d=3fd=3 f and ef+2d=7fe \mid f+2 d=7 f. As e>fe>f and ef(mod4)e \equiv f(\bmod 4), we have e=7f/3e=7 f / 3 and the elements are some multiples of {3,7,9}\{3,7,9\}. But a=7a=7 and b=9b=9 have no corresponding value of cc.
Subcase 3.2: c=ec=e.
Here d=f+2ed=f+2 e and ef+2d=3f+4ee \mid f+2 d=3 f+4 e so e3fe \mid 3 f. But this is not possible with e>fe>f and ef(mod4)e \equiv f(\bmod 4).

Solution 2

Let dd be the largest element. For any eSe \in \mathcal{S} with ede \neq d there must be a fSf \in \mathcal{S} such that de+2fd \mid e+2 f. This implies 2fe(modd)2 f \equiv-e(\bmod d), hence 2fde(modd)2 f \equiv d-e(\bmod d). Now ded-e is even (because all elements in S\mathcal{S} are odd) and dd is odd, so de2\frac{d-e}{2} is an integer and we have fde2(modd)f \equiv \frac{d-e}{2} (\bmod d). Further, 0<de2<d0<\frac{d-e}{2}<d, while we must also have 0<fd0<f \leqslant d, so f=de2f=\frac{d-e}{2}. We conclude that for any eSe \in \mathcal{S} with ede \neq d the integer de2\frac{d-e}{2} is also in S\mathcal{S} and not equal to dd.
Denote by e1<e2<<ek<de_{1}<e_{2}<\cdots<e_{k}<d the elements of S\mathcal{S}, where k1k \geqslant 1. Then de12>de22>>dek2\frac{d-e_{1}}{2}>\frac{d-e_{2}}{2}> \cdots>\frac{d-e_{k}}{2} are also elements of S\mathcal{S}, none of them equal to dd. Hence we must have e1=dek2e_{1}=\frac{d-e_{k}}{2} and
ek=de12e_{k}=\frac{d-e_{1}}{2}, so 2e1+ek=d=2ek+e12 e_{1}+e_{k}=d=2 e_{k}+e_{1}. We conclude e1=eke_{1}=e_{k}, so k=1k=1, and also d=2ek+e1=3e1d=2 e_{k}+e_{1}=3 e_{1}. Hence S={e1,3e1}\mathcal{S}=\left\{e_{1}, 3 e_{1}\right\} for some positive integer e1e_{1}.

Solution 3

Let dd be the largest element, and let eSe \in \mathcal{S} be any other element. We will say that xS(modd)x \in \mathcal{S} (\bmod d) if the unique element yy in {1,,d}\{1, \ldots, d\} such that xy(modd)x \equiv y(\bmod d) is an element of S\mathcal{S}. Note that by the choice of dd being the largest element, if xdx \neq d, then x≢0(modd)x \not \equiv 0(\bmod d). The given condition implies that if bSb \in \mathcal{S}, then b2S(modd)-\frac{b}{2} \in \mathcal{S}(\bmod d). Repeating this gives b2Sb4S(modd)-\frac{b}{2} \in \mathcal{S} \Rightarrow \frac{b}{4} \in \mathcal{S} (\bmod d), and by iterating, we have bSb(2)kS(modd)b \in \mathcal{S} \Rightarrow \frac{b}{(-2)^{k}} \in \mathcal{S}(\bmod d) for all kk. Since dd is odd, there is some gg such that (2)g1(modd)(-2)^{g} \equiv 1(\bmod d), so by setting k=g1k=g-1, we get that
 for all deS,2eS(modd) \text { for all } d \neq e \in \mathcal{S},-2 e \in \mathcal{S}(\bmod d) \text {. }
Now, if e>d2e>\frac{d}{2}, then 2eS(modd)-2 e \in \mathcal{S}(\bmod d) and d2e<0d-2 e<0, so 2d2eS2 d-2 e \in \mathcal{S}, contradicting the lack of even elements. Then e<d2e<\frac{d}{2} for any eS\{d}e \in \mathcal{S} \backslash\{d\}, so we have eSd2eSe \in \mathcal{S} \Rightarrow d-2 e \in \mathcal{S}. Since d2edd-2 e \neq d, we must have d2e<d2d-2 e<\frac{d}{2}, which rearranges to e>d4e>\frac{d}{4}.
Let λ(0,1)\lambda \in(0,1) be a positive real number and suppose we have proved that e>λde>\lambda d for any eS\{d}e \in \mathcal{S} \backslash\{d\}. Then d2e>λdd-2 e>\lambda d, which rearranges to e<(1λ)d2e<\frac{(1-\lambda) d}{2}. Then d2e<(1λ)d2d-2 e<\frac{(1-\lambda) d}{2}, which rearranges to e>(1+λ)d4e>\frac{(1+\lambda) d}{4}. Defining λ0=14\lambda_{0}=\frac{1}{4} and λi=1+λi14\lambda_{i}=\frac{1+\lambda_{i-1}}{4} for i1i \geqslant 1, we have shown that for all eS\{d}e \in \mathcal{S} \backslash\{d\} and all λi,e>λid\lambda_{i}, e>\lambda_{i} d. Now note that the sequence λi\lambda_{i} is increasing and bounded above by 13\frac{1}{3}, so it converges to some limit \ell, which satisfies =1+4\ell=\frac{1+\ell}{4}, so =13\ell=\frac{1}{3}. Hence ed3e \geqslant \frac{d}{3}, but then d2ed3d-2 e \geqslant \frac{d}{3} implies ed3e \leqslant \frac{d}{3}, so ee must be d3\frac{d}{3}, and we are done.
Comment. We can finish Solution 3 alternatively as follows: after showing that if eS\{d}e \in \mathcal{S} \backslash\{d\} then d2eS\{d}d-2 e \in \mathcal{S} \backslash\{d\}, note that
(d2e)d3=2d32e=2(ed3) (d-2 e)-\frac{d}{3}=\frac{2 d}{3}-2 e=-2\left(e-\frac{d}{3}\right)
So consider eS\{d}e \in \mathcal{S} \backslash\{d\} maximising ed3\left|e-\frac{d}{3}\right|. If ed3e \neq \frac{d}{3}, them the above shows that (d2e)d3>ed3\left|(d-2 e)-\frac{d}{3}\right|>\left|e-\frac{d}{3}\right|, which is a contradiction. Thus S\{d}\mathcal{S} \backslash\{d\} is empty or equal to {d3}\left\{\frac{d}{3}\right\}, which completes the proof.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.