Problem A. 803. (September 2021)

A. 803. Let \(\displaystyle \pi (n)\) denote the number of primes less than or equal to \(\displaystyle n\). A subset of \(\displaystyle S=\{1,2,\dots,n\}\) is called primitive if there are no two elements in it with one of them dividing the other. Prove that for \(\displaystyle n\ge 5\) and \(\displaystyle 1\le k<\frac{\pi (n)}{2}\) the number of primitive subsets of \(\displaystyle S\) with \(\displaystyle k+1\) elements is greater or equal to the number of primitive subsets of \(\displaystyle S\) with \(\displaystyle k\) elements.

Proposed by Cs. Sándor, Budapest

(7 pont)

Deadline expired on October 11, 2021.

Solution of user L567 on AoPS, written down by Tashi Diaconescu

Consider the following key claim:

Claim: Given a primitive subset with \(\displaystyle k\) elements (different from \(\displaystyle \{1\}\)), there exists at least \(\displaystyle \pi(n) - k\) prime powers of distinct primes which can be added to the set while still keeping it primitive.

Proof: Induct on \(\displaystyle k\), for \(\displaystyle k = 0\) take all primes. Now suppose it's true until a point, and we have added a new element, say \(\displaystyle \prod\limits_{i=1}^m p_i^{\alpha_i}\), with \(\displaystyle p_i < p_j\) for \(\displaystyle j > i\), if \(\displaystyle p_i\) is among the remaining prime powers, and \(\displaystyle i < m\), then increase its power to \(\displaystyle \alpha_i + 1\) so it's still primitive, since we lose out on at most one prime power (the one with \(\displaystyle p_m\)), the induction holds.

Ignore the subset \(\displaystyle \{1\}\) for now. Each primitive subset with \(\displaystyle k\) elements corresponds to \(\displaystyle \pi(n) - k\) subsets with \(\displaystyle k+1\) elements and each primitive \(\displaystyle k+1\) subset corresponds to exactly \(\displaystyle k+1\) things with \(\displaystyle k\) elements. So if there are \(\displaystyle M(k)\) primitive \(\displaystyle k\) subsets, then we have (now including \(\displaystyle \{1\}\))

\(\displaystyle M(k+1) \ge \frac{(\pi(n) - k)(M(k)-1)}{k+1} + 1 \ge M(k),\)

as desired.

Statistics:

18 students sent a solution.
7 points:	Bán-Szabó Áron, Jánosik Máté, Móricz Benjámin, Simon László Bence, Varga Boldizsár, Wiener Anna.
6 points:	Ben Gillott, Berkó Sebestyén , Bognár 171 András Károly, Kovács 129 Tamás, Lovas Márton, Móra Márton Barnabás, Nádor Benedek, Németh Márton, Seres-Szabó Márton, Török Ágoston.
5 points:	1 student.
3 points:	1 student.

Problems in Mathematics of KöMaL, September 2021