# Given n ranging from 1 to 100, find sum of digits equal to half of arithmetic sum of 1 to 100

I have a number sequence from 1 to 100. Given 2 bins, the numbers are randomly assigned to each bin.

I know the total sum from 1 to 100 is 5050. Thus, for both bins to have the same sum, each bin must sum up to 2525. All the 100 numbers must belong to either bin.

I know there are a total of 2^100 possible combinations. How do I find the number of combinations that sum to 2525 in each bin?

Thank you.

EDIT: Just to clarify, a bin is just a collection of numbers. So essentially, I have collection A and collection B. The sum in each collection must be equal and all 100 numbers must belong to either collection. Think of them as buckets or whatever is convenient for explanation.

-
@lone. If you can develop a program, the recursion $f(n,S) = f(n-1,S)+f(n-1,S-n)$ will do it – Sylvain Biehler Mar 17 '14 at 9:38
@lone: Regarding Bilou06's recursion: For this problem, dynamic programming (or memoization) is absolutely essential, or else you'll end up repeating a lot of work and likely take years to finish computing (if you don't run out of stack space earlier). Basically, instead of writing a recursive function, you should create a 2D array, fill in some initial entries, and loop through the entries. – Tony Mar 17 '14 at 9:58
Note: Spreadsheets can be used for double-recursion – Mark Bennet Mar 17 '14 at 10:05
To fill the array, you may use properties such as $n \geq s\implies f(n,s)=f(s,s)$ – Sylvain Biehler Mar 17 '14 at 10:12
You're right, $2^{100}$ is completely beyond any computer's ability to process in a reasonable amount of time. However, you're not actually going through all of them. This is the beauty of algorithms. – Tony Mar 17 '14 at 10:23

Using the recursion (thanks Bilou06)

$$f(n, S) = f(n - 1, S) + f(n - 1, S - n),$$

we have the following Python code:

n = 100
S = 2525

matrix = [[0]*(S+1) for x in range(0, n+1)]

for S in range(0, S+1):
matrix[0][S] = 0
for n in range(0, n+1):
matrix[n][0] = 1
for n in range(1, n+1):
for S in range(S+1):
matrix[n][S] = matrix[n-1][S] + matrix[n-1][S-n]

print matrix[n][S]


You can change the values of n and S when running the code to verify they work for smaller cases.

-
$1731024005948725016633786324$ is a very good answer. Next question: any idea what this is? I mean, a proper value in terms of binomial coefficients/power? – Sabyasachi Mar 17 '14 at 10:44
The prime factorization is $2^2 \times 61 \times 1044041 \times 6795097778839840081$. Not sure what this means though. – Tony Mar 17 '14 at 10:48
I'm also curious to know what the number means. I know if i test with n=4 and S=5, i get 2, which is correct since there are only 2 combinations that sum to 5. What other meanings can the answer have? – lone Mar 17 '14 at 10:57
I have a question regarding the values obtained at the final row. At each step, the calculation considers S ways to choose n-1 and S-n ways to choose n-1. What is the significance of the result obtained in the last row? if a n of 3 is used, my last row is [2, 2, 2, 2]. – lone Mar 18 '14 at 15:18

i converted the code to c code. however, my code would just hang.

i tried this with a smaller value of n =15. but my c code produces 5505 instead of the 722 this python code produced.

#include <stdio.h>
#include <string.h>
#include <math.h>  main()
{
int n=100;
double k=2;
int min=2525;
int rec[100][2525]; //100 row, 2525 column
int x,y,r,c,str;
int po = (int) pow((double) k,n); //2^100

for (r=0;r<n+1;r++) {
for(c=0;c<min+1;c++)
{
rec[r][c]=0;
} } for (x=0;x<n+1;x++) {
rec[x][0]=1; }

for (y=0;y<min+1;y++) {
rec[0][y]=0; }

for (r=1;r<n+1;r++) {
for(c=0;c<min+1;c++)
{
rec[r][c]=rec[r-1][c]+rec[r-1][c-r];
} }

printf("%d, %d, %d\n",rec[100][2525],r,c); printf("%d", po ); scanf ("%d",str); }

-
If you expect someone to help you with your code, you could pay attention to make it as readable as possible. What is tt? Besides, rec[0][0] should be 1, as in he python code – Sylvain Biehler Mar 19 '14 at 8:27
rec[100][2525] is not a valid statement. If you define "int x[123]" the maximal element you can access is "x[122]". – Listing Apr 7 '14 at 18:50