Brackets math problem

[zoki85]

I saw it in local newspapers:

-1-2-3-4-5-6-7-8-9-10=11

Insert brackets on the left side to make the sum correct.
I solved it like -1-(2-3)-4-(5-6-7-8-9)-10=11 but there are more
possibilities.How many solutions can you find?

 

[davee123]

-1-2-3-4-5-6-7-8-9-10=11

Insert brackets on the left side to make the sum correct.
I solved it like -1-(2-3)-4-(5-6-7-8-9)-10=11 but there are more
possibilities.How many solutions can you find?

Too many to list. Keeping in mind that "(2-3)(-4-5)-6" implies a multiplication, and that you can subdivide the number 10 by something like "-9-1(0)" or "(-9-1)(0)", there's worlds of possibilities! I wrote a program that found 13,639 solutions using one, two, or three pairs of parentheses.

However! I think the writers of the problem were after something a little more sneaky. Try solving the problem with only ONE set of parentheses, and you'll notice that there's only ONE solution!

DaveE

 

[zoki85]

13639 is really astronomical number.And the number of possibilities could be even much larger than that.I'm not sure if they predicted multiplication as legal option.How many possibilities do you find without multiplication usage?

 

[davee123]

13639 is really astronomical number.And the number of possibilities could be even much larger than that.I'm not sure if they predicted multiplication as legal option.How many possibilities do you find without multiplication usage?

Without multiplication, my program found 551 solutions. But a bunch of those are duplicates. For example, the program considers the following answers to be different, when really, they're the same:

-1-2-3-4-(5-6)-(7-8-9-10) = 11
-1-2-3-4-((5-6))-(7-8-9-10) = 11
(-1)-2-3-4-(5-6)-(7-8-9-10) = 11

But, there's still lots of solutions. Here's a few it found:

-1-2-3-4-(5-6)-(7-8-9-10) = 11
-1-2-3-4-(5-(6-(7-8))-9-10) = 11
-1-2-3-4-(5-(6-(7-8-9-10))) = 11
-1-(2-(3-4-(5-6))-7-8-9)-10 = 11
-1-(2-(3-4-5)-6-7-8-(9-10)) = 11
-1-((2-3-4-5)-6-7-8)-9-10 = 11
-1-(2-3)-4-(5-6-7-8-9)-10 = 11

There's tons, though. I could go on.

The point is that there's only ONE solution if you just use one pair of parentheses. I think THAT's the challenge they were offering.

My program found:
1 pair - 1 solution
2 pair - 32 solutions
3 pair - 518 solutions

So, see if you can find the one solution that only uses a single pair of parentheses!

DaveE

[edit]
So, modifying my program to account for *most* (but not all) of the duplicates, and not allowing for multiplication, it finds:
1 pair - 1 solution
2 pair - 20 solutions
3 pair - 189 solutions
[/edit]

 

[tehno]

If we don't allow multiplications , there
are only 17 basicaly different solutions without nested brackets:

1: -(1-2-3-4-5)-6-7-(8-9-10) =11
2: -(1-2-3-4)-(5-6)-(7-8)-(9-10)=11
3:-(1-2-3-4)-5-(6-7-8-9)-10 =11
4:-(1-2-3)-(4-5-6-7)-8-(9-10) =11
5: -(1-2-3)-(4-5-6)-(7-8-9)-10 =11
6: -(1-2)-(3-4-5-6-7)-(8-9)-10=11
7: -(1-2)-(3-4)-5-6-(7-8-9-10)=11
8:-(1-2)-3-(4-5)-(6-7)-(8-9-10)=11
9: -(1-2)-3-4-(5-6-7-8)-(9-10) =11
10:-1-(2-3-4-5-6-7-8)-9-10 =11
11:-1-(2-3-4)-5-(6-7)-(8-9-10) =11
12: -1-(2-3)-(4-5-6)-7-(8-9-10)=11
13:-1-(2-3)-(4-5)-(6-7-8)-(9-10)=11
14:-1-(2-3)-4-(5-6-7-8-9)-10 =11
15: -1-2-(3-4-5-6)-(7-8)-(9-10) =11
16: -1-2-(3-4-5)-(6-7-8-9)-10 =11
17: -1-2-3-4-(5-6)-(7-8-9-10) =11


I obtained them by program written in Turbo Pascal

