Given $26$ different positive integers , in any six numbers of the $26$ integers , there are at least two numbers , one can be devided by another. Then prove : There exists six numbers , one of them can be devided by the other five numbers .
Problem
Source: China Northern MO 2009 p3 CNMO
Tags: number theory, divides
13.12.2020 12:42
Let be $a_1<a_2<\dots<a_{25}<a_{26}$ the given positive integers. Denote $A=\{a_1,a_2,\dots,a_{25},a_{26}\}$; $m_1=\max\{x\in A\}=a_{26};\;A_1=\{x\in A\big|\;x|m_1\}$. Let be $m_2=\max\{x\in A\setminus A_1\}$ and denote $A_2=\{x\in A\setminus A_1\big|\;x|m_2\}$. Then: $m_3=\max\{x\in A\setminus (A_1\cup A_2)\}$ and denote $A_3=\{x\in A\setminus (A_1\cup A_2)\big|\;x|m_3\}$ and similarly $m_4,m_5,\dots,m_p;\;A_4,A_5,\dots,A_p$ with the properties: $m_k=\max\{x\in A\setminus\cup_{i=1}^{k-1} A_i\}$ and $A_k=\{x\in A\setminus \cup_{i=1}^{k-1} A_i\big|\;x|m_k\}$. $A=\cup_{i=1}^{p} A_i;\;p\in\mathbb{N};\;p<26$. $\textbf{Property 1:}$ $A_j\cap A_k=\phi,\;\forall 1\le j<k\le p$. Assume exist $y\in A;\;1\le j<k\le p$ such that $y\in A_j$ and $y\in A_k$. Then: $y\in A_k\Longrightarrow y\in A\setminus\cup_{i=1}^{k-1} A_i$, contradiction with the condition $y\in A_j$, where $j\in\{1,2,\dots,k-1\}$. Hence: we can write $A$ as the partition of the sets $A_i:\;A=\cup_{i=1}^{p} A_i;\;p\in\mathbb{N};\;p<26$. If exists $i\in\{1,2,\dots,p\}$ such that $|A_i|\ge6$, the problem is solved. Assume $|A_i|\le5,\;\forall i\in\{1,2,\dots,p\}$. Results: $p\ge\left\lceil\dfrac{26}{5}\right\rceil=6$. Consider the set $B=\{b_1,b_2,b_3,b_4,b_5,b_6\}$ such that $b_j\in A_j;\;j\in\{1,2,3,4,5,6\}$. Using the initial condition, exists $u,v\in\{1,2,3,4,5,6\};u\ne v$ such that $b_u|b_v$. Results: $b_u|m_u\Longrightarrow b_u\in A_u$; $b_u|b_v$ and $b_v|m_v\Longrightarrow b_u|m_v\Longrightarrow b_u\in A_v$, hence $A_u\cap A_v\ne\phi$, contradiction with the Property 1. Results: the assumption $|A_i|\le5,\;\forall i\in\{1,2,\dots,p\}$ is false, hence exists $i\in\{1,2,\dots,p\}$ such that $|A_i|\ge 6\Longleftrightarrow $ exist at least $5$ numbers $c\in A_i\subset A;\;c<m_i$ such that $c|m_i$.