Partitions of 100 into 10 parts having DIFFERENT sizes

[puctw]

How many partitions of 100 into 10 parts are there with all parts having DIFFERENT sizes?

I tried brute force, but ill take to long, and i can't find a Simple way to get it.

I was thinking in summation with (i) ... But i can't reach the answer.

 

[Mr. Bland]

Let's assume that all groups must contain at least 1.

We could say that the "first" permutation is (1, 2, 3, 4, 5, 6, 7, 8, 9, 55), which is constructed by including the smallest remaining group sizes until the last group, which fills in the amount needed to reach 100. From this, we know that no permutation will have a group with a size greater than 55, since that would make it impossible for there to be 9 other distinct groups without exceeding 100.

I'm envisioning a board with 55 holes and 10 pegs, where each hole corresponds to some integer counting up from 1 and each peg represents a group size in the thought experiment. The numerical values of all pegs must sum to exactly 100. Any time a peg moves one space to the right, another peg must move one space to the left to compensate. To eliminate the possibility of duplicate permutations, we'll say that pegs aren't allowed to jump over one another.

The puzzle, then, is identifying all arrangements of these pegs such that they add up to 100 and their respective order never changes.

The "second" permutation would have to be (1, 2, 3, 4, 5, 6, 7, 8, 10, 54), which is produced by beginning with the first permutaiton and moving the ninth and tenth pegs one spot each, which is the only possible change with the smallest possible distance. From here, we have two possible "third" permutations: move the 8 peg to 9, or move the 10 peg to 11. In both situations, the 54 peg moves to 53.

Enumerating all of the permutations will involve solidifying the behaviors of peg movement that emerge from the given constraints. I don't have the answer presently, but this intuitively seems like the kind of thing that will ultimately be boiled down to a single equation.

I feel like there's a Mothologer video in here waiting to be made...

 

[Mr. Bland]

I have made a computer program to crunch the numbers, as is my civic duty. It brute forces the possible "peg" configurations, moving pegs from the right, to the right where possible, stopping at 55 and considering pegs to the left as a last resort. The task is distributed across however many logical processors the computer happens to have. Once complete, it offers to save all of the matching permutations as a CSV file.

This forum system will not allow me to attach .html or .zip files, so I cannot directly share the software, nor can I attach the .csv containing all of the matches. If there's interest for these files I can host them somewhere myself.

The beast of a machine my employer provided at my workplace has 12 cores, which complete the task in about 5 minutes. In total, the software checks 29,248,649,441 total permutations and finds that 33,401 of them sum to 100. So at least as far as the original question goes, that's the answer (provided I didn't make any mistakes along the way).

 

[Cubist]

I obtain the same result as @Mr. Bland 33,401

Here's my code. I designed it to run fast therefore OP might struggle to understand it. There's no loops for the last two numbers, I use mathematics for speed...

Spoiler: show c++ code

#include <iostream>
using namespace std;

int main() {
  int tot=0;
  // Each successive variable must be greater than the last to eliminate duplicates...
  for (int a=1;a<=5;++a){ // sum(n,0,9,n+5) <= 100
    for (int b=a+1;b<=7;++b){ // 1+sum(n,0,8,n+7) <= 100
      for (int c=b+1;c<=8;++c){ // 1+2+sum(n,0,7,n+8) <= 100
        for (int d=c+1;d<=10;++d){ // 1+2+3+sum(n,0,6,n+10) <= 100
          for (int e=d+1;e<=12;++e){ // 1+2+3+4+sum(n,0,5,n+12) <= 100
            for (int f=e+1;f<=15;++f){ // 1+2+3+4+5+sum(n,0,4,n+15) <= 100
              for (int g=f+1;g<=18;++g){ // 1+2+3+4+5+6+sum(n,0,3,n+18) <= 100
                for (int h=g+1;h<=23;++h){ // 1+2+3+4+5+6+7+sum(n,0,2,n+23) <= 100
                  int remain=100-(a+b+c+d+e+f+g+h);
                  // How many ways can the last two numbers sum to "remain"
                  int i;
                  if ((remain & 1)==1) { // remain is odd, i + (i+1) = remain
                    i=(remain - 1)/2;
                  }
                  else { // remain is even, i + (i+2) = remain
                    i=(remain - 2)/2;
                  }
                  i -= h;
                  if (i>0) tot+=i;
                }
              }
            }
          }
        }
      }
    }
  }
  cout << tot << endl;
  return 0;
}

 

[Cubist]

Here's a much nicer solution that uses recursion. It can be used to calculate other cases, for example the ways to partition 80 into 11 parts, each of different size, is 131. (I prefer to think of this as the number of ways to have 11 different numbers that sum to 80).

Spoiler: show code

#include <iostream>
using namespace std;

