3
$\begingroup$

I've already asked this question before, but then I realized that wording was, unfortunately, quite confusing.

The statement of the problem is following:

Let $S(A)$ represent the sum of elements in set A of size n. We shall call it a special sum set if for any two non-empty disjoint subsets, $B$ and $C$, the following properties are true:

$1.$ $S(B) ≠ S(C$); that is, sums of subsets cannot be equal.

$2.$ If B contains more elements than $C$ then $S(B) > S(C)$.

For this problem we shall assume that a given set contains n strictly increasing elements and it already satisfies the second rule.

Surprisingly, out of the 25 possible subset pairs that can be obtained from a set for which $n = 4$, only 1 of these pairs need to be tested for equality (first rule). Similarly, when $n = 7$, only 70 out of the $966$ subset pairs need to be tested.

For $n = 12$, how many of the $261625$ subset pairs that can be obtained need to be tested for equality?

Problem statement specifies that, if size of subset $B$ doesn't equal to the size of the subset $C$, then theirs sums will not be equal by default. So when testing set $A$ for the equality, we only consider subsets with the same size.

The main question is, for arbitrary set $A$ with size $n$ which satisfies conditions specified in the problem, how many pairs of subsets with the same size are needed to be tested? I couldn't have come up with purely mathematical solution myself, so I checked answers provided by the users in the discussion thread. A lot of them mentioned so called "grid method", for example, one of the posts:

First, some observations. If elements of the set are assigned in ascending order to subset $B$, subset $C$, or discarded, and every element of $B$ can be paired with an element of $C$ that was selected later, then B's sum will be smaller than $C$'s, and the comparison will not be necessary.

If you imagine a walk on a grid from upper left to lower right, where selecting an element for subset $B$ is like walking East, and selecting an element for subset $C$ is like walking South, and selecting an element for neither subset is effectively the same as selecting it for both (East, then South), then a walk that crosses the diagonal from north to south (with this direction being the first diagonal crossing) corresponds exactly to a subset pair that must be compared.

And one more

