Let $p,q,r$ be distinct prime numbers and let \[A=\{p^aq^br^c\mid 0\le a,b,c\le 5\} \] Find the least $n\in\mathbb{N}$ such that for any $B\subset A$ where $|B|=n$, has elements $x$ and $y$ such that $x$ divides $y$. Ioan Tomescu
Problem
Source: Romanian TST 1997
Tags: floor function, ceiling function, number theory, prime numbers, combinatorics proposed, combinatorics, poset
17.09.2011 22:19
Since the set: $C=\{p^3,q^3,r^3,p^2q,p^2r,q^2p,q^2r,r^2p,r^2q,pqr\}$ is the maximum set with pairwise not divisable elements and $|C|=10$ 11 is the required number
17.09.2011 22:55
NO. A maximal set with pairwise not divisible arguments (a maximal antichain) has as triplets $(\alpha,\beta,\gamma)$ of exponents of $p,q,r$ the $27$ elements $(5,0,2),(5,1,1),(5,2,0)$, $(4,0,3),(4,1,2),(4,2,1),(4,3,0)$, $(3,0,4),(3,1,3),(3,2,2),(3,3,1),(3,4,0)$, $(2,0,5),(2,1,4),(2,2,3),(2,3,2),(2,4,1),(2,5,0)$, $(1,1,5),(1,2,4),(1,3,3),(1,4,2),(1,5,0)$, $(0,2,5),(0,3,4),(0,4,3),(0,5,2)$. Thus $28$ is the required number. This is a particular cas of the de Bruijn-Tengbergen-Kruyswijk theorem, stating that a maximal antichain of a product poset $[n_1] \times [n_2] \times \cdots n_k]$ is the a level of middle rank $\lfloor (n_1+n_2+\cdots + n_k)/2 \rfloor$ or $\lceil (n_1+n_2+\cdots + n_k)/2 \rceil$ (here $[n] = \{0,1,\ldots,n\}$). In our case, the product poset is $[5] \times [5]\times [5]$, and $\lfloor (5+5+5)/2 \rfloor = 7$, whence my choosing the numbers with sum of exponents $7$.
15.12.2011 19:45
Can you tell me more about "de Bruijn-Tengbergen-Kruyswijk theorem" ? I don't understand it!
15.12.2011 21:55
Other helpful keywords: Sperner's Theorem, Dilworth's Theorem. A family of results on the width of certain partially ordered sets.
02.01.2016 07:38
Anyone find a proof of de Bruijn-Tengbergen-Kruyswijk theorem for the general case? Anyway, the following works when $k \le 3$: http://artofproblemsolving.com/community/c176562h1180054_romanian_tst_1997_de_bruijntengbergenkruyswijk_theorem
18.02.2018 21:48
Who can explain me, clearly, in detail, how to solve this problem, please?
29.06.2020 17:40
redacted