Solution 85: Maximizing the Difference of "Alternating Sums"

Share
Embed
  • Published on Mar 28, 2019
  • Without a doubt, D(n) is unbounded. Does that mean that D(n)-D(n+111) is unbounded as well? If it is not, how can its maximum be achieved?
    Congratulations to quak quak, Albert Estellé Caballer, Rohit Agarwal, Minh Cong Nguyen, Intergalactic Bajrang dal, and mstmar for successfully solving the last week's math challenge question! quak quak was the first person to solve the question.
    Your support is a heartfelt source of encouragement that propels the channel forward.
    Please consider taking a second to subscribe in order to express your valuable support and receive notifications for the latest videos!
    Any likes, subscriptions, comments, constructive criticisms, etc., are very much appreciated.
    For more Weekly Math Challenges:
    usclip.net/p/PLpoKXj-PWCbaDXYHES37_zX4O-kCWxguM

Comments • 9

  • Sarthak Bansal
    Sarthak Bansal 5 months ago +1

    I noticed that there was no maximum for D(n) - D(n+111) because you could have n ending in a bunch of 9s and thus n+111 would end in a bunch of 0s

  • adandap
    adandap 5 months ago +2

    Looking at the solution here I'm glad I resorted to a program!

    • adandap
      adandap 5 months ago

      Sure thing Matthew. It's in Mathematica language.
      mmax= -1;
      For[n = 1, n mmax, mmax = ans] ];
      Print[mmax]

    • Matthew Hoge
      Matthew Hoge 5 months ago

      adandap I'd love to see the code :D

  • Benjamin Wang
    Benjamin Wang 5 months ago +14

    The proof that only final 5 digits matter is kinda hand-wavy :/

    • LetsSolveMathProblems
      LetsSolveMathProblems  5 months ago +3

      I did gloss over some parts of the argument that only the final five digits matter. In retrospect, I probably appealed too much to intuition instead of providing a clear, rigorous proof. I sincerely apologize if my explanation led to confusion or dissatisfaction. I include below what is perhaps a much better proof.

      Assertion: Given any positive integer n, D(n)-D(n+111) = D(p)-D(p+111), where p consists of the final k digits of n, where k is at most 5.

      Proof: Given any n that has three or more digits (certainly, we are done if n has one or two digits), we will perform the following casework. If the 100's digit of n does not change upon the addition of n by 111 (that is, no rounding occurs in the 100's digit), only the final three digits of n matter, since every digit preceding the 100's digit will be identical in n and n+111.

      Therefore, we focus only on n that has a rounding-up in its 100's digits. We will have a consecutive series of rounding-ups starting with the 100's digit (and proceeding leftward), which must eventually cease at kth digit from the right, where k is 4 or greater. Certainly, all digits to the left of kth digit will be identical in n and n+111 and can be ignored. If k = 4 or 5, we are done. Let k > 5. Now note that 4th, 5th, ... , (k-1)st digits from the right of n must be all 9's to allow for the consecutive rounding-ups. So, the 4th, 5th, ... , (k-1)st digits from the right of (n+111) will all be 0's. As in the video, we can safely disregard an even number of pairs of 9's in n and, correspondingly, 0's in (n+111) and retain the same value of D(n)-D(n+111). This completes the proof.

  • vokuheila
    vokuheila 5 months ago +24

    I am not a fan of this problem at all. The solution is far from beautiful and extremely grindy.

    • adandap
      adandap 5 months ago

      @LetsSolveMathProblems I think the problem might have been (at least for me) that I didn't have enough intuition about the problem to be able to be surprised by the answer. The fact that two unbounded numbers might have a finite difference doesn't seem that surprising. After all, (n+1) - n = 1...

    • LetsSolveMathProblems
      LetsSolveMathProblems  5 months ago +1

      I admit that this problem is very "bashy" and, as far as I am aware, does not yield to any elegant approaches. I had hoped that the surprising final answer of 24 (and the corresponding value of n of 908) would compensate for the long-winded proof.