Iranian TST problem on maximum subset with some property in a poset

Question

Let $M$ be the largest subset of $\{1,\dots,n\}$ such that for each $x\in M$, $x$ divides at most one other element in $M$. Prove that$$ |M|\leq \left\lceil \frac{3n}4\right\rceil. $$

My attempt:

Let $M_1 = \{x\in M;\;\exists !y\in M:\; x|y \} $ and $M_0 = M\setminus M_1$. Obviously both $M_0$ and $M_1$ are an antichains in $M$ and they make a partition of $M$. And this is all I can find. I was thinking about Dilworth theorem but... Also, I was thinking, what if I add a new element $k\in M^C$ to $M$. Then $M\cup \{k\}$ is no more ''good'' set...

Answer 1

Divide the $M$ integers into $\lceil\frac{n}{2}\rceil$ groups, depending on the maximum odd divisor. Notice we can take at most two from each group and some groups have size $1$, we do the analysis mod $4$.

$n=4k:$

number of groups: $2k$, number of groups of size $1: k$, upper bound: $3k=\lceil\frac{12k}{4}\rceil=\lceil\frac{3n}{4}\rceil$

$n=4k+1:$

number of groups: $2k+1$, number of groups of size $1: k+1$, upper bound: $3k+1=\lceil\frac{12k+3}{4}\rceil=\lceil\frac{3n}{4}\rceil$

$n=4k+2:$

number of groups: $2k+1$, number of groups of size $1: k$, upper bound: $3k+2=\lceil\frac{12k+6}{4}\rceil=\lceil\frac{3n}{4}\rceil$

$n=4k+3:$

number of groups: $2k+2$, number of groups of size $1: k+1$, upper bound: $3k+3=\lceil\frac{12k+12}{4}\rceil=\lceil\frac{3n}{4}\rceil$

Answer 2

You are right. We first divide $M$ into two subsets , $M_1$ and $M_2$, where the former contains all $x$ such that $x$ divides exactly one other element, and $M_2$ contains all the others.

It is easy to see that $M_1$ is an antichain with respect to two elements being linked if one divides the other. This is because if $x$ and $y$ in $M_1$ are linked, then one of them divides two elements in the group , a contradiction. Similarly, it's easy to see that $M_2$ is also an antichain.

It's clear that the maximum size of an antichain is $\frac n2$,since if we take the greatest odd divisor of each element in the antichain, these will be distinct, but there are only $\frac n2$ of these. An example of a maximal antichain is $\frac n2 + 1 , ...,n$.

Suppose that $|M| \geq \frac {3n}4 + 1$. Then, take the greatest odd divisor of each element of $M$. No three elements can share this greatest odd divisor (can you see why?), and there are only $\frac n2$ of them, so by the pigeonhole principle, there must be at least $\frac n4$ pairs of numbers in $A$ having the same greatest odd divisor. Out of this list of greatest odd divisors, pick the biggest, say $D$. Since there are at least $\frac n4$ distinct odd divisors in the above list, it follows that $d > \frac n2$, but then , of the pair of numbers with $d$ as the greatest divisor, one of them must be greater than or equal to $2d \geq n$, giving the contradiction. Hence, the claim follows.