As difficult as 01 10 11

Computer Science Level 4

$\begin{aligned} && 9 \\ && 1 + 8 \\ && 2 + 7 \\ && 3 + 6 \\ && 4 + 5 \\ && 1 + 2 + 6 \\ && 1 + 3 + 5 \\ && 2 + 3 + 4 \\ \end{aligned}$

Above shows a total of eight number of ways to express the number 9 as the sum of distinct positive integer in ascending order.

What is the total number of ways to express the number 58 as the sum of distinct positive integer in ascending order?

Bonus : Define $f(n)$ as the total number of ways to express the positive integer $n$ as the sum of distinct positive integers in ascending order. Prove that there exist a polynomial of minimum degree $\frac {n(n+1)}2$ such that you can find $f(1), f(2), \ldots, f(n)$ . Construct this polynomial.

The answer is 8808.

3 solutions

Jesse Nieminen
Mar 5, 2016

Simple recursion using Java:

public static int foo(int num, int min) {
        if(min >= num) return 0;
        int sum = 1;
        for (int i = min+1; i <= num - min; i++) {
            sum += foo(num - i, i);
        }
        return sum;
}
public static void main(String[] args) {
        System.out.println(foo(58, 0));
}

Moderator note:

Great! That's a simple recursive way to find the sum. For this problem, it doesn't seem like dynamic programming would help, and we just have to find the value on a case by case basis.

Yay! Thankyouuu

Pi Han Goh - 5 years, 3 months ago

Brock Brown
Jun 3, 2015

Python 2.7:

def children(elements, n):
    if len(elements) == 0:
        for i in xrange(1, n):
            yield (i,)
    else:
        for new in xrange(elements[-1] + 1, n):
            if sum(elements) + new <= n:
                yield elements+(new,)
def goal(elements, n):
    return sum(elements) == n
def ascending_sums(n):
    sums = 1
    start = ()
    frontier = [start]
    while frontier:
        next = []
        for state in frontier:
            for child in children(state, n):
                next.append(child)
                if goal(child, n):
                    sums += 1
        frontier = next[:]
    return sums
print "Answer:", ascending_sums(58)

Algorithm used: Breadth-First Search

Yay! Now solve the bonus question!

Pi Han Goh - 6 years ago

Brock Brown - 6 years ago

I guess this answers some part of the bonus question

Sualeh Asif - 6 years ago

The bonus question (as stated) does not make sense to me. Given any $n$ values, I can always find a polynomial of degree $n-1$ that takes on those values.

Calvin Lin Staff - 5 years, 3 months ago

I guess the problem asks for a polynomial of degree $\frac{n(n+1)}{2}$ ? This is typically harder than a degree $n-1$ polynomial.

Sualeh Asif - 5 years, 3 months ago

@Sualeh Asif – I'm confused by what you mean. $n-1 < \frac{ n (n+1} { 2}$ so it is more restrictive. At the most, I will add $(x-1)(x-2)(x-3) \ldots ( x - \frac{n(n+1)}{2}$ to my polynomial to get the degree to match.

Calvin Lin Staff - 5 years, 3 months ago

@Calvin Lin – Would my bonus question make sense if I remove the words "minimum degree"?

Pi Han Goh - 5 years, 3 months ago

Pranjal Jain
Mar 24, 2016

Here's DP solution for those who wants optimization:

#include <iostream>
using namespace std;
int table[60][60];                      //table[i][j] is number of ways of making sum i using maximum number j
int main(){
    for(int i=1;i<=58;i++){             //Base Case
        table[1][i]=1;
    }
    for(int i=2;i<=58;i++){             //Base Case
        table[i][1]=0;
    }
    for (int i=2;i<=58;i++){
        for (int j=2;j<=58;j++){
            if (i-j<0){
                table[i][j]=table[i][j-1];
                continue;
            }
            if(i==j){
                table[i][j]=table[i][j-1]+1;
                continue;
            }
            table[i][j]=table[i][j-1]+table[i-j][j-1];
        }
    }
    cout<<table[58][58];
    return 0;
}

Pi Han Goh - 5 years, 2 months ago

As difficult as 01 10 11

The answer is 8808.

3 solutions

Moderator note:

0 pending reports