Team Selection Test for IMO 2019

Question

Let n be a positive integer with b digits and l, r be non-negative integers satisfying l + r < b. We say that a positive integer number is a sub-divisor of n, if it divides the number obtained by erasing the first l and last r digits of n. (For example, sub-divisors of 143 are 1, 2, 3, 4, 7, 11, 13, 14, 43 and 143.) For any positive integer d, let A_d be the set of positive integers for which d is not a sub-divisor. Find all positive integers d for which the set A_d is finite.

Accepted Answer

Answer: All positive integers which are coprime with

10

. If a number is divisible by either

2

or

5

then it can not divide any number of the form

11 \dots 1

. Therefore, for all numbers which are not coprime with

10

the set

A_{d}

is not finite.

Now let

d

be a positive integer which is coprime with

10

and

b > d

. Let us show that any number

a_{b} a_{b - 1} \dots a_{1}

is not in the set

A_{d}

. Consider the numbers

a_{1}

,

a_{2} a_{1}

,

a_{3} a_{2} a_{1}

,

\dots

,

a_{b} a_{b - 1} \dots a_{1} (mod d)

. Since

d > b

there are

i

and

j

,

i > j

such that

a_{i} a_{i - 1} \dots a_{1} = a_{j} a_{j - 1} \dots a_{1} (mod d)

. Therefore,

a_{i} a_{i - 1} \dots a_{j - 1} \cdot 1 0^{j} = 0 (mod d)

. Since

d

is coprime with

10

we get

d ∣ a_{i} a_{i - 1} \dots a_{j - 1}

and hence

a_{b} a_{b - 1} \dots a_{1}

is not in

A_{d}

. Thus, all numbers in

A_{d}

have at most

d

digits and consequently

A_{d}

is finite.