Challenge 85: Can You Maximize D(n) - D(n+111)?

Share
Embed
  • Published on Mar 21, 2019
  • Congratulations to Philip Yao, Gabriel N., Jeremy Weissmann, Kunal Gaurav, Evyatar Baranga, Rishav Gupta, Ruben van Erkelens, Nicola C, attyfarbuckle, and Mac KNÖDEL for successfully solving the last week's math challenge question! Philip Yao was the first person to solve the question.
    Welcome, everyone! LetsSolveMathProblems presents one weekly math challenge problem every Wednesday (continental U.S. time). To participate, please comment your proposed answer and explanation below (or discuss potential solutions with other viewers), keeping in mind that your comment should be left unedited to win the recognition prize. Up to the first ten people with correct solutions are recognized in the next challenge video. The solution to a challenge problem is posted as a separate video the following Wednesday.
    For more Weekly Math Challenges:
    usclip.net/p/PLpoKXj-PWCbaDXYHES37_zX4O-kCWxguM

Comments • 48

  • Esha Kurwa
    Esha Kurwa 2 months ago

    max value is 91

  • mstmar
    mstmar 2 months ago

    the maximum is 24 for n = 908 (and also any n of the form 9...908 with an odd number of 9s)
    if we consider an n which has digits abcd...klm...z and n+111 has digits abc...kLM...Z where k is where the carry overs stop from the addition of 111. The start of each alternating sum of D(n) and D(n+111) will cancel each other out up to k. E.g. n = 123999 and n+111 = 124110 then a...k = 12, l...z = 3999, L...Z = 4110. in the alternating sum, the 1-2 cancels in both and thus D(n) - D(n+111) = D(l..z) - D(L..Z). Because of this, we can ignore the start of any number n which the carry doesn't go all the way to the first dgit, leaving only n's of the form a99...999bcd (with 0 or more 9s, and a,b,c and d can be any digit from 0-9)
    On top of that, any consecutive 9's will just cancel out leaving 9-9 or -9+9 in D(n) and 0-0 in D(n+111) thus we can ignore any number that has more than one 9
    leaving us only needing to check numbers of the form abcd or a9bcd
    numbers of the form a9bcd have the 9 in the second position which gives D(n) a -9 hit, and gets taken out for n+111 from the carry over, thus no numbers of that form can work unless a = 9 which essentially leaves just bcd.
    this leaves only 1-3 digit numbers or 4 digit numbers ending in at least 889 (for the carry to happen) which are easy enough to check

  • Jaime Araujo
    Jaime Araujo 2 months ago

    Something interesting is that with s(n)= digits sum it will be the same answer

  • Intergalactic Bajrang dal

    Let the last 3 digit numbers be ABC, If n has even digits like 1234567ABC , D(n) = 1+3+5+7-2-4-6+(B-A-C) = x+(B-A-C), if n has odd digits, D(n) = x+(A+C-B) where x is the alternative sum of the remaining digits.
    n+111 = ...EFGH where EFHG are the last 4 digits.
    D(n+111) =y+ (F+H)-(E+G) if n+111 has odd digits or else its y+ (E+G)-(F+H)
    D(n)-D(n+111) = f(n)
    f(n) has 4 possibilities
    case 1: f(n) = (B+E+G)-(A+C+F+H)
    case 2 : f(n) = (B+F+H) - (A+C+E+G)
    case 3: f(n) = (A+C+E+G) - (B+F+H)
    case 4 :f(n) = (A+C+F+H) - (B+E+G) i.e. n has odd digits and n+111 has even digits
    C+1=H if we can maximize both terms then f(n) would be larger. case 3 rules out as C-H=1 thus f(n) will be smaller. Case 2 also rules out as H-C = -1. f(n) will be less again. case 1 also rules out as H and C need to be minimized i.e H=1 and C=0, but in case 4 if C= 8, then H=9 then C+H = 17 which is the maximum value we get out of the 4 cases.
    proceeding with case 4 is it seems more "answer friendly"
    if B=0 then G=1, (minimize B and G)
    if A=8, F=9,
    and so E=0, but that would mean n+111 has odd digits which is a contradiction. So we choose A= 9 and so F=0 and so E=1, thus n+111 has even digits as we had assumed.
    thus ABC = 908, EFGH = 1019
    f(n) = 9+8-1-1+9 = 24

  • Ahmad Kalaoun
    Ahmad Kalaoun 3 months ago

    I calculated it and i found that
    D(n) - D(n+111)=-1
    for any positif integer n...

  • Minh Cong Nguyen
    Minh Cong Nguyen 3 months ago +5

    The answer is 24.

    I found that after I post the answer of 24, someone else have realized that the real answer is 24 (not 21), however no one have shown a "rigorous" solution for this problem. Here is my solution:
    Let U(n)= D(n)-D(n+1) then we need to maximize D(n)-D(n+1)=U(n)+U(n+1)+U(n+2)+.... + U(n+110), which is the sum of 111 consecutive numbers of the sequence U(n). So we first need to find the properties of the sequence U(n).

    Here are all the actual values of U(n): 1,-1,10,-10,8

    U(n)=8 if n = 9, 999, 99999,..... (an odd number of 9s). U(n)=-1 if n=99, 9999, 999999,... (an even number of 9s)
    In other cases, n can be writtten in the forms of X, X99, X999, X9999,... with X is a number not ending with 9.

    If n has an ODD number of digits:
    U(n) = -1 if n is ending with X, X99, X9999,.... (with X has an ODD number of digits and X is not ending with 9)
    U(n) =10 if n is ending with X9, X999, X99999,....(with X has and EVEN number of digits and X is not ending with 9)

    If n has an EVEN number of digits:
    U(n) = 1 if n is ending with X, X99, X9999,.... (with X has an EVEN number of digits and X is not ending with 9)
    U(n) = -10 if n is ending with X, X99, X9999,.... (with X has an ODD number of digits and X is not ending with 9)

    Now we need to maximize the sum of 111 consecutive numbers from the above sequence:

    If U(n), U(n+1),..., U(n+110) do not contain any value of 8s, i.e the interval from n to n+110 does not contain any of 9, 999, 99999,.... Then the sum of 10 consecutive numbers will be +1 (sum of 9 of -1s and 1 of 10) or -1 (sum of 9 of 1s and 1 of -10s). Hence the maximum sum of 111 consecutive numbers will be 21 (110 numbers creating 11 groups with the sum of +1 and a lone number 10). That's why many people claimed that 21 is the maximum value.

    If U(n), U(n+1),..., U(n+110) contain value of 8s, i.e the interval from n to n+110 contains any of 9, 999, 99999,...., then it can only contains exactly 1 value of 9, 999, 99999,..., which means that U(n), U(n+1),..., U(n+110) contains exactly 1 value of 8, the rest are 1,-1,10,-10. By try-and-error, the ways to maximize the sums is to have 18 of 1s, 82 of -1s, 9 of 10s, 1 of -10, and 1 of 8, giving the sum of 24.

    Hence, the maximum possible value is 24.

  • Rohit Agarwal
    Rohit Agarwal 3 months ago

    The answer is 24 with n=908. Check my previous comment for the code (which I fixed).

  • Sam Georgiou
    Sam Georgiou 3 months ago

    24, when n=908, 99908, 9999908 etc

  • Albert Estellé Caballer

    The maximum can be achieved when n has an odd number of digits and n+111 an even number of digits. For example ABC+111=DEFG.
    Then you can group D(n)-D(n+111) as (A-B+C)-(D-E+F-G), which equals A+C+E+G-(B+D+F).
    That tells us that we are looking for n with high numbers on the thirdmost and last digits, which should one or both change into low numbers in the fourth to last and/or second to last digits of n+111.
    That leaves few combinations to test of which a maximum of 24 is achieved on n=908.
    Adding an even amount of 9's to the left of n makes the same result stay.

  • Amihai Zivan
    Amihai Zivan 3 months ago +1

    I don't know why several people wrote 21 as for n=908 D(n)-D(n+111)=24. I suspect it is the max value

  • Serengeti Ghasa
    Serengeti Ghasa 3 months ago

    The answer is 24 .
    In case of n=9a9 where a n+111=10000x+1019
    Then D(n)-D(n+111)=24 {up to first x digit all will cancel and it will follow D(908)-D(1019)=24}
    With love
    Prabhat Kumar Sahu

    • Serengeti Ghasa
      Serengeti Ghasa 3 months ago

      Last few step gives the results as 10
      So it is maximum value when n=908
      In other case in odd digit number if last four are 09a9 where a

  • Vansh Singh
    Vansh Singh 3 months ago +1

    The answer is 21. I tried the same strategy as @Arun Bhardwaj did. I maximised D(n) by taking it to be of the form 90909......909 this gives us the max cap. Now by hit and trial I checked if this value seems consistent or does it diverge. Strangely enough it seems to be max capped at 21.... Example: 90909 gives sum as 27 and adding 111 we get 91020. Subtracting we get 21 as the result. You can also minimise the value of the expression D(n+111). Ofcourse this is a little vague approach but it still counts. Ty for reading. Cheers

  • quak quak
    quak quak 3 months ago +3

    if n+111 has no values that carries over (basically if there are no 9s in the right most 3 digits) D(n) - D(n+111) will have all digits cancel out apart from the rightmost 3, the total will be either 1 or -1 depending if the number of digits of n is odd or even, if we allow to have 9s only in the 3 rightmost digits we can at most get 24 using n=908, if we allow 9s to be both in the rightmost 3 digits and in the rest of the number to get a digit to change after the sum we need all of the digit to the right of it to be 9s (apart from the rightmost 3 digits), if we calculate D(n) almost all of these 9s will cancel out apart from at most one 9 (that could be a -9 depending on the positions of the digits and how much digits n has), D(n+111) is affected as well, all the 9s we used this way will turn into 0s (note thet I don't mean all the 9s in n, just the one that are next to each other and that are affected in the summation), so they don't contribute in D(n+111), but we have a 1 carried over at the end, if we have set up n so that the successions of 9s gives a +9 in D(n) we will have a contribution of -1 in D(n+111) given buy the carry, in total D(n)-D(n+111) will gain a +10, unless n is in the form 9...9abc (where abc are the rightmost 3 digits), in this case the carry 1 will make n+111 a digit longer, in this case D(n)-D(n+111) will gain a +8, if we try to use this information to build an n which will give us the maximum we will find that it's impossible to beat n=908, so the maximum is D(908)-D(908+111)=17-(-7)=24

    • Serengeti Ghasa
      Serengeti Ghasa 3 months ago +1

      Nicely explained

    • Jeremy Weissmann
      Jeremy Weissmann 3 months ago +1

      quak quak I just found this n in bed and came on here to check if someone else had found it. Gadzooks!

  • 112BALAGE112
    112BALAGE112 3 months ago

    I would start by writing n as 1000k + l, l

  • adandap
    adandap 3 months ago

    The maximum clearly exists because only the last four digits can change (and only three if there is no carry of one) and thus the difference reduces to the difference of the numbers generated by the last four digits. So the question reduces to finding the maximum value generated by D = ... d4 d3 d2 d1 and D + 111, with there being two cases - odd or even numbers of digits. The biggest difference for odd digits will be when n+1 ends 090 - and it's clear that D = .... 0979 and D+111= ... 1090 maximises the difference to be 9-7+9 - (-1+0-9+0) = 21. In the even case the best you can do is 12, with n+111 ending ...909. An explicit example of the maximum is n = 10979, D(n) = 1+9+9-7 = 12 and then n+1 = 11090, D(n+111) = 1+0+0-1-9 = -9.

    • adandap
      adandap 3 months ago

      @Benjamin Wang Thanks, but it's fine. Someone else can have the shout out slot. I'm happy just to play along at home.

    • Benjamin Wang
      Benjamin Wang 3 months ago

      adandap post as non-reply comment?

    • adandap
      adandap 3 months ago

      Rats - this is not quite right. I wrote some Mathematica code and while there are lots of 21s, there are also some instances of 22 and 24. The answer is actually 24, with two such examples being n = 908 or 99908. So my answer above should be modified to read that the max is when n has an odd number of digits and is of the form 999...908, thus n+111 = 1000...019 has an even number of digits.

  • Arun Bharadwaj
    Arun Bharadwaj 3 months ago

    Since my previous comment is nowhere to be seen in the comment section, im posting it again....
    The answer is 21.
    The two strategies one can use is maximize D(n) by choosing n to be 909090...90909. Which gives D(n)-D(n+111) = 21.
    Or
    Minimize D(n+111) by choosing n+111= 19090909090...90909. This makes D(n)-D(n+111) = 12.
    Maximizing the expression gives us the required answer as 21.

  • Rohit Agarwal
    Rohit Agarwal 3 months ago

    Clearly only the last 4 digits matter (because of carrying), I checked all the numbers up to 10000 to find the maximum of this difference. Here is the code: editor.p5js.org/rohaga20@bergen.org/sketches/vihrYB2Fu . I got 21 which happens at 1909.

    • Rohit Agarwal
      Rohit Agarwal 3 months ago

      Nvm it’s 24 with 908, let me recomment although it’s probably too late

    • Rohit Agarwal
      Rohit Agarwal 3 months ago

      Yeah that shouldn’t affect the max though, although the location is wrong. Hopefully I’ll still get credit. I just used p5 because I was on my laptop with no IDEs lol. Sorry for spaghetti code.

    • attyfarbuckle
      attyfarbuckle 3 months ago

      Kudos for using p5.
      You've got an out-by-one error though when you check whether to add or subtract.
      This means e.g. D(6) = -6 when it needs to be +6.
      Easily fixed though.

  • mark erena
    mark erena 3 months ago

    If you do a bit of work, you world realise that the last 3 or 4 digits of n and of n+111 are remaining because the others cancel. The max is obviastly reached when n has an odd number of digits, because if n doesn't, then you subtract more.
    case 1: no remainder
    What will be left is: n3-n2+n1-(n3+1-n2-1+n1+1)=-1
    case 2: remainder
    If n1=9 then n3-n2+9-(n3+1-n2-2 +9)=1
    If n2=9 then n3-9+n1-(n3+2-0+n1+1)=-12
    If n2=8 and n3=9 then n3 -8+9-(n3+2-0+0)=-1
    And so on you continue with also the last 4 digits and would get That the max is 21

  • Mohith S N Raju
    Mohith S N Raju 3 months ago

    21
    As if the unit digit is nine adding will be a carry over and it will to a net (-10) as 9is replaced by 0 in units place and and one is added in tens place but it results in subtraction.
    And in 111 the one in tens place leads to another decrease in one
    And similarly if the hundreds place has a nine it will again lead to -10

  • ba ke
    ba ke 3 months ago

    The answer is 21.

  • Minh Cong Nguyen
    Minh Cong Nguyen 3 months ago

    The answer is 24

  • Nitro Zox
    Nitro Zox 3 months ago

    Its -1 for odd digits and 1 for even digits.
    for a number N with k digits : N= n0 + 10n1 + 10^2n1 ...... 10^k nk.
    D(N) = The sum of r=0 to k : (-1)^k-r nk-r

  • anonimo aninimus
    anonimo aninimus 3 months ago

    The answer: 21.
    Let f(n) = D(n) - D(n+111). Then, the maximum value of f(n) is 21 for multiple n values. We see this by trying to maximize f as a normal function. We first try to maximize D(n). It is easy to see that if n is of the form n = 90909...909, then D(n) is at its maximum value, as if there are b 9's, then D(n) = b * 9. Since in base 10, 9 is the highest single digit one can get, this must be the maximum value.
    Now, for each n of this form, let b be the number of 9's it has. For b = 2, we have f(n) = 15. For b > 2, we have that f(n) = (9*b) - (9*(b-2) - 3) = 9*2 + 3 = 21. We can easily prove this through induction. This is left to the reader. Then, for n of this form, f(n) = 21.
    For any other n, f(n) will be less. Since D(n+111) can be negative, it can contribute to f, but for it to contribute at its maximum, we need n+111 to be of the form 190909...909. But then, we have n = 190909...090798 (again, we can prove this by induction), and so if b is the amount of 9's n+111 has, then f(n) = (1 - (9*(b-2)) - 7 + 9 - 8) - (1 - (9*b)) = 1 - 7 + 9 - 8 + 18 - 1 = 12.

    • 112BALAGE112
      112BALAGE112 3 months ago

      If a function f(x) has a maximum at x0 then it doesn't necessarily follow that f(x0)+f(x0+c) is a maximum of f(x)+f(x+c).

  • DragonFire17
    DragonFire17 3 months ago

    I got the maximum value to be 91 because each number can be written as the sum of 10^n*a_n and when you do the alternating sum, everything will cancel except for the last four terms. Doing some case work, we would find the maximum value is 91

    • DragonFire17
      DragonFire17 3 months ago

      Well it appears I am not as good at math as previously thought. Carry on.

    • 상훈강
      상훈강 3 months ago

      n=999999999999999999, that isn't.

    • LetsSolveMathProblems
      LetsSolveMathProblems  3 months ago

      I do not believe there exists n such that the desired expression equals 91. Could you provide an example of such n?

  • Sergio Sanz
    Sergio Sanz 3 months ago

    All the digits of D(n) and D(n+111) except for the last four cancel out. So the maximum only depends on the last four digits of n and whether the number of digits in n is even or odd, if n has an even number of digits then the last three digits are negative, positive, negative. If n has an odd number of digits then the last three digits are positive negative positive. If the last three digits are all less than 8 and n has an odd number of digits then D(n) - D(n+111) will give a value of -1. Similarly if the last three digits are all less than 8 and n has an even number of digits, D(n) - D(n+111) will equal 1. If the last four digits are 8899 and the number of digits in n is odd. The result would be 10 which is the maximum value since increasing any of the digits value past 8899 would cause an extra subtraction to occur due to the remainder.

    • Sergio Sanz
      Sergio Sanz 3 months ago

      I see what I did wrong, I decided to have high first and third digits in order to have a remainder. But this was a huge sacrifice for a tiny addition. Instead 0909 would give 21

    • leoitshere
      leoitshere 3 months ago

      n = 9090 gives 12.

    • Matt Moreno
      Matt Moreno 3 months ago

      What about n = 80? Wouldn't that give us 8 - 0 - 1 + 9 - 1 = 15?

  • Rajat Khandelwal
    Rajat Khandelwal 3 months ago +1

    I think its max value does not exist as it is dependent of the n. for any number n if its no. Of digit is even in no. Then its value is 1 and if it is odd in no. It value will be - 1
    Let n=abc.....$€¥ (a x digest it number)
    Case 1 when no. Of digit are even
    Then d(n) =a-b+...-$+€-¥
    Or d(n+111)=a-b+c-.... - ($+1)+(€+1)-(¥+1)
    Then d(n) - d(n+111)=1-1+1=1
    Case 2 if odd no. Of digits
    D(n) - d(n+111)=-1
    Hence its maximum value purely depends on no. Of digits of n

  • José Ortiz
    José Ortiz 3 months ago

    D(n)-D(n+111) = 2D(n)-1 .... and D(n) does not have a maximum therefore the first expression neither

    • LetsSolveMathProblems
      LetsSolveMathProblems  3 months ago

      Note that your formula does not hold for n = 1: D(1) - D(112) = 1 - (1 - 1 + 2) = -1, which is not equal to 2D(1) - 1 = 1.

  • Smokie Bear 🔴🔵
    Smokie Bear 🔴🔵 3 months ago +4

    I believe that the maximum value does not exist because moving clocks are slower.

    • Aaron He
      Aaron He 3 months ago +1

      Moving clocks? What am I missing from this joke?

    • LetsSolveMathProblems
      LetsSolveMathProblems  3 months ago +9

      Since you did not specify the reference frame from which the clocks are observed, I unfortunately cannot accept your answer.

  • Bruno Alejandro Andrades

    Did u just say modulo 11?