# A problem with 26 distinct positive integers

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, 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.

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

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.

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$.

• 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.) – Steve Kass Dec 28 '13 at 2:46
• @SteveKass: Got it fixed – Beni Bogosel Dec 28 '13 at 10:14
• 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. – universalset Jan 25 '14 at 14:41
• 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)$. – ShreevatsaR Jan 29 '14 at 3:57

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 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$$.