Existence of a subset satisfying specific conditions

For discussing Olympiad Level Combinatorics problems
User avatar
Phlembac Adib Hasan
Posts:1016
Joined:Tue Nov 22, 2011 7:49 pm
Location:127.0.0.1
Contact:
Existence of a subset satisfying specific conditions

Unread post by Phlembac Adib Hasan » Wed Oct 12, 2016 10:43 am

Let $A$ be a finite set of positive integers. Prove that $\exists B\subseteq A$ satisfying the following conditions:

i) if $b_1,b_2\in B$ are distinct, then neither $b_1$ and $b_2$ nor $b_1+1$ and $b_2+1$ are multiples of each other, and
ii) for any $a\in A$, we can find a $b\in B$ such that either $a|b$ or $b+1|a+1$.

Source: Kürschák 2016, problem 2
Welcome to BdMO Online Forum. Check out Forum Guides & Rules

Post Reply