Finding combinations of 81 discrete values that add up to a known value

Question

First, I'm a mechanical engineer, and not a programmer. So for practical purposes, the answer may be as simple as "Excel can't do that without VB", or even "Excel can't do that". This is just a thought experiment for me, but I've run out of brainpower. Anyone that wants to solve this for me will get a heartfelt "NEAT!" which, I think we can agree, is pretty much the pinnacle of engineering accolades...

I watched a video that showed a set of gauge blocks of various sizes, from .0500 to 4.0000" thick, 81 unique blocks in total. The author made reference to the large number of combinations that could be made with such a set. That got me wondering if I could use Excel to figure out all the combinations (and sums) of the set of 81 blocks.

To bound the problem, the sum of all the blocks added together is 26.5295", so that's the maximum, and the minimum increment is 0.0001", so that's 265,295 possible options for sums. I quickly calculated the number of combinations of 81 blocks, C(81,r) where r is 0 thru 81. There are 81 combos of 1 block, 1 combo of 81 blocks, and in between, there are 2.1E23 combos of 41 blocks. All told, there are 2.42E24 combinations of blocks, and thus 2.4 septillion sums (admittedly there will be a lot of repeated sums). I think this rules out Excel...

Alternatively, if you start with each of the 265295 possible sums, someone with the programming knack might be able to work the other way. I can picture this workflow in my mind, but I don't have the chops to program it. For some value, say 3.9762 (copied from video), you start by subtracting the correct 1/10000 block, in this case 0.1002. That leaves 3.8760. Subtract the correct 1/1000 block, here there could be multiple solutions, I would use the smallest appropriate block 0.1060. That leaves 3.7700. Next I'd use 0.1200 to get to 3.6500. Then 0.6500 to get 3.0000. Finally, 3.0000 to get to 0.0000 remaining.

The 0.000X space is either 0, or it requires 0.1001 to 0.1009 blocks. The X.0000 space for X<10 can be dealt with by 1, 2, 3, 4 blocks. Beyond X=10, some wacky combo of smaller 0.0500" increment blocks is required.

If anyone is interested in the specific values of the blocks, they are:

• 4 blocks 1.000 to 4.000 in 1.0000 increments
• 19 blocks 0.0500 to 0.9500 in 0.0500 increments
• 49 blocks from 0.1010 to 0.1490 to 0.0010 increments
• 9 blocks from 0.1001 to 0.1009 in 0.0001 increments

Sauce, for those interested: Video: Origins of Precision, Relevant discussion around 26:34

Answer 1

You have 81 blocks and you either include or exclude each one. (This results in the possibility of a sum of $0$ but it seems you do not want to count this one, so there are $2^{81}-1$ possibilities in total).

So you can just use a recursion, where if $b_n$ is the $n$th and the counts of possibilities adding up to $x$ after $n$ blocks is $f_n(x)$, then $$f_n(x)=f_{n-1}(x)+f_{n-1}(x-b_n)$$ starting with nothing, i.e. $f_0(0)=1$ and $f_0(x)=0$ for $x \not=0$.

This is easier enough to program and runs quickly. The following is in R, including a plot of frequencies. You could use Excel. Note:

• R starts counting at $1$ not $0$
• There is an offset to enable adding $f_{n-1}(x-b_n)$ for negative $x-b_n$ but that offset and the value corresponding to $0$ are dropped at the end from the results
• It is is easier and sensible to work in integers, and avoids some potential rounding errors, so all your lengths are multiplied by $10000$
• The plot appears to show two lines: the higher line is for lengths which are a multiple of $5$ thanks to a very small bias introduced by the interaction of your last nine blocks.

.

blocks <- c(seq(from=10000, to=40000, by=10000),
            seq(from=  500, to= 9500, by=  500),
            seq(from= 1010, to= 1490, by=   10),
            seq(from= 1001, to= 1009, by=    1))
sumblocks <- sum(blocks)
zerooffset <- max(blocks) + 1
counts <- numeric(sumblocks+zerooffset) 
counts[zerooffset] <- 1
for (n in 1:length(blocks)){
    counts[(blocks[n]+1):(sumblocks+zerooffset)] <- 
      counts[(blocks[n]+1):(sumblocks+zerooffset)] + 
      counts[1:(sumblocks+zerooffset-blocks[n])]
    }
results <- counts[(zerooffset+1):(sumblocks+zerooffset)]
sum(results)
# 2.417852e+24
plot(results, pch = ".")