MathDB

Let

S

be a finite set of positive integers which has the following property:if

x

is a member of

S

,then so are all positive divisors of

x

. A non-empty subset

T

S

is good if whenever

x,y\in T

and

x<y

, the ratio

y/x

is a power of a prime number. A non-empty subset

T

S

is bad if whenever

x,y\in T

and

x<y

, the ratio

y/x

is not a power of a prime number. A set of an element is considered both good and bad. Let

k

be the largest possible size of a good subset of

S

. Prove that

k

is also the smallest number of pairwise-disjoint bad subsets whose union is

S

Problem Statement