BMO 2011, problem 3 immediately corollary to dilworth theorem see http://web.mit.edu/yufeiz/www/olympiad/algcomb.pdf (page 3)

paul1703 wrote: immediately corollary to dilworth theorem I would really like to see the order you may put on S...

you say $x>y$ if $\frac{x}{y}=p^k$ by extremal argument(maximal) any god subset is a chain. i didn't even try this problem during the contest because i didn't do 1

Let $p_1,p_2,\ldots,p_s$ be all the primes dividing any element of $S$. Then an element $x$ of $S$ can be written as $x=\prod_{i=1}^s p_i^{x_i}$, with $0 \leq x_i \leq \alpha_i$ (where $\alpha_i$ is the largest exponent of the prime $p_i$ over all elements of $S$). In fact, we will identify $x$ with the $s$-tuplet $(x_1,x_2,\ldots,x_s)$. Defining a relation $y \prec x$ by having all $y_i = x_i$, with the exception of one index $j$ for which $y_j \leq x_j$, does not work, since transitivity is not ensured (for example, $(0,0) \prec (0,1) \prec (1,1)$, but $(0,0) \not \prec (1,1)$), and so the relation is not a partial order. Thus the above does not allow the use of Dilworth's theorem. An easy analysis of the structure of a good set shows that, for any index $j$ for which $\alpha_j = \max_{1\leq i\leq s} \alpha_i = \alpha$, it could only be of the form $\{(x_1,\ldots,x_j,\ldots,x_s) \mid x_j = 0,1,\ldots,\alpha\}$, thus the largest size is $k=\alpha+1$. Now, we may define $y \prec x$ by having all $y_i = x_i$, with the exception of one index $j$ for which $y_j \leq x_j$, and also $\left \lfloor \dfrac {1} {k} \sum_{i=1}^s y_i \right \rfloor = \left \lfloor \dfrac {1} {k} \sum_{i=1}^s x_i \right \rfloor$. This is a partial order relation, with largest chain of size $k$ (some, but not all, of the good sets are chains under this relation). All antichains are easily seen to be bad sets, so Dilworth's theorem provides the answer - but in fact this is done with the hindsight of knowing what we were looking for, since one cover made by $k$ bad sets $B_0,B_1,\ldots,B_{k-1}$ could be done by choosing $B_r = \left \{ x \mid \sum_{i=1}^s x_i \equiv r \pmod{k}\right \}$, for $0\leq r\leq k-1$, hence no actual need for Dilworth's.

As I didn't understand the previous solution posted, i post my own and please tell me if I am correct. First I defined some properties of a good subset: i) A good subset may have as elements powers of the same prime, including 1. ii) A good subset may have as elements the elements described above all multiplied by a constant. iii) A good subset cannot have as elements powers of different primes. So, let N be the greatest element of $S$. Then all its divisors will be elements of $S$ too. Let $N=p_1^{a_1}p_2^{a_2}p_3^{a_3}...p_n^{a_n}$ Where $p_i$ are primes and $a_i$ positive integers Then the good subset with the greatest number of elements will contain as much elements as the greatest $a_i$ plus one (to also include 1) due to i) and iii) $\Rightarrow k=max(a_i)+1$ Now, when we have to divide $S$ into bad subsets which do not share common elements, we have to separate the powers of every prime divisor of N. So, the powers of the prime in the greatest power at least must be in different subsets. We again find that: least number of bad subsets$=max(a_i)+1=k$ as requested.

1) It is not always true that $k = \max(a_i) + 1$, where $N= p_1^{a_1}p_2^{a_2}\cdots p_n^{a_n}$ is the largest element of $S$. As I said in my previous post, $k$ is one more than the largest exponent of a prime dividing any element of $S$. As an example, take $S$ to be the set containing $M= 2^5, N= 2^4\cdot 3^4\cdot 5^4$, and all their divisors; then $N$ is the largest element in $S$, but $k=1+5 = 6$. 2) All you proved is that the least number of bad subsets into which we can partition $S$ is greater or equal to $k$. One has to actually show that this minimum number is reached (e.g. by building those $k$ bad sets).

mavropnevma wrote: 1) It is not always true that $k = \max(a_i) + 1$, where $N= p_1^{a_1}p_2^{a_2}\cdots p_n^{a_n}$ is the largest element of $S$. As I said in my previous post, $k$ is one more than the largest exponent of a prime dividing any element of $S$. As an example, take $S$ to be the set containing $M= 2^5, N= 2^4\cdot 3^4\cdot 5^4$, and all their divisors; then $N$ is the largest element in $S$, but $k=1+5 = 6$. 2) All you proved is that the least number of bad subsets into which we can partition $S$ is greater or equal to $k$. One has to actually show that this minimum number is reached (e.g. by building those $k$ bad sets). You are so right! I hadn't even noticed that there could be a case like the one you said. However, could you please explain me your solution above, as I'm not familiar with the symbols and terms used? (I also didnt understand exactly your comment number 2) )

My comment number 2) states that you did not prove equality - you just proved that you need at least $k$ bad sets to cover (via a partition) the set $S$. You also need to show that this is possible. As for my proof, just ignore the references to Dilworth's theorem - they are just made in order to incorporate this problem into the poset theory where it belongs. What I've done is to first state the structure of a good set, and compute its maximal size $k$ as being one more than the largest power of a prime dividing some element of $S$, then exhibiting a way to build $k$ disjoint bad sets of union $S$. That is done quite clearly in my post above - maybe you just need to read it more patiently and carefully.

Does anyone know anything about the results? Thank you!

mavropnevma wrote: My comment number 2) states that you did not prove equality - you just proved that you need at least $k$ bad sets to cover (via a partition) the set $S$. You also need to show that this is possible. As for my proof, just ignore the references to Dilworth's theorem - they are just made in order to incorporate this problem into the poset theory where it belongs. What I've done is to first state the structure of a good set, and compute its maximal size $k$ as being one more than the largest power of a prime dividing some element of $S$, then exhibiting a way to build $k$ disjoint bad sets of union $S$. That is done quite clearly in my post above - maybe you just need to read it more patiently and carefully. Thank you! It just was a bit difficult to read the proof and then even more to understand it. I just didn't know what some of your symbols meant. Thank you, again.

paul1703 wrote: you say $x>y$ if $\frac{x}{y}=p^k$ This is not an order, because we don't have transitivity: $pq>p>1$ but not $pq>1$

I strongly believe that there is no "pure" Dilworth solution to this problem, due to the fact that the condition imposed on the set $S$ (for any $a\in S$ and $d|a$ we have $d\in S$ is not contained by the theorem naturally. In mavropnevma's solution, the order relation is based on the fact that we have $k$ as the highest degree of a prime number over all the numbers in $S$, which is actually equivalent to the maximum length of a "chain" because of the condition. During the contest, I thought about Dilworth, but abandoned it in 5 minutes or so due to the fact that it would be really tricky to incorporate the condition in it, and the problem obviously has a more natural, sleek solution.

salazar wrote: Does anyone know anything about the results? Thank you! salazar the offical results can be found in the official page (just google it) and stop asking this in every BMO question.