2005 AIME I Problem 12

Question

For positive integers

n,

let

\tau(n)

denote the number of positive integer divisors of

n,

including

1

and

n.

For example,

\tau(1) = 1

and

\tau(6) = 4.

Define

S(n)

by

S(n) = \tau(1) + \tau(2) + \cdots + \tau(n).

Let

a

denote the number of positive integers

n \le 2005

with

S(n)

odd, and let

b

denote the number of positive integers

n \le 2005

with

S(n)

even. Find

|a - b|.

Answer

Answer: 25

Concepts:parity perfect square factor counting

Difficulty rating: 2760

Small hint:

\tau(n)

is odd exactly when

n

is a perfect square, so

S(n)

changes parity only at squares

Big hint:

S(n)

is odd exactly when

\lfloor\sqrt{n}\rfloor

is odd; count

n \le 2005

block by block between consecutive squares

Solution:

Divisors of

n

pair up as

d

and

\frac{n}{d},

so

\tau(n)

is odd exactly when

n

is a perfect square. Hence

S(n)

changes parity exactly at the squares, which means

S(n)

is odd exactly when the number of squares up to

n,

namely

\lfloor\sqrt{n}\rfloor,

is odd.

For each

k,

there are

2k + 1

integers

n

with

\lfloor\sqrt{n}\rfloor = k,

namely

k^2 \le n \le k^2 + 2k.

Since

44^2 = 1936

\le 2005

\lt 2025 = 45^2,

the odd values

k = 1, 3, \ldots, 43

all have their full blocks within range, so

\begin{aligned} a &= \sum_{k \text{ odd},\, k \le 43} (2k + 1) \\ &= 2(1 + 3 + \cdots + 43) + 22 \\ &= 2 \cdot 484 + 22 \\ &= 990. \end{aligned}

Then

b = 2005 - 990 = 1015,

and

|a - b| = 25.

2005 AIME I Problem 12

Answer: 25

Difficulty rating: 2760

Small hint:

Big hint:

Solution:

Problem 12 in other years