I encountered a clean mathematical problem in my research. It seemed simple, but turned out to be very finicky problem in my research. I just solved it, with Katherine’s invaluable help, and I thought I’d post it here for others to see.

Let a divisor multiset S of size n be a multiset of positive integers such that |S| = n, and such that for all elements s in S, s divides n.

For instance, if n=6, then S=[1,1,1,2,2,3] is a divisor multiset.

Let a perfect subset S’ of a divisor multiset S with |S|=n be a subset of S such that the sum of the elements of S’ is exactly n.

For instance, S=[1,1,1,2,2,3] has three perfect subsets: [1,1,1,3], [1,1,2,2], [1,2,3].

The theorem we want to prove is that all divisor multisets have a perfect subset.

We proved this using strong induction on n, and by splitting into three cases:

  • There are at least n/6 1s in S.

  • n is of the form 2^i 3^j, and there are less than n/6 1s in S.

  • n is divisible by some prime k >= 5, and there are less than n/6 1s in S.

At least n/6 1s

In the first case, we proceed by placing the elements of S into S’ in order from largest to smallest, until one would go over n. At this point, we fill in the remaining space with 1s. This always works if there are at least n/6 1s in S.

For instance, with S=[1,1,1,2,2,3], this results in the perfect subset S’=[3,2,1].

n = 2^i 3^j

In the second case, either S has n/2 even elements, or S has n/3 odd elements greater than 1, all of which must be divisible by 3.

In either case, we divide the appropriate subset by its known prime factor, apply the inductive hypothesis, and turn it back into a perfect subset of S.

For instance, with n=12 and S=[1,2,2,2,2,2,3,3,3,4,4,6], there are 8 even elements of S, so we can take the subset [2,2,2,2,2,4], divide all of the elements by 2 to get the size-6 divisor multiset [1,1,1,1,1,2], apply the inductive hypothesis to get the sum-6 perfect subset [1,1,1,1,2], and turn it back into [2,2,2,2,4], a sum-12 perfect subset of S.

n has a prime factor k >= 5

In the third case, we split up S into multiples of k, 1s, and others. If there are at least n/k multiples of k, we apply the inductive hypothesis just as in the second case. Otherwise, there are lots of divisors of n which are not multiples of k and not 1. These must be divisors of n/k with value at least 2. As a result, we can use the inductive hypothesis to extract perfect subsets of sum n/k. Each such subset only contains at most n/2k elements, because we’re building them out of integers that are at least 2. In fact, we can extract k such disjoint subsets of sum n/k. Combining them gives our perfect subset.

For instance, with n=20 and S=[1,1,1,2,2,2,2,2,2,2,2,2,4,4,4,4,4,4,4,4,5,5,5], we form 5 disjoint subsets of sum 4: [2,2], [2,2], [2,2], [2,2], [4]. This forms a perfect subset: [2,2,2,2,2,2,2,2,4].

Bigger example

Consider the divisor multiset with n=60, and S=[1x1, 29x2, 19x3, 11x5]. Here the number before the “x” indicates the multiplicity, to make things more concise.

This divisor multiset is notable for not containing a perfect subset in which all elements are factors of all larger elements, which is one of the simplest kinds of perfect subsets. I believe it is the smallest such divisor multiset, but I am not sure.

Applying our construction, we start in case 3, due to the presence of the prime factor k=5. We then take the elements which are not multiples of 5 and are not 1, and start forming divisor multisets of size n/k=12.

We extract 5 perfect subsets with sum 12: [6x2], [6x2], [6x2], [6x2], [4x3]. These combine to form the desired perfect subset.

Full proof

The full proof is here: Perfect Subsets.

Note that this is a much cleaner proof than the initial one I created.