Clearly we only need to test equal size groups $(k)$. If we select $2k$ elements, we only need to test some partition of that into $2k$-size groups if there is an $m$-smallest number in the group with the smallest element that is bigger than the $m$-smallest number in the other group. This can be modeled as a path across a $k×k$ grid that crosses the diagonal, so we can use Catalan numbers $C_k$ (which count paths that don't cross the diagonal) and half the total number of paths across the grid to get the number of diagonal-crossing paths (half = given start direction).Then the selection of the initial $2k$ set is a binomial coefficient, and sum across values of $k$.

Can some explain what is this "grid" they are referring to? And how do you solve the problem using this method?

$\endgroup$
1
  • $\begingroup$ It is an interesting combinatorial problem if I understand it correctly, which is expected if it comes from Project Euler. However it think the Question's presentation needs improvement (which might help your own progress on the problem). The gist seems to be, given weights on set elements that satisfy Rule 2, how many comparisons of subset pairs' sums are needed to check if Rule 1 also holds. $\endgroup$ – hardmath Jun 9 '19 at 13:44
4
$\begingroup$

A grid is just this regular pattern of horizontal and vertical lines:

enter image description here

In red, this image also shows one of those paths: It consists of $9$ steps, hence is about $n=9$. It has $3$ east and $3$ south steps, so $|B|=|C|=3$ (where $|B|=|C|$ is equivalent to the path ending on the dotted diagonal; and as the path is not purely on the diagonal, $B,C$ are non-empty). The first step away form the diagonal is east, meaning that $B$ contains the smallest used element - we can assume this by symmetry. But at some point, the path goes below the diagonal - if this were not the case, the path would correspond to a case where trivially $S(B)<S(C)$. (For reference, the path depicts $B=\{a_2,a_7,a_9\}\, C=\{a_3,a_5,a_6\}$).


Maybe put it in a different form: Consider all strings of length $n$ that can be formed from "(", ")", and "-" such that at least one "(" and at least one ")" occur. This can encode the disjoint non-empty subsets $B$ and $C$ of the ordered set $\{a_1,a_2,\ldots, a_n\}$, namely we let $B$ be the set of all $a_i$ where our string has "(" in position $i$, and similarly $C$ for ")". There are $$3^n-2^{n+1} +1$$ such strings (so for $n=4$: $50$ strings; to arrive at the $25$ from the problem statement, we can make use of the symmetry $B$ vs. $C$, which I'll do further down).

To begin with, we need only perform our test for cases with equal number of "(" and ")", for in all other cases condition 2 applies. By symmetry (i.e., because otherwise we can simply swap $B$ and $C$), we may assume without loss of generality that the first bracket of our string is an opening bracket. By these conditions, we would have to test $$\tag1 \frac12\sum_{k=1}^{\lfloor n/2\rfloor}{n\choose 2k}{2k\choose k}=\frac12\sum_{k=1}^{\lfloor n/2\rfloor}{n\choose k}{n-k\choose k}=\frac12\sum_{k=1}^{\lfloor n/2\rfloor}\frac{n!}{(n-2k)!\,k!^2}$$ cases (so for $n=4$: $9$ strings).

Also, whenever the brackets are "properly nested" (for $n=4$ this means "(())", "(--)", "(-)-", "()()", "()--", "-(-)", "-()-", "--()"), we need not perform a test - because we can pair of each "(" with the corresponding ")" and thereby pair off all elements of $B$ with elements of $C$ such that the former are smaller than the latter each time and hence trivially $S(B)<S(C)$. How many tests do we get rid of this way? If it were note for the "-", this would be counted by the Catalan numbers $C_k=\frac1{k+1}{2k\choose k}$. Due to the interspersed "-"'s we remove $$\tag2\sum_{k=1}^{\lfloor n/2\rfloor}{n\choose 2k}C_k =\sum_{k=1}^{\lfloor n/2\rfloor}\frac1{k+1}{n\choose 2k}{2k\choose k}=\sum_{k=1}^{\lfloor n/2\rfloor}\frac{n!}{(n-2k)!\,(k+1)!\,k!}$$ tests instead. By subtracting $(2)$ from $(1)$, we are left with $$\tag3\sum_{k=1}^{\lfloor n/2\rfloor}\frac{(k-1)\,n!}{2\,(n-2k)!\,k!\,(k+1)!}.$$

However - can be be sure that no further reduction of tests is possible? Yes, we can. Given an string of "(", ")", "-" as above, let $k_1>1$ be the position of the first ")" not matching a previous "(", and $k_2$ the position of a later "(". Set $a_1=1$, and then recursively $a_k=a_{k-1}+\alpha_k$ where $\alpha_k$ is an irrational number $\Bbb Q$-linearly independent of all previous $\alpha_i$ and such that $0<\alpha_k<\frac1{n^2}$ -except that for $x=k_1$ and for $k=k_2$ we set $a_k=a_{k-1}+X_1$ and $a_k=a_{k-1}+X_2$, respectively. The condition that $S(B)=S(C)$ then becomes an equation of the form $$\tag4X_1+c_1=X_2+c_2$$ where $0\le c_1,c_2<\frac1n$. It is possible to find solutions to $(4)$ with $0<X_1,X_2<\frac1n$. We still have enough leeway to make the smaller of the two variables irrational and $\Bbb Q$-linearly independent from all $\alpha_i$ previously chosen. Then $(4)$ (i.e., the application of our test to $a_1,\ldots, a_n$) is up to rational multiples the only valid equation with rational coefficients among the $a_i$. Therefore no other test will result in equality. Hence condition 1 holds for all choices of $B,C$ except the one choice corresponding to our test (or its negative, i.e., swapping $B$ and $C$). Moreover, as all $a_i$ are between $1$ and $1+\frac 1n$, it follows that $\lfloor S(X)\rfloor = |X|$ for all subsets, hence condition 2 also holds.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.