13
$\begingroup$

I am trying to solve the following problem.

Assume that we are given 26 distinct positive integers. Show that either there exist 6 of them $x_1<x_2<x_3<x_4<x_5<x_6$, with $x_1$ dividing $x_2$, $x_2$ dividing $x_3$, $x_3$ dividing $x_4$, $x_4$ dividing $x_5$ and $x_5$ dividing $x_6$ or there exist six of them, such that none of them divides another one of these six.

A possibly good start is to assume that, in every six of these numbers, there exists at least one dividing another one of the same six.

Update. I have found a solution of the problem (for 17 numbers though) in a Russian site. As unbelievable as it may sound, this problem was a question in a 1983 Soviet Mathematics contest (Турниры Городов) for student of 7-8 grades!

I am presenting the solution I found in that site below as an answer, and it is generalised for $n^2+1$ distinct integers, where we show that either there exist $n+1$ of them dividing each other or none diving none else.

$\endgroup$
  • 3
    $\begingroup$ This is not a duplicate of the question on increasing and decreasing subsequences, as divisibility is a partial order, not a strict linear order. $\endgroup$ – ShreevatsaR Jan 26 '14 at 9:33
14
$\begingroup$

Apply Dilworth's Theorem to the poset of the $26$ integers under the divisibility relation. Either there is an antichain of length $6$ (no two of $6$ integers divide one another) or the set can be partitioned into at most $5$ chains (sequences where each integer divides the next), one of which must have length at least $6$ by the pigeonhole principle.

$\endgroup$
3
$\begingroup$

Define a chain as a sequence $(y_j)$ such that $y_1|y_2 |...|y_k$ and an antichain a sequence $(y_j)$ such that $y_1 \nmid y_2 \nmid .. \nmid y_k$.

To each $x$ in the initial sequence attach a pair of numbers $(i_x,j_x)$ such that $i_x$ is the the length of the longest chain ending in $x$ and $j_x$ is the length of the longest antichain starting with $x$.

Pick now two elements $x\neq y$ such that $x$ is before $y$ in the sequence $(x_n)$. If $x | y$ then $i_x<i_y$ since any chain ending in $x$ can be extended to a longer chain ending in $y$. If $x \nmid y$ then $j_x > j_y$ since any antichain starting in $y$ can be extended to a longer antichain starting in $x$. Therefore the application $x \mapsto (i_x,j_x)$ is injective.

Consider a sequence with $mn+1$ elements, and suppose the length of the longest chain is $m$ and the length of the longest antichain is $n$. Therefore the map $x \mapsto (i_x,j_x)$ is an injection from a set with $mn+1$ elements into a set with $mn$ elements. This is a contradiction proving that there is a chain of length $m+1$ or an antichain of length $n+1$.

In the problem presented here we have $m=n=5$.

$\endgroup$
  • $\begingroup$ The third paragraph should end $x \mapsto (i_x,j_x)$ instead of $x \mapsto (i_x,i_y)$. (I tried editing your answer, but the change was less than 6 characters, which isn't allowed.) $\endgroup$ – Steve Kass Dec 28 '13 at 2:46
  • $\begingroup$ @SteveKass: Got it fixed $\endgroup$ – Beni Bogosel Dec 28 '13 at 10:14
  • 3
    $\begingroup$ Your definition of antichain isn't right: the elements have to be such that none divides another. $2\nmid 5$ and $5\nmid 6$ but these three don't form an antichain. $\endgroup$ – universalset Jan 25 '14 at 14:41
  • $\begingroup$ I have the same doubt as @universalset: For the desired conclusion of the question (and for the general meaning of "antichain") to hold, you must define your antichain as a sequence such that none of them divides any other. But then we can no longer say that if $x\nmid y$, then an antichain starting at $y$ can be extended to a longer antichain starting at $x$. Indeed, the conclusion of this proof, that $x\mapsto (i_x,j_x)$ is injective, is not true: Consider the sequence $(2,3,4)$. Then, the pairs corresponding to $2$ and $3$ are both $(1,2)$ and $(1,2)$. $\endgroup$ – ShreevatsaR Jan 29 '14 at 3:57
2
$\begingroup$

I have found this solution (for 17 numbers though) in a Russian site, as this problem was a question in a 1983 Soviet Mathematics contest (Турниры Городов) for student of 7-8 classes!

Solution. We shall attach on each of our numbers $$ x_1<x_2<\cdots<x_{26}, $$ an index next to their subscript in the following fashion:

$x_1$ becomes $x_{1,1}$.

If $x_1$ divides $x_2$, then $x_2$ becomes $x_{2,2}$, otherwise it becomes $x_{2,1}$.

In general, if we have attached indices to $x_1,\ldots,x_k$, then the index of $x_{k+1}$ will be $1$ is none of the $x_1,\ldots,x_k$ divides $x_{k+1}$, or it will become $i+1$, if $i$ is the largest index of all the numbers which divide $x_{k+1}$.

If the index of some of the $x_j$'s is at least $6$ then we have have a sequence $$ x_{k_1,1} \mid x_{k_2,2} \mid x_{k_3,3} \mid x_{k_4,4} \mid x_{k_5,5}\mid x_{k_6,6}. $$ In all the indices are less or equal to $5$, then some number in $\{1,2,3,4,5\}$, say $j$, is necessarily the index of at least $6$ numbers, i.e. $$ x_{k_1,j} < x_{k_2,j} < x_{k_3,j} < x_{k_4,j} < x_{k_5,j} < x_{k_6,j}, $$ which means that none of the above $6$ numbers divide another one of them.

Note. Τhis can be generalised to finding a chain of $k$ numbers, fully ordered by division, or a subset of $\ell$ numbers, with none of them dividing another one, among $m$ distinct positive integers, whenever $(k-1)(\ell-1)\le m-1$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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