partitioning a number into two sets based on sum of digits - MathOverflow

partitioning a number into two sets based on sum of digits

2011-02-12T03:27:07Z

hi, how can one determine whether a number belongs to such a set of numbers whose every element can be divided into two sets such that the sum of digits of each set of the number is same. E.g 23450 does belong to such a set , as it can be split into two sets : (3,4,0) and (2,5) such that sum of digits in each set is the same(7). Similary 91125 belongs to such a set: (9) and (1,1,2,5). but 567 , or 34523 do not belong to such a set of numbers .

Thanks.

Answer by Igor Rivin for partitioning a number into two sets based on sum of digits

2011-02-12T04:59:11Z

Actually, this is a research level question, and here is what's known about it:

http://en.wikipedia.org/wiki/Partition_problem

EDIT If you read the wikipedia article, and follow the links, you will see that if the size of the elements is bounded (for example, by $10$) the problem can be solved using dynamic programming in $O(n^2)$ time, where $n$ is the number of "digits".

Answer by ARupinski for partitioning a number into two sets based on sum of digits

2011-02-12T06:25:31Z

Not really a total answer, but as an addendum to Gerhard's comment, because there are only 10 digits which can appear there are several things which make the problem easier.

It's not immediately obvious, but there is a finite set of "minimal" partitions $(S_1,S_2)$ where each $S_i$ is a collection of digits. These minimal partitions have the following properties:

1). $sum(S_1) = sum(S_2)$

2). $sum(T_1) = sum(T_2)$ for $\emptyset\neq T_1\subseteq S_1$ and $\emptyset\neq T_2\subseteq S_2$ implies ($T_1 = S_1$ and $T_2 = S_2$)

Note that the sets $S_1 = S_2$ = $\lbrace d\rbrace$ are minimal by this definition.

Rough Outline of Proof: Condition 2 implies that a given digit $d$ cannot appear in both $S_1$ and $S_2$ and 0 does not appear in either one. Thus $S_1$ contains some digits and $S_2$ contains other digits (except for the single digit pairs noted above), and we can reduce to at most $3^9+10$ cases of which digits appear in $S_1$ and $S_2$ (for each digit, it either goes in $S_1$, in $S_2$, or in neither, plus the 10 single digit pairs).

Now lots of these cases get thrown away right away, for example if 1 and 2 are in $S_1$ and 3 is in $S_2$. Among the ones that remain, there are only finitely many ways to put in more copies of the digits to avoid equal subsums. \ \

Once one has this set of minimal partitions, one can use them as a sort of 'primes' for building up all larger partitions of a set of digits into equal subsums; every partition which has equal sums will have at least one of these minimal partitions as subsets of its digit sets, removing this subset one gets a strictly smaller set to deal with.

Using basic enumeration techniques from combinatorics, one can use them to give an upper bound on how many integers with a given number of digits can have such a partition. It is possible that there are multiple ways of decomposing a partition into these minimal sets, for example let n = 1123333444. Then there are at least two ways to decompose the digits of $n$ into minimal partitions:

$(\lbrace 1,1\rbrace,\lbrace 2\rbrace) \cup (\lbrace 3,3,3,3\rbrace,\lbrace 4,4,4\rbrace)$

$(\lbrace 1,1,4\rbrace,\lbrace 3,3\rbrace) \cup (\lbrace 2,3,3\rbrace,\lbrace 4,4\rbrace)$

Answer by Tony Huynh for partitioning a number into two sets based on sum of digits

2011-02-12T20:05:14Z

This isn't really an answer, but just a short proof that there are indeed a finite number of minimal partitions. See ARupinski's answer for a definition of minimal partition.

Lemma. There are a finite set of minimal partitions.

Proof. Let $(S_1, S_2)$ be a minimal partition. We claim that no digit occurs more than 44 times in either of the multi-sets $S_1$ or $S_2$, from which the lemma clearly follows. Towards a contradiction suppose that some $i \in [9]$ occurs at least 45 times in $S_1$. Then for each digit $j$, we have that $j$ occurs at most $i-1$ times in $S_2$ (because otherwise we could remove $j$ copies of $i$ from $S_1$ and $i$ copies of $j$ from $S_2$). But now

