Subscribe via feed.

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

This post is under “MathsChallenge” and has 7 respond so far.
If you enjoy this article, make sure you subscribe to my RSS Feed.

7 Responds so far- Add one»

  1. 1. Zorglub Said:

    Is it possible that the solution is

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

  2. 2. slavy Said:

    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 :)

  3. 3. Chris Said:

    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.

  4. 4. slavy Said:

    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 :P

  5. 5. Zorglub Said:

    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.

  6. 6. slavy Said:

    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)

  7. 7. slavy Said:

    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.

Post a reply

PHP Warning: PHP Startup: Unable to load dynamic library 'C:\Program Files (x86)\Parallels\Plesk\Additional\PleskPHP5\ext\php_mssql.dll' - The specified module could not be found. in Unknown on line 0 PHP Warning: PHP Startup: Unable to load dynamic library 'C:\Program Files (x86)\Parallels\Plesk\Additional\PleskPHP5\ext\php_pdo_mssql.dll' - The specified module could not be found. in Unknown on line 0