2
$\begingroup$

Consider any $10$ different positive integers. Prove that you can choose four numbers out of the ten numbers ($a<b<c<d$), such that for any two numbers $x<y\in \{a,b,c,d\}$, $x|y$, or for any two numbers $x<y\in \{a,b,c,d\}$, $x$ is not a divisor of $y$.

$\endgroup$

closed as off-topic by Carl Mummert, Saad, Shailesh, Brian Borchers, Xander Henderson Mar 24 '18 at 4:07

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Carl Mummert, Saad, Shailesh, Brian Borchers, Xander Henderson
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Note that for 9 it is not true. Why 10 is the smallest number? I think it is connected with the fact $(4-1)(4-1)=9$. $\endgroup$ – Leo Gardner Mar 20 '18 at 18:36
  • 1
    $\begingroup$ -1 because you did not identify the "graph theory book" from which you copied that problem. Unattributed quotation is bad. $\endgroup$ – bof Mar 20 '18 at 23:03
  • $\begingroup$ Hey! I understand you, but my book has an hebrew title... $\endgroup$ – Leo Gardner Mar 21 '18 at 7:17
  • $\begingroup$ You can probably translate the title into English, and you can certainly give the author's name as it appears on his international publications. $\endgroup$ – bof Mar 21 '18 at 8:59
6
$\begingroup$

This may go outside your view of this problem as a graph theory problem, but there's a more general concept that's being applied here known as Dilworth's Theorem. Think of these numbers forming a digraph, where $(x,y)$ is a directed edge if $x|y$. Note that this digraph has the transitive property, namely that if $(x,y)$ and $(y,z)$ are edges, then $(x,z)$ is also an edge, and the antisymmetric property, that if $(x,y)$ is an edge and $x\neq y$, then $(y,x)$ is not an edge. These all follows from our knowledge of divisibility.

We in fact have a poset structure here, where $x<y$ if $(x,y)$ is an edge. By Dilworth's theorem, the largest antichain is the size of the smallest partition of the poset into chains. If this size is at least $4$, then our size $4$ antichain is a set of elements none of which are related, i.e. none of which divides another. Then assume this size is less than $4$, i.e. at most $3$. Then one of our chains must have size at least $4$. If not, we'd have at most $3$ chains with at most $3$ elements each, meaning we have at most $9$ elements, a contradiction. Then our chain of size at least $4$ is a set of numbers where for each pair, one divides the other. This is where your intuition comes in- we need $10$ because it exceeds $3\times 3$.

$\endgroup$
  • 1
    $\begingroup$ Dilworth's theorem is overkill. All you need is the comparatively trivial fact that the size of the largest chain is equal to the size of the smallest partition of the poset into antichains. $\endgroup$ – bof Mar 20 '18 at 23:06

Not the answer you're looking for? Browse other questions tagged or ask your own question.