partitioning a number into two sets based on sum of digits

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.

-
This is not a research level question. Voted to close. – Mark Sapir Feb 12 '11 at 3:50
Are you asking whether you can test this efficiently? For example, only testing a polynomial number of subsets of digits? Obviously one can just enumerate over all possible subsets (and there are cleverer ways to proceed too). – Tony Huynh Feb 12 '11 at 4:13
By simple brute-force method it would take long time to find such numbers among a range. So is there any better solution to it? Maybe by using bit operations? – pranay Feb 12 '11 at 17:53
This question came up on the math-fun mailing list in 2001, and William Thurston outlined a proof that the set of numbers with the property described above can be recognized by a finite state automaton. The sequence is mentioned in the OEIS at oeis.org/A064544. – Dave R Feb 13 '11 at 1:15

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,$$

-
You should be able to tighten the estimate to 43, as there are at most 8 nonzero digits to sum over in S2. Gerhard "Ask Me About System Design" Paseman, 2011.02.12 – Gerhard Paseman Feb 12 '11 at 20:12
You can also use divisibility conditions to improve the estimate for certain numbers. E. G. there are fewer than 36 occurences of 6. Gerhard "Ask Me About System Design" Paseman, 2011.02.12 – Gerhard Paseman Feb 12 '11 at 20:24
Also, arguing modulo i, any appropriately large multiset of i digits has a nonempty (consecutive) subset summing to 0 mod i, so I think one can bring the number of occurrences of i down to 9. I am still glad of your original analysis though. Gerhard "Ask Me About System Design" Paseman, 2011.02.12 – Gerhard Paseman Feb 12 '11 at 20:33
That is a nice short proof of the result I cited. I didn't feel like running through hard estimates on the maximal size of minimal partitions, so I decided just to give a sketch of the proof. Another method of proof I considered talking about was via the theory of minimal covering sets; see for example: M. Lothaire,"Combinatorics on Words" in Encylopedia of mathematics and its applications. Vol, 17, Addison-Wesley, 1983. pp. xix+238, ISBN 0-201-13516-7. MR 84g:05002 From Lothaire's result, one can deduce the finiteness of minimal partitions as a corollary, but this seemed too advanced. – ARupinski Feb 13 '11 at 1:32

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.

-

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".

-
For arbitrarily large bases, yes. For base 10, there is not as much challenge in partitioning a multiset with at most 10 distinct elements. After greedily removing pairs, one reduces the problem to a set of size at most 10. If the sum of this residue set is even, one can try all cases by brute force, adding in a few of the previously removed pairs if needed. Gerhard "Ask Me About System Design" Paseman, 2011.02.11 – Gerhard Paseman Feb 12 '11 at 5:20
I think the problem is harder than that Gerhard. Think about a number like 22228 ;) – Nick S Feb 12 '11 at 6:02
The point is that it can be reduced to a finite number of cases, unlike the general partition problem. The finite cases are subsets of the set of digits, with enough additional pairs to fill in up to the maximal difference needed, which is less than 46. In fact, the maximal difference needed may be less than 10. Gerhard "Ask Me ABout System Design" Paseman, 2011.02.11 – Gerhard Paseman Feb 12 '11 at 6:19
On the other hand, finding a short description of the collection of multisets which admit such a partition may be of interest, leading to subset sums in grops, addition chains, and the like. So there is research level mathematics lurking near the question, even if the original question as asked is not as intractable as your run-of-the-mill NP problem. Gerhard "Ask Me About System Design" Paseman, 2011.02.11 – Gerhard Paseman Feb 12 '11 at 6:23
For example, in base b, I can imagine the following statement being true (but I do not have a proof yet):"Any subset of the digits in base b with even sum and size epsilon*b admits a partition, where epsilon is of the order b^(-1/2)." Gerhard "Ask Me About System Design" Paseman, 2011.02.11 – Gerhard Paseman Feb 12 '11 at 6:29

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)$

-

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.

-
Looking at Igors post, it would seem that with 10 digits chosen at random there is a better than 99.89% chance of a perfect partition (the results there are for base 11 not base 10). For under 10 digits a search (enlightened or even just brute force) is very easy. – Aaron Meyerowitz Feb 13 '11 at 20:17