Maths Olympiad Prep

Library / /26 of 41

Number theory Difficulty 6.0 AIME, harder Prove it New Zealand

Problem:

In a sequence of numbers, a term is called golden if it is divisible by the term immediately before it. What is the maximum possible number of golden terms in a permutation of 1,2,3,,20211,2,3,\ldots ,2021?

Solution

Solution:

Let kk be the number of golden terms. We claim that k1010k \leq 1010.

Proof: Define the term immediately before a golden term to be a silver term. The number of silver terms is also kk. If aa is any silver term and bb is the corresponding golden term then we must have
ab220212<1011.a \leq \frac{b}{2} \leq \frac{2021}{2} < 1011.
Therefore a1010a \leq 1010. Hence a{1,2,3,,1010}a \in \{1,2,3,\ldots ,1010\} and therefore there can be at most 1010 different silver terms. Therefore k1010k \leq 1010.

Now we need to show that k=1010k = 1010 is indeed possible. To do this we first partition the set {1,2,3,,2021}\{1,2,3,\ldots ,2021\} into the following distinct parts:
{1,2,4,8,16,32,64,128,256,512,1024},\{1,2,4,8,16,32,64,128,256,512,1024\},
{3,6,12,24,48,96,192,384,768,1536},\{3,6,12,24,48,96,192,384,768,1536\},
{5,10,20,40,80,160,320,640,1280},\{5,10,20,40,80,160,320,640,1280\},
{7,14,28,56,112,224,448,896,1792},\{7,14,28,56,112,224,448,896,1792\},
\ldots
{2019},\{2019\},
{2021}.\{2021\}.
Each part starts with an odd number, which is then doubled until the result is larger than 2021.

Putting each part in the above sequence in order is our example. In this example every even term, 2n2n, is golden because it occurs immediately after the term nn. There are 1010 even numbers, so k=1010k = 1010 is possible.

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.