MathDB

Divisibility mingled with combinatorics

Source: Romanian TST for 2019 IMO

October 1, 2019

set theorynumber theory

Problem Statement

Let be two natural numbers

m,n,

and

m

pairwise disjoint sets of natural numbers

A_0,A_1,\ldots ,A_{m-1},

each having

n

elements, such that no element of

A_{i\pmod m}

is divisible by an element of

A_{i+1\pmod m} ,

for any natural number

i.

Determine the number of ordered pairs

(a,b)\in\bigcup_{0\le j < m} A_j\times\bigcup_{0\le j < m} A_j

such that

a|b

and such that

\{ a,b \}\not\in A_k,

for any

k\in\{ 0,1,\ldots ,m-1 \} .

Radu Bumbăcea

Back to Problems View on AoPS