2016 USAMO Problems/Problem 1
Let be a sequence of mutually distinct nonempty subsets of a set . Any two sets and are disjoint and their union is not the whole set , that is, and , for all . Find the smallest possible number of elements in .
The answer is that .
First, we provide a inductive construction for . Actually, for we will provide a construction for which has elements in a line. (This is sufficient, since we then get for .) The idea is to start with the following construction for : Then inductively, we do the following procedure to move from to : take the chain for elements, delete an element, and make two copies of the chain (which now has even length). Glue the two copies together, joined by in between. Then place the element in alternating positions starting with the first (in particular, this hits ). For example, the first iteration of this construction gives: Now let's check is sufficient. Consider a chain on a set of size . (We need else .) Observe that there are sets of size can only be neighbored by sets of size , of which there are . So there are sets of size . Also, there are sets of size . So the total number of sets in a chain can be at most .
My proof that is basically the same as the one above. Here is another construction for that I like because it works with remainders and it's pretty intuitive. The basic idea is to assign different subsets to different remainders when divided by particular numbers, and then to use the Chinese Remainder Theorem to show that all of the subsets are distinct. The motivation for this comes from the fact that we want and to always be disjoint, so remainders are a great way to systematically make that happen, since and do not have the same remainder modulo any positive integer greater than Anyway, here is the construction:
Let For we will choose which elements of the set belong to based on the remainder of modulo and we will choose which elements of the set belong to based on the remainder of modulo We do this as follows: Finally, we specially define and
It is relatively easy to see that this configuration satisfies all of the desired conditions. We see that so and are disjoint, as are and The remainder configuration above takes care of the rest, so any two consecutive sets are disjoint. Then, by the Chinese Remainder Theorem, no two integers from to have the same combination of residues modulo and modulo so all of the sets are distinct for It is also easy to verify that none of these match or since they all have at most two elements of and at most two elements of whereas and do not satisfy this; hence all of the sets are distinct. Finally, notice that, for any pair of consecutive sets, at least one of them has at most elements, while the other has at most Thus, their union always has at most elements, so for all
All of the conditions are satisfied, so this configuration works. We thus conclude that
|2016 USAMO (Problems • Resources)|
|First Problem||Followed by|
|1 • 2 • 3 • 4 • 5 • 6|
|All USAMO Problems and Solutions|