MathDB

Let

\pi(n)

denote the number of primes less than or equal to

n

. A subset of

S=\{1,2,\ldots, n\}

is called primitive if there are no two elements in it with one of them dividing the other. Prove that for

n\geq 5

and

1\leq k\leq \pi(n)/2,

the number of primitive subsets of

S

with

k+1

elements is greater or equal to the number of primitive subsets of

S

with

k

elements.
Proposed by Cs. Sándor, Budapest

Problem Statement