Maths Olympiad Prep

Library / /5 of 5

Number theory Difficulty 6.1 National Olympiad Prove it United States

Problem:

In the pattern shown below, row 1 (the bottom row) consists of two 11's, and row nn is formed by taking row n1n-1 and inserting between each adjacent pair of numbers aa and bb their sum a+ba+b:

15473857275837451
143525341
13231
121
11
1

In row 2019 of the pattern, how many copies of 2019 will there be?

Solution

Solution:

The number of copies of nn in row nn is ϕ(n)\phi(n), where ϕ\phi is the totient function, or the number of positive integers less than or equal to nn that are relatively prime to nn. To see this, consider the following pattern of fractions, where we start with 01\frac{0}{1} and 11\frac{1}{1} and insert a+cb+d\frac{a+c}{b+d} between ab\frac{a}{b} and cd\frac{c}{d}:

Figure 1

The denominators of these fractions form the pattern of numbers in the problem, and the fractions are in increasing order. Row nn contains all the fractions in the nnth Farey sequence exactly once, i.e. all the fractions with denominator at most nn (plus some other fractions). Thus, the number of copies of nn in row nn equals the number of fractions between 0 and 1 with denominator nn in simplest form. Each of these fractions must have numerator less than or equal to nn and relatively prime to nn, so there are ϕ(n)\phi(n) such fractions. Thus, there are ϕ(n)\phi(n) copies of nn in row nn.

The prime factorization of 20192019 is 36733 \cdot 673, thus in row 20192019 the number of copies of 20192019 is
ϕ(2019)=2019(113)(11673)=2672=1244 \phi(2019) = 2019\left(1-\frac{1}{3}\right)\left(1-\frac{1}{673}\right) = 2 \cdot 672 = 1244

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.