Autonomous Sets

[archimedes1]

Let be a set of numbers. We'll call autonomous if the number of elements in is itself an element of . For example, the set is autonomous, as is the set , but the set is not. Find, with proof, the number of autonomous subsets of .

[CatalystOfNostalgia]

Click to reveal hidden content

The answer is .

Consider the number of -element autonomous subsets, where . This covers all autonomous subsets, and clearly each autonomous subset falls in exactly one of these categories. must be in this set, then we can choose the other elements arbitrarily in ways (as there are elements left to choose from). Each -element autonomous subset can be constructed in this way, and conversely this construction always gives rise to an -element autonomous subset, so we have a bijection. Thus, there are -element autonomous subsets.

Thus, the total number of autonomous subsets is

,

the first equality following from the Binomial Theorem. This completes the proof.

[archimedes1]

Click to reveal hidden content

We perform casework on the number of elements in each desired subset. For any integer , where , if our desired subset has elements, then it must contain the element . Since the other elements can be arbitrarily chosen from the remaining elements in the original set, we have that there are desirable subsets.

Thus, our answer is .

This suggests that there exists a bijection from the set of autonomous subsets to the set of nonautonomous subsets. Has anyone been able to find one?

[Temperal]

I didn't apply to Mathcamp, but here's a sort-of bijection: Consider all autonomous subsets of length ; we claim that this is the same number of nonautonomous subsets of length because . An actual one-to-one correspondence between the sets I can't think of right now, but there's probably an obvious one that I've overlooked. At first I thought of , where is the autonomous subset, but unfortunately that doesn't work.

[JBL]

Doesn't work, but it's close. Certainly we can pair and . Now if is a set of size , the set is a set of size and contains if and only if does not contain .

(I'm worried that I've made an off-by-one error somewhere.)

[Goldey]

Bijection between autonomous and non-autonomous:

Take any autonomous subset If for some i, then remove from this set. If not, then remove from this set. Either way, this will yield a non autonomous set with elements.

Now, no two different autonomous original sets will generate the same non autonomous sets by this method (i'm lazy and its late, im not going to prove that rigorously, but its true, you can check), so we have that there are at least as many non-autonomous sets as autonomous ones.

Step 2: Take any non-autonomous subset If for some i, then add to this set's elements (as the set is non autonomous, we know is not already an element). If there is no such i, then add in to this set's elements. Either way, we obtain a autonomous set with k terms. Again, no to different non autonomous sets will generate the same autonomous set, so we have a bijection from autonomous to non-autonomous sets. As there are possible subsets of our original set, of these must be autonomous.

Yea, i realize i couldve done this with better notation/more rigorously, but w/e