Maths Olympiad Prep

Library / /54 of 62

, 2020

Algebra Difficulty 6.5 National Olympiad Find the answer United States

Problem:

While waiting for their next class on Killian Court, Alesha and Belinda both write the same sequence SS on a piece of paper, where SS is a 2020-term strictly increasing geometric sequence with an integer common ratio rr. Every second, Alesha erases the two smallest terms on her paper and replaces them with their geometric mean, while Belinda erases the two largest terms in her paper and replaces them with their geometric mean. They continue this process until Alesha is left with a single value AA and Belinda is left with a single value BB. Let r0r_{0} be the minimal value of rr such that AB\frac{A}{B} is an integer. If dd is the number of positive factors of r0r_{0}, what is the closest integer to log2d\log _{2} d ?

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Solution:

Because we only care about when the ratio of AA to BB is an integer, the value of the first term in SS does not matter. Let the initial term in SS be 11. Then, we can write SS as 1,r,r2,,r20191, r, r^{2}, \ldots, r^{2019}. Because all terms are in terms of rr, we can write A=raA = r^{a} and B=rbB = r^{b}. We will now solve for aa and bb.

Observe that the geometric mean of two terms rmr^{m} and rnr^{n} is simply rm+n2r^{\frac{m+n}{2}}, or rr raised to the arithmetic mean of mm and nn. Thus, to solve for aa, we can simply consider the sequence 0,1,2,,20190, 1, 2, \ldots, 2019, which comes from the exponents of the terms in SS, and repeatedly replace the smallest two terms with their arithmetic mean. Likewise, to solve for bb, we can consider the same sequence 0,1,2,,20190, 1, 2, \ldots, 2019 and repeatedly replace the largest two terms with their arithmetic mean.

We begin by computing aa. If we start with the sequence 0,1,,20190, 1, \ldots, 2019 and repeatedly take the arithmetic mean of the two smallest terms, the final value will be
a=0+12+22+32++2019=k=12019k222020k2 a = \frac{\frac{\frac{0+1}{2} + 2}{2} + 3}{2} + \cdots + 2019 = \sum_{k=1}^{2019} \frac{k}{2} \frac{2^{2020-k}}{2}
Then, we can compute
2a=k=12019k22019ka=2aa=k=12019k22019kk=12019k22020k=k=12019k22019kk=02018k+122019k=2019j=1201912j=2019(1122019)=2018+122019 \begin{aligned} 2a &= \sum_{k=1}^{2019} \frac{k}{2^{2019-k}} \\ \Longrightarrow a &= 2a - a = \sum_{k=1}^{2019} \frac{k}{2^{2019-k}} - \sum_{k=1}^{2019} \frac{k}{2^{2020-k}} \\ &= \sum_{k=1}^{2019} \frac{k}{2^{2019-k}} - \sum_{k=0}^{2018} \frac{k+1}{2^{2019-k}} \\ &= 2019 - \sum_{j=1}^{2019} \frac{1}{2^{j}} \\ &= 2019 - \left(1 - \frac{1}{2^{2019}}\right) = 2018 + \frac{1}{2^{2019}} \end{aligned}
Likewise, or by symmetry, we can find b=1122019b = 1 - \frac{1}{2^{2019}}.

Since we want AB=rarb=rab\frac{A}{B} = \frac{r^{a}}{r^{b}} = r^{a-b} to be a positive integer, and ab=(2018+122019)(1122019)=2017+122018a-b = \left(2018 + \frac{1}{2^{2019}}\right) - \left(1 - \frac{1}{2^{2019}}\right) = 2017 + \frac{1}{2^{2018}}, rr must be a perfect (22018)th\left(2^{2018}\right)^{\text{th}} power. Because r>1r > 1, the minimal possible value is r=222018r = 2^{2^{2018}}. Thus, d=22018+1d = 2^{2018} + 1, and so log2d\log_{2} d is clearly closest to 20182018.

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.