## 2013 part 2

Posted by slavy on April 29, 2012 – 1:47 am

Find all positive integers N, s.t., from the “N string” 12345678910111213….N with the help of (unlimited number of) “+” signs we can derive 2013.

Example: We can derive 28 for N=4 via 1+23+4

April 29th, 2012 at 6:31 am

Is it possible that the solution is

N = 9k + 3 or N = 9k + 5 for k = 1, 2 ,…, 23 ?

April 29th, 2012 at 8:43 am

Wow, so it is possible to do a computation right This is my answer, as well I’m interested in seeing some mathematical arguments, but maybe this can be postponed with couple of days so that we don’t spoil Chris’ fun

April 30th, 2012 at 9:10 am

I’m baffled. I can see that N = 9k+3 or 9k+5 (I haven’t yet bothered to check the range of k, but it is obvious that there is one). I can only show that that’s a necessary condition, but not a sufficient condition. In fact, I’d be surprised if it is sufficient. My brain hurts thinking of how to prove it, yet alone to find how many ways you could do it (as was originally asked in part 1) etc.

All I’ve come up with is the following. As usual we assume that e.g.

ABCD = A+B+C+D = AB+CD = … (mod 9). The residue (mod 9) of the digits in the string is equal to the residue of N(N+1)/2 (mod 9). We need N(N+1)/2 = 2013 (mod 9) => N(N+1) = 3 (mod 9). There is no slick way of solving for N, so we simply create a table and inspect it. As N steps from 1 to 9, N(N+1) steps through 2,6,3,2,3,6,2,0,0 (mod 9). Hence only N = 3 or 5 (mod 9) => N = 9k+3 or 9k+5.

I will look at the range of k, even if only to look at the distribution of the digits in the first N integers in decimal notation.

Thanks for these two problems Slavy. They have been quite stimulating.

April 30th, 2012 at 12:56 pm

Hi Chris, mod 9 is extremely powerful tool So far you are not taking full advantage of it. My suggestion is the following: consider first the min case N=12, and show that 2013 is achievable there. This is the most difficult case actually, and if you manage to to id, you most probably will be able to crack the rest. A somehow surprising hint: Diophantus equations…

That’s from me here – I prefer to see what you and Zorglub have rather than revealing my ideas

April 30th, 2012 at 4:54 pm

Here is a quick draft of what I had in mind

2013 mod 9 = 6. The only numbers whose sum of digits mod 9 = 6 are N = 9k + 3 or N = 9k + 5.

My idea was some sort of induction.

First cases:

12+34+56+789+10+1112 = 2013

1+2+34+56+789+10+1112+1+3+1+4 = 2013

Induction based on observations like 12 = (1 + 2) + 9 and 34 = (3+4) + 3*9. All of these numbers can be broken down by adding or subtracting multiples of nines.

And finally, the largest number must be less than 218 because the sum of the digits of 123…217218 exceeds 2013.

—–

Note: the induction part was pure intuition of my part. That is why in post 1 I asked if my answer was right rather than claiming to have found the answer.

May 1st, 2012 at 1:55 am

Hi Zorglub. I don’t think induction arguments work here. However, your observation with 12 and 34 is in the right direction! Generalize it to three- and four-digit numbers and use the hint from my previous post In order that you and Chris get more intuition, I will give you another subproblem to start with (should appear as 2013 part 3 in a while)

May 3rd, 2012 at 2:55 pm

Now for this problem: with the notation from my last post under “2013 part 3″, and using d as the sum of the last digits of the summands we have the system: 111a+11b+c=(2013-S(N))/9 and a+b+c+d=S(N). Take the solution for which a < b <c < d and d is maximal (argue that such a solution always exists!). I claim that for all N=9k+3 and N=9k+5 with k=1…23 the latter solution gives rise to at least one valid expression.