AlgebraDifficulty 6.6National olympiadProve itSouth Africa
A positive integer k is said to be visionary if there are integers a>0 and b≥0 such that a⋅k+b⋅(k+1)=2020. How many visionary integers are there?
Solution
All lower case variables in this solution denote integers. Let X denote the set of visionary integers. We show that X={⌊n2020⌋:1≤n≤2020}.
If k is a visionary integer, then there exist a>0 and b≥0 such that ak+b(k+1)=2020, i.e., 2020=k(a+b)+b, where 0≤b<a+b. This implies that k=⌊a+b2020⌋ and we also have 1≤a+b≤2020, since a≥1 and k≥1. Hence k∈X. Conversely, let k∈X, i.e., k=⌊n2020⌋ for some 1≤n≤2020. Then 2020=kn+r, where 0≤r<n. Put b=r and a=n−r. Then a>0 and b≥0, and we see that ak+b(k+1)=2020, i.e., k is visionary.
In order to solve the problem, we need to find the cardinality of the set X. To this end, write X as the disjoint union of X1={⌊n2020⌋:1≤n<2020} and X2={⌊n2020⌋:2020<n≤2020}. (Note that 2020 is not a square.) Also, since the smallest element of X1 is ⌊⌊2020⌋2020⌋=⌊442020⌋=45, and the largest element of X2 is ⌊⌊2020⌋+12020⌋=⌊452020⌋=44, the sets X1 and X2 are indeed disjoint.
Let 1≤n1<n2≤⌊2020⌋. If ⌊n12020⌋=⌊n22020⌋, then 0<n12020−n22020<1, implying that 0<n2−n1<1, an impossibility. This shows that X1 has exactly ⌊2020⌋=44 elements.
Next, consider any n such that 1≤n≤⌊2020⌋. We show that there exists a q, where 2020<q≤2020, such that ⌊q2020⌋=n. By the Division Algorithm, there exist (unique) q and r such that 2020=qn+r, where 0≤r<n. Now if q≤⌊2020⌋, then 2020=qn+r<qn+n=n(q+1)≤⌊2020⌋⋅(⌊2020⌋+1)=44⋅45=1980, a contradiction. So we have 2020<q≤2020. Moreover, n=⌊q2020⌋, as 2020=nq+r, where 0≤r<n<q. Finally, if 2020<n≤2020, then 1≤n2020<2020, so that also 1≤⌊n2020⌋<2020, i.e., all elements of X2 lie in the interval [1,⌊2020⌋]. This shows that ∣X2∣=∣X1∣, and we conclude that ∣X∣=∣X1∣+∣X2∣=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.