Maths Olympiad Prep

Library / /14 of 22

Algebra Difficulty 6.6 National olympiad Prove it South Africa

A positive integer kk is said to be visionary if there are integers a>0a > 0 and b0b \ge 0 such that ak+b(k+1)=2020a \cdot k + b \cdot (k+1) = 2020. How many visionary integers are there?

Solution

All lower case variables in this solution denote integers. Let XX denote the set of visionary integers. We show that X={2020n:1n2020}X = \{\lfloor \frac{2020}{n} \rfloor : 1 \le n \le 2020\}.

If kk is a visionary integer, then there exist a>0a > 0 and b0b \ge 0 such that ak+b(k+1)=2020a k + b(k + 1) = 2020, i.e., 2020=k(a+b)+b2020 = k(a + b) + b, where 0b<a+b0 \le b < a + b. This implies that k=2020a+bk = \lfloor \frac{2020}{a+b} \rfloor and we also have 1a+b20201 \le a + b \le 2020, since a1a \ge 1 and k1k \ge 1. Hence kXk \in X. Conversely, let kXk \in X, i.e., k=2020nk = \lfloor \frac{2020}{n} \rfloor for some 1n20201 \le n \le 2020. Then 2020=kn+r2020 = k n + r, where 0r<n0 \le r < n. Put b=rb = r and a=nra = n - r. Then a>0a > 0 and b0b \ge 0, and we see that ak+b(k+1)=2020a k + b(k + 1) = 2020, i.e., kk is visionary.

In order to solve the problem, we need to find the cardinality of the set XX. To this end, write XX as the disjoint union of X1={2020n:1n<2020}X_1 = \{\lfloor \frac{2020}{n} \rfloor : 1 \le n < \sqrt{2020}\} and X2={2020n:2020<n2020}X_2 = \{\lfloor \frac{2020}{n} \rfloor : \sqrt{2020} < n \le 2020\}. (Note that 2020 is not a square.) Also, since the smallest element of X1X_1 is 20202020=202044=45\lfloor \frac{2020}{\lfloor \sqrt{2020} \rfloor} \rfloor = \lfloor \frac{2020}{44} \rfloor = 45, and the largest element of X2X_2 is 20202020+1=202045=44\lfloor \frac{2020}{\lfloor \sqrt{2020} \rfloor+1} \rfloor = \lfloor \frac{2020}{45} \rfloor = 44, the sets X1X_1 and X2X_2 are indeed disjoint.

Let 1n1<n220201 \le n_1 < n_2 \le \lfloor \sqrt{2020} \rfloor. If 2020n1=2020n2\lfloor \frac{2020}{n_1} \rfloor = \lfloor \frac{2020}{n_2} \rfloor, then 0<2020n12020n2<10 < \frac{2020}{n_1} - \frac{2020}{n_2} < 1, implying that 0<n2n1<10 < n_2 - n_1 < 1, an impossibility. This shows that X1X_1 has exactly 2020=44\lfloor \sqrt{2020} \rfloor = 44 elements.

Next, consider any nn such that 1n20201 \le n \le \lfloor \sqrt{2020} \rfloor. We show that there exists a qq, where 2020<q2020\sqrt{2020} < q \le 2020, such that 2020q=n\lfloor \frac{2020}{q} \rfloor = n. By the Division Algorithm, there exist (unique) qq and rr such that 2020=qn+r2020 = q n + r, where 0r<n0 \le r < n. Now if q2020q \le \lfloor \sqrt{2020} \rfloor, then 2020=qn+r<qn+n=n(q+1)2020(2020+1)=4445=19802020 = q n + r < q n + n = n(q+1) \le \lfloor \sqrt{2020} \rfloor \cdot (\lfloor \sqrt{2020} \rfloor + 1) = 44 \cdot 45 = 1980, a contradiction. So we have 2020<q2020\sqrt{2020} < q \le 2020. Moreover, n=2020qn = \lfloor \frac{2020}{q} \rfloor, as 2020=nq+r2020 = n q + r, where 0r<n<q0 \le r < n < q. Finally, if 2020<n2020\sqrt{2020} < n \le 2020, then 12020n<20201 \le \frac{2020}{n} < \sqrt{2020}, so that also 12020n<20201 \le \lfloor \frac{2020}{n} \rfloor < \sqrt{2020}, i.e., all elements of X2X_2 lie in the interval [1,2020][1, \lfloor \sqrt{2020} \rfloor]. This shows that X2=X1|X_2| = |X_1|, and we conclude that X=X1+X2=44+44=88|X| = |X_1| + |X_2| = 44 + 44 = 88.

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.