int getWays(int minGroupSize, int remainingGroups, int requiredTotal) {
  if (remainingGroups == 2) {
    // Special case
    // Calculate the maximum possible size for the first of the two remaining groups
    int max;
    if ((requiredTotal & 1)==1) { // requiredTotal is odd, max + (max+1) = requiredTotal
      max = (requiredTotal - 1)/2;
    }
    else { // requiredTotal is even, max + (max+2) = requiredTotal
      max = (requiredTotal - 2)/2;
    }
    int ways = max - minGroupSize + 1;
    return (ways>0) ? ways : 0;
  }
  else {
    // Calculate the maximum possible size for this group, "max"
    // We require...
    //  sum(n, 0, remainingGroups - 1, max + n) <= requiredTotal
    //  sum(n, 0, remainingGroups - 1, max) + sum(n, 0, remainingGroups - 1, n) <= requiredTotal
    //  remainingGroups*max + sum(n, 0, remainingGroups - 1, n) <= requiredTotal
    //  remainingGroups*max + remainingGroups*(remainingGroups - 1)/2 <= requiredTotal
    //  remainingGroups*(2*max + remainingGroups - 1)/2 <= requiredTotal
    //  2*max + remainingGroups - 1 <= requiredTotal*2/remainingGroups
    //  2*max <= requiredTotal*2/remainingGroups - remainingGroups + 1
    int max = (requiredTotal*2/remainingGroups - remainingGroups + 1)/2;
    int ways = 0;
    for (int i = minGroupSize; i <= max; ++i) {
      ways += getWays(i + 1, remainingGroups - 1, requiredTotal - i);
    }
    return ways;
  }
}

/////////////////////////////////////////////////////////////

int main() {
  cout << getWays(1, 10, 100) << endl; // the ways to partition 100 into 10 parts
  cout << getWays(1, 11, 80) << endl; // the ways to partition 80 into 11 parts
  return 0;
}

 

[Mr. Bland]

Looking good! I love when people revisit something that already works in an effort to make it better/more general.

Programming challenge: Think you can adjust that to do it with a buffer instead of recursion?

Extra credit: What is the benefit of doing something with a buffer instead of recursion?

 

[Cubist]

Extra credit: What is the benefit of doing something with a buffer instead of recursion?

Are you thinking of threading, to take advantage of extra CPU cores?

--

I've thought of a reduction formula. Imagine the pegboard of post#2. Each hole has a place-value. Let's say we have the goal of summing 5 pegs to 18. If we put two pegs in the leftmost holes...

  1 2 3 4 5 6 7 8
  P P . . . . . .

...there would be 3 pegs left that need to be placed on the remaining "."

Now suppose that we have a function f(h,p,t) that returns the number of ways that the remaining pegs can be placed

h = next hole's place-value
p = remaining pegs
t = remaining total

There are only two possibilities for hole 3. We either put a peg, or we leave it empty. Therefore...

  1 2 3 4 5 6 7 8
  P P . . . . . .  the number of ways to place 3 pegs on the remaining "."
                   = f(3, 3, 18-(1+2))
                   = f(3, 3, 15)

THE ABOVE IS EQUAL TO THE SUM OF THE FOLLOWING TWO AMOUNTS

  1 2 3 4 5 6 7 8
  P P P . . . . .  the number of ways to place 2 "X" pegs on the remaining "."
                   = f(4, 2, 15-3)

PLUS

  1 2 3 4 5 6 7 8
  P P O . . . . .  the number of ways to place 3 "X" pegs on the remaining "."
                   = f(4, 3, 15)

"O" means that there's no peg in that position

Therefore the reduction formula is f(h,p,t) = f(h+1, p-1, t-h) + f(h+1, p, t)

Obviously f() would need to return trivial answers directly (thus ending the recursion). Let m be the sum if the remaining pegs are placed leftmost

[math]m=\sum_{n=0}^{p-1}\left(h+n\right) = \frac{p(2h + p - 1)}{2} [/math]
These trivial solutions follow:-
f(h,p,t) = 1 IF t=m
f(h,p,t) = 0 IF t<m
f(h,p,t) = 1 IF t>m AND p=1

This leads to much faster code for the case when the total is large...

Spoiler: show code

The attached code caches the results to prevent re-calculation since multiple calls occur with the same parameters. To calculate f(1, 10, 400) takes 0.04s compared to 54.31s using the post#5 method (I had to change the post#5 code to use "long long" instead of "int", in some places, to obtain the correct answer since it's too large to fit into an "int" on my system)

#include <iostream>
#include <map>
using namespace std;

map<int, map<int, map<int, long long> > > cache;

long long getWays(int h, int p, int t) {
  int minSum=p*(2*h+p-1)/2;
  if (t==minSum) return 1;
  if (t<minSum) return 0;
  if (p==1) return 1;

  // Check the cache
  auto& i=cache[h][p];
  auto j=i.find(t);
  if (j != i.end()) return j->second;

  // use reduction formula
  long long ways = getWays(h+1, p-1, t-h)  +  getWays(h+1, p, t);
  
  // Insert into cache
  i[t] = ways;
  return ways;
}

/////////////////////////////////////////////////////////////

int main() {
  cout << getWays(1, 10, 100) << endl; // the ways to partition 100 into 10 parts
  cout << getWays(1, 10, 400) << endl;
  return 0;
}

 

[Mr. Bland]

Whoops, forgot to check in on this. A buffer is generally preferred over recursion because of how the memory is allocated: for a buffer, the memory is located on the heap, whereas for recursion it is located in the stack. For large sets of items, recursion can quickly exhaust the available stack space (stack overflow), whereas a buffer can be much larger in size.

 

[Cubist]

...recursion can quickly exhaust the available stack space (stack overflow), whereas a buffer can be much larger in size.

Yes that's certainly a potential problem with recursion. But on the plus side recursion usually results in code that is easier to understand (and is therefore easier to maintain). Swings and roundabouts. I'll leave the job of converting my solution to use the heap for someone else to do (I somehow doubt that anyone will ever find a practical use for this particular algorithm anyhow, but who knows!). Something should also be done about the global variable used for a cache if this ever gets deployed within a proper application.

This question reminds me of kakuro (click) puzzles, before any numbers are placed in the grid you'd look for a line where there's a single way of inserting (different) digits to a given total.