MathDB

RMO 2024 Q6

Source: RMO 2024 Q6

November 3, 2024

number theory

Problem Statement

Let

n \geq 2

be a positive integer. Call a sequence

a_1, a_2, \cdots , a_k

of integers an

n

-chain if

1 = a_2 < a_ 2 < \cdots < a_k =n

,

a_i

divides

a_{i+1}

for all

i

,

1 \leq i \leq k-1

. Let

f(n)

be the number of

n

-chains where

n \geq 2

. For example,

f(4) = 2

corresponds to the

4

-chains

\{1,4\}

and

\{1,2,4\}

.
Prove that

f(2^m \cdot 3) = 2^{m-1} (m+2)

for every positive integer

m

.

Back to Problems View on AoPS