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

• Esha Kurwa 5 months ago

max value is 91

• mstmar 5 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 5 months ago

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

• 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 5 months ago

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

• Minh Cong Nguyen 5 months ago +5

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 5 months ago

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

• Sam Georgiou 5 months ago

24, when n=908, 99908, 9999908 etc

• 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 5 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 5 months ago

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 5 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 5 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 5 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 5 months ago +1

Nicely explained

• Jeremy Weissmann 5 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 5 months ago

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

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.

@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 5 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 5 months ago

Since my previous comment is nowhere to be seen in the comment section, im posting it again....
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 5 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 5 months ago

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

• Rohit Agarwal 5 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 5 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 5 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 5 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 5 months ago

• Minh Cong Nguyen 5 months ago

• Nitro Zox 5 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 5 months ago

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 5 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 5 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 5 months ago

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

• 상훈강 5 months ago

n=999999999999999999, that isn't.

• LetsSolveMathProblems  5 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 5 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 5 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 5 months ago

n = 9090 gives 12.

• Matt Moreno 5 months ago

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

• Rajat Khandelwal 5 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 5 months ago

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

• LetsSolveMathProblems  5 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 🔴🔵 5 months ago +4

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

• Aaron He 5 months ago +1

Moving clocks? What am I missing from this joke?

• LetsSolveMathProblems  5 months ago +9

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

• Did u just say modulo 11?