PROGRAM Brackets (INPUT,OUTPUT);

VAR
   i,j,counter,sum:INTEGER;
   t : ARRAY[1..10] OF INTEGER;
   open:BOOLEAN;
BEGIN

counter:=0;
t[1]:=1;
FOR i:=2 TO 10 DO t[i]:=2*t[i-1];
FOR i:=512 TO 1023 DO
BEGIN
sum:=0;
FOR j:=1 TO 10 DO
   IF t[11-j] AND i:=0 THEN sum:=sum+j
                       ELSE sum:=sum-j;
   IF sum=11 THEN
BEGIN
   INC(counter);
   WRITE(counter:5,':');
FOR j:=1 TO 10 DO
   IF t[11-j] AND i=0 THEN WRITE('+',j)
                      ELSE WRITE('-',j);
WRITELN('=11');
END;
END;
END.

The program is written to be short and quick so maybe isn't
obvious at first glance how works.
The resulting listing given above corresponds to program output when we get
rid of the brackets on the left side of the expressions.
One feature of this program is that it can be modifyed to
find all possibilities with and without nested brackets.
There are 7628 of these in total!No more no less.
However all of the solutions with nested brackets can be reduced
to the 17 basicaly different ones given above.
For example:

-1-2-3-4-(5-(6-(7-8-9))-10)=11
-1-2-3-4-(5-(6-(7-8-9-10)))=11

are reducible to the solution #17.

EDIT:
I didn't bother myself to compose the program that will account
for multiplication options as well.
But my rough estimate gives me an upper bound
~$7628\sqrt{20}$ for number of all the solutions with these options.

 

[davee123]

However all of the solutions with nested brackets can be reduced
to the 17 basicaly different ones given above.

Effectively, yes, there's a limited amount of +'s and -'s that you can apply to each term. So essentially, by adding parentheses, you're granting the ability to make some of the numbers positive, or leave them negative. The number 1 always has to be negative, but anything else can be switched one way or another. So, in theory, there are 2^9 (512) possibilities, and (I trust) only 17 of those are valid solutions.

But what that means is that a solution like this:

-1-(2-(3-4-5)-6-7-8-(9-10)) = 11

Would be equivalent to your solution #14:

-1-(2-3)-4-(5-6-7-8-9)-10 = 11

Now, that's sort of true, but I'd argue that those really are pretty distinct in terms of order of operations and in writing style.

DaveE

[edit]
To be a bit more clear, the 17 solutions are:

-1,+2,+3,+4,+5,-6,-7,-8,+9,+10
-1,+2,+3,+4,-5,+6,-7,+8,-9,+10
-1,+2,+3,+4,-5,-6,+7,+8,+9,-10
-1,+2,+3,-4,+5,+6,+7,-8,-9,+10
-1,+2,+3,-4,+5,+6,-7,+8,+9,-10
-1,+2,-3,+4,+5,+6,+7,-8,+9,-10
-1,+2,-3,+4,-5,-6,-7,+8,+9,+10
-1,+2,-3,-4,+5,-6,+7,-8,+9,+10
-1,+2,-3,-4,-5,+6,+7,+8,-9,+10
-1,-2,+3,+4,+5,+6,+7,+8,-9,-10
-1,-2,+3,+4,-5,-6,+7,-8,+9,+10
-1,-2,+3,-4,+5,+6,-7,-8,+9,+10
-1,-2,+3,-4,+5,-6,+7,+8,-9,+10
-1,-2,+3,-4,-5,+6,+7,+8,+9,-10
-1,-2,-3,+4,+5,+6,-7,+8,-9,+10
-1,-2,-3,+4,+5,-6,+7,+8,+9,-10
-1,-2,-3,-4,-5,+6,-7,+8,+9,+10

And there are multiple ways of writing each of these with parentheses, as demonstrated above.
[/edit]

 

[tehno]

Classification of reduction depends on how one uses the no-nested brackets code for composing the expanded code for nested brackets solution.
Point is there are 7628 solutions and that all are reducible to 17 solutions.

cheers.

 

[zoki85]

That's absolutely insane!More than 7628 solutions if multiplication can be used...Ok,I'll trust You guys.
Does that mean that they expect to find the best solution,like that under
number #10 in tehno's post (with only 1 pair of brackets)?
By the way ,how many solutions exists with unnested brackets but with allowed multiplication ?