$$\sum S_1 \geq 45i = \sum_{j=1}^{9} ij > \sum S_2,$$

a contradiction.

Answer by Gerhard Paseman for partitioning a number into two sets based on sum of digits

2011-02-13T05:27:00Z

The short answer is : brute force. However, there are sufficient conditions which take on the order of B choose b operations to test, where B is the radix or base of the number system ( 10 in the case of this problem ) and b is a (asymptotic with respect to the growth of B) relatively small number, on the order of sqrt(2B). So there is a good chance at a quick algorithm.

If we have the digits running from 0 to B-1, then there is for every such number a partition which has difference at most B-1 between the sums of the two submultisets. The case of a multiset of odd order is left to the reader, while the case of an even number of elements places two elements in each candidate partition so as to minimize the difference observed so far. Since the difference between the two digits is at most B-1, the difference between the sums of each partially formed partition can be arranged also to be at most B-1.

Now suppose the multiset M contains a set S of distinct digits, such that S is nice, that is S has an even sum and further S can be divided into two sets the difference of whose sums is any even number between 0 and B-1 inclusive. Then partition (M - S) as above to get a difference of less than B, and then use the appropriate partition of S to realize a partition such that the difference between the two resulting sums is at most 1.

We thus have a sufficient condition: if M contains such a nice set S, then it has a partition with difference equal to the sum modulo 2 of M. The nice thing is that a nice S is a set, and it need have about b elements in it to acheive the desired property. There may be nice multisets T of about the same size, but I do not know this.

I further suspect that most subsets of the B digits of size 2b have such a desired set S. I also suspect that these results and similar ones are in the literature, so I shan't write up much more. If someone is interested in finding how many nice subsets S there are for B up to 10 (care to try it A. M.?), I might then venture a better guess as to the size of b. I know {1,2,3,4} and {2,3,4,5} are nice for B = 10.

Gerhard "Ask Me About System Design" Paseman, 2011.02.12

Answer by Aaron Meyerowitz for partitioning a number into two sets based on sum of digits

2011-02-13T05:36:41Z

This shouldn't be too hard; the question is how to do it with relatively few cases. I'm not satisfied that I have that done nicely but I think I have a reasonable method:

Let's assume that the $\gcd$ is 1 (an easy reduction) and eliminate at least the case of an odd number of 9's together with other digits adding to 1,3,5, or 7. (More cases like $9^a3^b1^1$ come to mind but let's skip that). A good start (familiar from bin packing) is to order the digits in decreasing order then put them in two bins always choosing the lowest one. At the end the difference will be 0,2,4,6,or 8? A difference of 8 could only come from $9^a1^1$ or $9^a8^{2b+1}$ (the first impossible the second possible iff $a \ge 8$, I think). Even a difference of 6 could only happen if there is at most one digit 5 or less, but it seems unsatisfying to enumerate all the options for that and unpromising to do that for a difference of 4 or 2. One can see as well that several situations ensure that the initial difference will end up 0 (at least 8 1's, at least 7 1's (since we eliminated $9^{2a+1}1^7$), a 5 and at least 5 1's etc.) However if the difference does not immediately come out to be 0 then we have the task of moving a few things from one bin to the other and vice versa. This is where I think my solution is too lengthy. Say that the difference is $d$. Then we need to look at the small sums which can be made with the digits from each bin (I think maybe up to 72 might be enough and less than that if we eliminate the easily analyzed case of $9^a8^b$) then we just have to see if there is a sums $s+d$ from the large bin matched with a sum $s$ from the small bin. If there are few distinct digits this will be particularly easy. If there are more than a few (for example at least one each of 1,2,3,4) then we can argue that the algorithm would already have arrived at 0 in the first place.

Hmm I see Gerhard just posted something similar.