## 2013 part 3

Posted by slavy on May 1, 2012 – 2:00 am

Given the string 123456789101112, in how many different ways can you place “+” signs among some of the digits, so that the overall expression sums up to 2013?

The answer is at least 1, due to Zorglub’s example: 12+34+56+789+10+1112 = 2013

May 1st, 2012 at 9:34 am

I haven’t attempted to find ALL other options, but two solutions are as follows:

1234 + 567 + 89 + 10 + 1 + 112 = 2013

1234 + 5 + 678 + 91 + 0 + 1 + 1 + 1 + 2 = 2013

May 1st, 2012 at 3:33 pm

I found 14 solutions

1234 + 567 + 89 + 10 + 111 + 2

1234 + 567 + 89 + 10 + 1 + 112

1234 + 567 + 8 + 91 + 0111 + 2

1234 + 567 + 8 + 91 + 01 + 112

1234 + 567 + 8 + 91 + 0 + 111 + 2

1234 + 567 + 8 + 91 + 0 + 1 + 112

1234 + 5 + 678 + 91 + 01 + 1 + 1 + 2

1234 + 5 + 678 + 91 + 0 + 1 + 1 + 1 + 2

123 + 4 + 5 + 678 + 91 + 01112

123 + 4 + 5 + 678 + 91 + 0 + 1112

12 + 34 + 56 + 789 + 10 + 1112

1 + 234 + 567 + 89 + 10 + 1112

1 + 234 + 567 + 8 + 91 + 01112

1 + 234 + 567 + 8 + 91 + 0 + 1112

May 1st, 2012 at 11:50 pm

Very good Let´s say they are 9, since I don´t like numbers starting with 0. Can you prove that there are no other solutions and how?

May 2nd, 2012 at 6:12 am

Nothing fancy from me on this one.

14 positions for a + sign (or not) so only 2^14 options.

Easy enough for a brute force method involving a spreadsheet.

The proof is easy since you can see every scenario.

michel

May 2nd, 2012 at 7:31 am

I see I can confirm that your routine gives the right answer By the way, could you program also the three-scale algorithm if you have time? I´m really interested in the outcome…

May 2nd, 2012 at 4:52 pm

I am looking forward to Slavy’s justification. I bet that there is an accessible explanation.

May 3rd, 2012 at 1:41 am

OK, let me sketch the solution. It is not that elegant and still involves some cases, that one needs to compute.

First of all, 2013 is a 4-digit number and we use only ¨+¨ signs, meaning that we never glue more than 4 digits together in order to obtain 2013 at the end. The key observation (already made by Zorglub in the case of gluing 2 digits) is that: cd-(c+d)=9c, bcd-(b+c+d)=99b+9c, and abcd-(a+b+c+d)=999a+99b+9c. Now, denote the sum of the digits of the N-string by S(N). Take an arbitrary expression E where we have put enough signs in between so that every summand is at most 4 digital. Then E-S(N)=9(111a+11b+c), where a is the sum of all the leading digits of the summand, b is the sum of all the second digits, and c – the sum of all the third digits (under the convention that each summand is represented as a 4-digit number via adding as many zeros as necessary, e.g., 23=0023, 5=0005, etc.).

In our particular problem, N=12, S(N)=51, and E=2013, leading to 111a+11b+c=(2013-51)/9=218. Now we need to consider several cases:

Case 1: a=0 Then 11b+c=218. We will show that such a setup does not lead to an admissible expression. First of all, note that it is very hard (and extremely unlikely) that b>c. Indeed in the string 123456789101112 the only 3-digit numbers which second digit is smaller than the first one are 910 and 101, and since they have 2 elements of the string in common, we cannot use both of them in the same expression! Moreover, we have two case 111 and 112, where the two digits are equal, and in all the others we have that the second digit is by 1 bigger than the first one! Thus, the solution b=19, c=9 of the Diophantine equation cannot lead to a valid expression. The next possibility b=18, c=20 leads to b+c=38, which is too large for us. The sum of all the digits of the string is 51, and at least every third digit is a last digit of a summand, hence not involved in b+c. But there is no way that the sum of all last digits be less than 14, so there is no valid expression associated to this case either. It gets even worse for b < 18, so the case a=0 is completed.

Case 2: a=1. We have 3 candidates for the 4-digit summand: 1234, 1011, 1112. With a similar arguments as in the case a=0 it is relatively easy to conclude that 1012 also does not lead to a valid expression (it´s position in the string makes 9 a last digit of a number, and on the top of that 1011 does not contribute to b and subtracts only 1 from the remaining c). We have two substantial sub-cases:

2.1. 1234. We are left with the string 56789101112, for which 11b+c=218-111-11*2-3=82. Similar as before, solutions with b greater than c do not lead to valid expressions. For (b=6, c=16) we have two options: b=5+1 or b=6 (meaning either two 3-digit summands or only one).

2.1.1 In the first case, we have 567 with 101,111, or 112. 101 is impossible, 111 leads to the string 8910 for which c=16-7=9 and this can be achieved in 2 different ways 89+10 or 8+91+0, while 112 leads to the string 89101 again with c=9 and again with the corresponding solutions 89+10+1 and 8+91+0+1 as before.

2.1.2 For b=6, we have 678 as a summand and remaining string 9101112 with c=16-7=9. We have only one solution 91+0+1+1+1+2.

2.1.3 b < 6. Then c is greater than 27 and it is not hard to check that this doesn´t lead to a valid expression.

2.2. 1112. We are left with the string 12345678910, for which 11b+c=218-111-11*1-1=95. Again (b=8,c=7) doesn´t lead to a valid expression, and neither (b < 7,c greater than 29). Thus we are left with (b=7,c=18). Here we have 3 options b=7, b=6+1, or b=5+2.

2.2.1. b=7, i.e., 789 is a summand. We are left with two pieces of the string 123456 and 10 for which c=18-8=10. The only option is 12+34+56+10.

2.2.2. b=6+1, i.e., 123 and 678 are summands. We are left with two pieces of the string 45 and 910 for which c=18-9=9. Again only one option 4+5+91+0.

2.2.3. b=5+2, i.e., 234 and 567 are summands. We are left with the string 8910 for which c=18-9=9. This case is the same as 2.1.1 and leads to 2 solutions.

Overall we get 9 solutions: four from 2.1.1, one from 2.1.2, one from 2.2.1, one from 2.2.2, and two from 2.2.3. The proof is finished.

May 3rd, 2012 at 4:58 pm

Wow. Thanks for taking the time to write the exhaustive details.

I was hoping to avoid that type of enumeration, but I understand that it is necessary.