Browse · MathNet
PrintArgentina_2018
Argentina 2018 counting and probability
Problem
A set of natural numbers is regular if each of the subsets has sum different from . Partition the numbers , , , into a minimum number of regular sets.
Solution
Such a partition clearly needs at least regular sets (e.g., and must be in different regular sets). Here is a partition with regular sets:
Let us check that and are indeed regular. Suppose on the contrary that one of them has a subset with sum . Note that has at most elements as the sum of the smallest numbers among , , , is . Let have exactly elements with . If then , which is impossible. Hence and clearly one of is in . In addition one of them is in because the three largest numbers in have sum less than . If, e.g., then ; in particular . However then , a contradiction.
Let have exactly elements with and ; then , . It follows that if then . On the other hand , so that . Similarly if then . Because , this yields . In both cases we reach a contradiction.
Because has more than element, the conclusion is that and are both regular.
Let us check that and are indeed regular. Suppose on the contrary that one of them has a subset with sum . Note that has at most elements as the sum of the smallest numbers among , , , is . Let have exactly elements with . If then , which is impossible. Hence and clearly one of is in . In addition one of them is in because the three largest numbers in have sum less than . If, e.g., then ; in particular . However then , a contradiction.
Let have exactly elements with and ; then , . It follows that if then . On the other hand , so that . Similarly if then . Because , this yields . In both cases we reach a contradiction.
Because has more than element, the conclusion is that and are both regular.
Final answer
2
Techniques
Coloring schemes, extremal argumentsLinear and quadratic inequalities