Maths Olympiad Prep

Library / /1 of 11

Number theory Difficulty 7.5 National Olympiad, round 2 Prove it Bulgaria

Problem:
Denote by d(a,b)d(a, b) the number of the divisors of a positive integer aa, which are greater than or equal to bb. Find all positive integers nn such that
d(3n+1,1)+d(3n+2,2)++d(4n,n)=2006 d(3 n+1,1)+d(3 n+2,2)+\cdots+d(4 n, n)=2006

Solution

Solution:
Denote by D(a,b)D(a, b) the set of the divisors of aa, which are greater than or equal to bb. Thus, D(a,b)=d(a,b)|D(a, b)|=d(a, b). Every integer kk, 1k41 \leq k \leq 4, belongs to at most one of the sets
D(3n+1,1),D(3n+2,2),,D(4n,n) D(3 n+1,1), D(3 n+2,2), \ldots, D(4 n, n)
Every integer kk, 1kn1 \leq k \leq n, 3n+1k4n3 n+1 \leq k \leq 4 n belongs to exactly one of the sets (1). The integers kk, 2n+1k3n2 n+1 \leq k \leq 3 n do not appear in the sets (1).
Let n+1k2nn+1 \leq k \leq 2 n, i.e. k=n+ik=n+i, i=1,,ni=1, \ldots, n. If kk belongs to one of the sets (1), then
3n+12(n+i)4n 3 n+1 \leq 2(n+i) \leq 4 n
or
3n+13(n+i)4n 3 n+1 \leq 3(n+i) \leq 4 n
We conclude that i=n+12,,ni=\left\lceil\frac{n+1}{2}\right\rceil, \ldots, n or i=1,,n3i=1, \ldots,\left\lfloor\frac{n}{3}\right\rfloor. The number of the integers from the interval [n+1,2n][n+1,2 n] that belong to exactly one of the sets (1) equals n2+n3\left\lceil\frac{n}{2}\right\rceil+\left\lfloor\frac{n}{3}\right\rfloor. Thus
D(3n+1,1)+D(3n+2,2)++D(4n,n)=2n+n2+n3 |D(3 n+1,1)|+|D(3 n+2,2)|+\cdots+|D(4 n, n)|=2 n+\left\lceil\frac{n}{2}\right\rceil+\left\lfloor\frac{n}{3}\right\rfloor
and therefore n=708n=708.

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.