The Doodle Problem

I came across the following problem on this site:

Can you make 100 by interspersing any number of pluses and minuses within the string of digits 9 8 7 6 5 4 3 2 1? You can't change the order of the digits! So what's the least number of pluses and minuses needed to make 100?

The originator of the problem called it a "doodle problem" because he felt it was "one that's best worked on during meetings where you might be doodling otherwise". It's easy enough to come up with a solution but not necessarily one that involves the least number of pluses and minuses. My solution was 9-8+76-5+4+3+21.

Referring to the originator's solution (link), he began:

A lot of trial and error is needed, and, although there are ways to help limit the set of possibilities, there isn’t a surefire method of arriving at a solution in a reasonable amount of time with a pen and paper. 

To start with, we might notice the first two digits make the number 98, which is quite close to 100. So, if we can add and subtract the rest of the single digits to make 2, then we’ll have 100. In fact, there are eight ways to do this: 

98 + 7 + 6 - 5 - 4 - 3 + 2 - 1 

98 + 7 - 6 + 5 - 4 + 3 - 2 - 1 

98 + 7 - 6 + 5 - 4 - 3 + 2 + 1 

98 + 7 - 6 - 5 + 4 + 3 - 2 + 1 

98 - 7 + 6 + 5 + 4 - 3 - 2 - 1 

98 - 7 + 6 + 5 - 4 + 3 - 2 + 1 

98 - 7 + 6 - 5 + 4 + 3 + 2 - 1 

98 - 7 - 6 + 5 + 4 + 3 + 2 + 1 

But we can do better—we can make 100 with fewer than 7 pluses and minuses. 

Here’s one way to make sure we find all possibilities: use a computer simulation. Each pair of digits can be connected by either nothing, a plus sign, or a minus sign. Since there are eight paired connections, there are \(3^8 = 6,561\) possible combinations of pluses and minuses. I simulated each one of these combinations to determine which sum to 100.

So at least my solution involved only six pluses and minuses but this may still not be the least number possible. I was intrigued at the prospect of a computer simulation using SageMathCell to find all possible solutions along with those that contained the minimum number possible. However, I haven't been able to figure out how to do this. I'll keep trying.

The originator succeeded with his computer simulation however, and came up with the following results:

The simulation unearthed that there are seven other ways of making 100: 

98 - 7 - 6 - 5 - 4 + 3 + 21 

9 + 8 + 76 + 5 + 4 - 3 + 2 - 1 

9 + 8 + 76 + 5 - 4 + 3 + 2 + 1 

9 - 8 + 76 + 54 - 32 + 1 

9 - 8 + 76 - 5 + 4 + 3 + 21 

9 - 8 + 7 + 65 - 4 + 32 - 1 

98 - 76 + 54 + 3 + 21 

The bolded solution is the winner. It uses only four pluses and minuses! 

The computer simulation also revealed that it’s possible to make every number from 1 to 100, which could keep you doodling for many meetings. In fact, it’s possible to make every number in more ways than one with one notable exception: 9 + 87 - 65 + 4 - 32 - 1 is the unique way to make 2.

This interesting little problem is similar to the selfie numbers that I posted about recently. The difference is that more operations than just addition and subtraction can be used in creating selfie numbers and the goal with them is always to recreate the original number. Here is a link to that post.