Let x1,x2,…,x2023 be distinct real positive numbers such that an=(x1+x2+⋯+xn)(x11+x21+⋯+xn1) is an integer for every n=1,2,…,2023. Prove that a2023⩾3034.
Solutions — 2
Solution 1
We start with some basic observations. First note that the sequence a1,a2,…,a2023 is increasing and thus, since all elements are integers, an+1−an⩾1. We also observe that a1=1 and a2=(x1+x2)(x11+x21)>2 by Cauchy-Schwarz inequality and using x1=x2. So, a2⩾3.
Now, we proceed to the main part of the argument. We observe that 3034 is about three halves of 2023. Motivated by this observation, we will prove the following.
Claim. If an+1−an=1, then an+2−an+1⩾2.
In other words, the sequence has to increase by at least 2 at least half of the times. Assuming the claim is true, since a1=1, we would be done since a2023=(a2023−a2022)+(a2022−a2021)+⋯+(a2−a1)+a1⩾(2+1)⋅1011+1=3034
We now prove the claim. We start by observing that an+12==⩾==(x1+⋯+xn+1)(x11+⋯+xn+11)(x1+⋯+xn)(x11+⋯+xn1)+1+xn+11(x1+⋯+xn)+xn+1(x11+⋯+xn1)an2+1+2xn+11(x1+⋯+xn)⋅xn+1(x11+⋯+xn1)an2+1+2an(an+1)2, where we used AM-GM to obtain the inequality. In particular, if an+1=an+1, then xn+11(x1+⋯+xn)=xn+1(x11+⋯+xn1).(1) Now, assume for the sake of contradiction that both an+1=an+1 and an+2=an+1+1 hold. In this case, (1) gives xn+21(x1+⋯+xn+1)=xn+2(x11+⋯+xn+11). We can rewrite this relation as xn+2xn+1(xn+11(x1+⋯+xn)+1)=xn+1xn+2(xn+1(x11+⋯+xn1)+1). From (1) again, we conclude that xn+1=xn+2 which is a contradiction.
Solution 2
The trick is to compare an+2 and an. Observe that an+22==⩾=(x1+⋯+xn+2)(x11+⋯+xn+21)(x1+⋯+xn)(x11+⋯+xn1)+(xn+1+xn+2)(xn+11+xn+21)+(x1+⋯+xn)(xn+11+xn+21)+(xn+1+xn+2)(x11+⋯+xn1)an2+(xn+1+xn+2)(xn+11+xn+21)+2(xn+1+xn+2)(xn+11+xn+21)(x1+⋯+xn)(x11+⋯+xn1)an2+(xn+1+xn+2)(xn+11+xn+21)+2an(xn+1+xn+2)(xn+11+xn+21), where we used AM-GM to obtain the inequality. Furthermore, we have (xn+1+xn+2)(xn+11+xn+21)>4 because xn+1=xn+2 by assumption. Therefore, it follows that an+22>an2+4+4an=(an+2)2 Because an+2 and an are both positive integers, we conclude that an+2⩾an+3 A simple induction gives a2k+1⩾3k+a1 for every k⩾0. Since a1=1, it follows that a2k+1⩾3k+1. We get the desired conclusion for k=1011.
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 reproduced verbatim; metadata (topic, difficulty) added by this project.