Exercise 4.5.8* (Torture chambers)

Proof. Here $n$ is a positive integer.

(a)

Existence of a subset $𝒮$having property $M$and containing $n$elements.

Consider the subset of $[[1,2n]]$ defined by

$$𝒮=[[n+1,2n]].$$

Then $𝒮$ contains $n$ elements. Assume for the sake of contradiction that two distinct elements $a,b$ satisfy $a\mid b$, so that there is some integer $k>1$ such that $b=\mathit{ka}$. Then $a>n$, and $b\le 2n$, thus $k=\frac{b}{a}<2$. But $k\ge 2$. This contradiction shows that $𝒮$ has the property $M$.

Non-existence of a subset $𝒮$having property $M$and containing $n+1$elements.

Consider for every odd positive integer $m$ the set

$$A_m=\{x\in [[1,2n]]\mid \exists <!--\; FUNCTION\; APPLICATION\; -->k\in \mathbb{N},x=m{2}^k\},$$

and the sequence ${(A_m)}_{m\in I}$, where

$$I=\{m\in [[1,2n]]\mid m\equiv 1(\mathit{mod}2)\}=\{1,3,\dots ,2n-1\}.$$

Since every integer is in a unique way in the form $x=m{2}^k$, where $m$ is an odd positive integer, and $k\ge 0$ an integer, then ${(A_m)}_{m\in I}$ is a partition of $[[1,2n]]$, that is

$$\underset{m\in I}{\bigcup }{A}_m=[[1,2n]],\forall <!--\; FUNCTION\; APPLICATION\; -->m\in I,\forall <!--\; FUNCTION\; APPLICATION\; -->m^{\prime }\in I,m\ne m^{\prime }\Rightarrow A_m\cap A_{m^{\prime }}=\varnothing .$$

Suppose that $𝒮\subset [[1,2n]]$ contains $n+1$ elements.

Since $|I|=n$, there are $n$ classes $A_m$ in the partition, so by the pigeonhole principle, there are two distinct elements $a<b$ in $𝒮$ which are in the same $A_m$ for some odd integer $m$. Then

$$a=m{2}^j,b=m{2}^k,\text{where }j<k,$$

thus $a\mid b,a\ne b$, so $𝒮$ has not the property $M$. This shows that no subset of $[[1,2n]]$ with $n+1$ elements has property $M$.

(b)

Let $𝒮$ be a subset of $\{1,2,3,\dots ,2n-1\}$. A fortiori, $𝒮$ is a subset of $[[1,2n]]$. Therefore, by part (a), $𝒮$ has at most $n$ elements. Moreover $${𝒮}_0=[[n,2n-1]]=\{n,n+1,n+2,\dots ,2n-1\}$$

has $n$ elements and has the property $M$, so we obtain the same results for subsets $𝒮$ of $\{1,2,3,\dots ,2n-1\}$.

(c)

Consider now a subset $𝒮$ of $B=\{1,3,5,\dots ,2n-1\}$ satisfying the property $M$. We define for every odd $m$ such that $m\equiv \pm 1(\mathit{mod}3)$ the subset $$B_m=\{x\in [[1,2n-1]]\mid \exists <!--\; FUNCTION\; APPLICATION\; -->k\in \mathbb{N},x=m{3}^k\},$$

and the sequence ${(B_m)}_{m\in J}$, where

$$J=\{m\in B\mid m\not\equiv 0(\mathit{mod}3)\}=\{1,5,7,11,\dots \}$$

is the set of $m\in [[1,2n-1]]$ such that $m\equiv \pm 1(\mathit{mod}6)$.

As in part (a), ${(B_m)}_{m\in J}$ is a partition of $B$, with $|J|$ classes.

Let $𝒮$ a subset of $B$ with $|J|+1$ elements. Then there are two elements $a,b$ in $𝒮$ such that $a<b$ are in a same class $B_m$, thus $a\mid b$, so $𝒮$ has not the property $M$. This shows that every $𝒮$ satisfying the property has at most $|J|$ elements.

If remains to estimate $|J|$. Since

$$\begin{array}{llll}\hfill J& =\{m\in [[1,2n-1]]\mid m\equiv \pm 1(\mathit{mod}6)\}& \hfill & \\ \hfill & =\{1,7,\dots ,6k-5\}\cup \{5,13,\dots ,6l-1\},& \hfill & \end{array}$$

where $k$ is the larger integer such that $6k-5\le 2n-1$, so $k=\lfloor \frac{n+2}{3}\rfloor$, and $l$ is the larger integer such that $6l-1\le 2n-1$, so $l=\lfloor \frac{n}{3}\rfloor$. This gives

$$|J|=\lfloor \frac{n}{3}\rfloor +\lfloor \frac{n+2}{3}\rfloor ,$$

or equivalently (see Problem 4.1.15)

$$|J|=n-\lfloor \frac{n+1}{3}\rfloor .$$

Consider now the particular solution

$$𝒮=\left\{2\lfloor \frac{n+1}{3}\rfloor +1,2\lfloor \frac{n+1}{3}\rfloor +3,\dots ,2n-1\right\}.$$

Then $𝒮$ has $n-\lfloor \frac{n+1}{3}\rfloor$ elements. Moreover $𝒮$ has the property $M$: if two elements $a<b$ in $𝒮$ are such that $a\mid b$, then $b=\mathit{aq}$, where $q>1$. Since $a$ and $b$ are odd, $q\ne 2$ so $q\ge 3$. Moreover

$$q=\frac{b}{a}\le \frac{2n-1}{2\lfloor \frac{n+1}{3}\rfloor +1},$$

where

$$\begin{array}{llll}\hfill \frac{2n-1}{2\lfloor \frac{n+1}{3}\rfloor +1}<3& ⟺n<3\lfloor \frac{n+1}{3}\rfloor +2& \hfill & \\ \hfill & ⟺\frac{n+1}{3}<\lfloor \frac{n+1}{3}\rfloor +1.& \hfill & \end{array}$$

Since the last inequality is true by definition of the greatest integer function, the first is true, so $q<3$. This is a contradiction, because $q\ge 3$. This shows that $𝒮$ has the property $M$, where this particular $𝒮$ has $|J|=n-\lfloor \frac{n+1}{3}\rfloor$ elements.

In conclusion, there are

$$n-\lfloor \frac{n+1}{3}\rfloor$$

elements in the largest subset $𝒮$ of $\{1,3,5,7,\dots ,2n-1\}$ having property $M$.