A nice problem about a number theory problem containing combinatorics! Prove that for any set $ A$ that is finitely positive integers, there exists a subset $B$ of $ A$ such that the following conditions are satisfied:
$i)$ if $b_1 \in B $ and $b_2\in B$ are distinct elements, then $b_1$ and $b_2$ are not multiples of each other, and neither are $b_1 + 1$ and $b_2+1.$ ( I mean $b_1$ is not divisible by $b_2$ and $b_2$ is not divisible by $b_1$)
$ii)$ for each $a \in A$ \ $ B ,$ we can find $b \in B$ such that either $a \mid b$ or $b+1 \mid a+1.$
I am very stuck with this problem , I have thought for days but no idea for this problem .Originally , my idea was to be inductive on the number of elements of A.That is, I assume that for every setA containing n trials that are satisfied, then every setAcontaining n+1 elements also satisfies . But the a|b condition keeps me from mining . So my guess is that this problem needs an algorithm to solve ! So I just want to ask everyone for a suggestion. I hope to get help from everyone. Thanks very much!
 A: Given a set $S$ of integers, define the maximal elements of $S$ to be those $s\in S$ which do not divide any $t\in S$ besides $t=s$. For example, the maximal elements of $\{1,2,4,9\}$ are $4$ and $9$. Initialize $A_0=A$, and let $B_0$ be the maximal elements of $A$. Then, given $(A_i,B_i)$, define
$$R_i=\big\{x\in B_i : \text{there exists some }y\in B_i\text{ with }x\neq y\text{ and }y+1\mid x+1\big\}.$$
Define $A_{i+1}=A_i\setminus R_i$, and let $B_{i+1}$ be the maximal elements of $A_i$. We claim that, for some $i$, $R_i=\emptyset$, and that then $B_i$ satisfies the desired property.
The intuition for this is as follows: we start with a set $B_0$ which satisfies (ii), and then figure out where (if at all) it fails to satisfy (i). By definition, no two distinct members of $B_0$ may divide one another, so the only issue is if $y+1 \mid x+1$ for some distinct $x,y\in B_0$. If this happens, we must remove either $x$ or $y$. We'd rather remove $x$, since then $a=x\in A$ still satisfies condition (ii) with $b=y\in B_0$. However, once we remove $x$, condition (ii) may fail -- there may be some $a\in A$ which divides no element of $B_0$ besides $x$. So, we recompute the maximal elements of $A$ with $x$ removed, with the knowledge that $y$ is still a maximal element (and so condition (ii) is still satisfied at $x=a$), and continue this process until it halts.

Now for the proof:
Firstly, it is easy to see why some $R_i$ must be empty. Until $R_i$ is empty, the size of $A_i$ decreases at each step:
$$|A_0|>|A_1|>|A_2|>\cdots.$$
Since $|A_0|=|A|$ is finite, the size of $A_i$ can only decrease finitely many times, and so eventually $R_i=\emptyset$.
We now claim that, if $R_i$ is empty, $B=B_i$ satisfies condition (i). Indeed, by the definition of a maximal element, there exist no distinct $b_1,b_2\in B$ with $b_1\mid b_2$, as otherwise $b_1$ would not be maximal. In addition, if $b_1+1\mid b_2+1$ for $b_1,b_2\in B$ distinct, then $b_2$ would be in $R_i$. Since $R_i=\emptyset$, this cannot occur. So, the set $B$ given by this process satisfies condition (i).
Finally, we'll show that $B_i$ satisfies condition (ii) for every $i$, by induction on $i$. For the base case of $i=0$, assume $B_0$ fails to satisfy (ii), and let $a$ be the largest element of $A\setminus B$ such that $a\nmid b$ for every $b\in B$. Since $a\not\in B$, $a$ is not a maximal element of $A$, and so there exists some $a'\in A$ with $a\mid a'$. Clearly, $a'\not\in B$. However, since $a$ was chosen to be the largest element of $A$ satisfying its definitional property, $a'$ must divide some element $b$ of $B$, and so $a\mid a'\mid b$, a contradiction.
For the inductive step, we first show that
$$B_i\subset B_{i+1}\cup R_i\tag{$\star$}.$$
The proof is by contradiction: consider some $b\in B_i$ which is neither in $B_{i+1}$ nor $R_i$. Since $b\not\in R_i$, we know $b\in A_{i+1}$; however, since $b\not\in B_{i+1}$, there exists some $b'\in A_{i+1}$ with $b'\neq b$ and $b\mid b'$. However, since $A_{i+1}\subset A_i$, such a $b'$ would mean that $b$ is not a maximal element of $A_i$, contradicting $b\in B_i$.
We now proceed with the inductive step. Fix $i$, and assume that, for every $a\in A$, there exists some $b\in B_i$ for which either $a\mid b$ or $b+1\mid a+1$ (if $a\in B_i$, we simply take $a=b$). Now, consider some $a\in A$.

*

*If there exists some $b\in B_i$ with $b+1 \mid a+1$, take the smallest such $b$. It is clear that $b\not\in R_i$, as $b\in R_i$ would contradict the minimality of $b$. This means by ($\star$) that $b\in B_{i+1}$, which is enough. (Note that this case covers the case of $a\in B_i$.)

*If $a\not\in B_i$ and there exists some $b\in B_i$ with $a\mid b$, we claim $a$ must be in $A_{i+1}$. Indeed, this would imply that $a$ is not maximal in any set that contains $B_i$ as a subset; in particular, $a\not\in B_j$ for any $0\leq j\leq i$. This means that $a\not\in R_j$ for any $0\leq j\leq i$, and so $a\in A_{i+1}$, as desired. Now, since $B_{i+1}$ is defined as the set of maximal elements of $A_{i+1}$, there exists some $b\in B_{i+1}$ with $a\mid b$, finishing the proof.

