Mixing
How to come up with a greedy solution and prove it?
Clash Royale CLAN TAG#URR8PPP
up vote
3
down vote
favorite
Say we have a function $S(x)$, which gives the sum of the digits in the number $x$. So $S(452)$ would be $4 + 5 + 2 = 11$.
Given a number $x$, find two integers $a, b$ such that $0 <= a, b <= x$ and $a + b = x$. Objective is to maximize $S(a) + S(b)$. I came across this question on a programming website and the answer is to greedily choose a number $a$ containing all $9$'s such that it is lesser than $x$, and the other number would be $x - a$.
If $x = 452$, then $S(99) + S(353) = 29$ which is the maximum possible. How do I come up with this and prove the same?
number-theory discrete-mathematics algorithms
asked 2 hours ago
Andrew Scott
284
 |Â
show 2 more comments
up vote
3
down vote
favorite
Say we have a function $S(x)$, which gives the sum of the digits in the number $x$. So $S(452)$ would be $4 + 5 + 2 = 11$.
Given a number $x$, find two integers $a, b$ such that $0 <= a, b <= x$ and $a + b = x$. Objective is to maximize $S(a) + S(b)$. I came across this question on a programming website and the answer is to greedily choose a number $a$ containing all $9$'s such that it is lesser than $x$, and the other number would be $x - a$.
If $x = 452$, then $S(99) + S(353) = 29$ which is the maximum possible. How do I come up with this and prove the same?
number-theory discrete-mathematics algorithms
asked 2 hours ago
Andrew Scott
284
What is $n$ in the requirement $a+b=n$?
– 5xum
1 hour ago
2
I assume $n=x$, no? As a small point, you say that you are allowing $b=n$ but that would make $a=0$ which you are not allowing. Do you mean to allow the pair $n+0=n$ or not?
– lulu
1 hour ago
@5xum, n goes upto $10^12$.
– Andrew Scott
1 hour ago
2
I think the point isn't so much that the greedy algorithm finds some sort of unique max. Indeed, in most cases it just finds one of many. To prove it, I'd start by noting that given any optimal solution $a≤b$ we can subtract enough from each decimal place of $a$ to make the corresponding place of $b$ equal to $9$ without changing the sum you want. For example, for $n=154$ we could have the solution $77,77$ or we could "move $2$ over from each slot" to get the equivalent solution $55,99$ which is what the greedy algorithm would find.
– lulu
1 hour ago
@lulu, Yes. I am sorry. Edited the question.
– Andrew Scott
1 hour ago
 |Â
show 2 more comments
up vote
3
down vote
favorite
up vote
3
down vote
favorite
Say we have a function $S(x)$, which gives the sum of the digits in the number $x$. So $S(452)$ would be $4 + 5 + 2 = 11$.
Given a number $x$, find two integers $a, b$ such that $0 <= a, b <= x$ and $a + b = x$. Objective is to maximize $S(a) + S(b)$. I came across this question on a programming website and the answer is to greedily choose a number $a$ containing all $9$'s such that it is lesser than $x$, and the other number would be $x - a$.
If $x = 452$, then $S(99) + S(353) = 29$ which is the maximum possible. How do I come up with this and prove the same?
number-theory discrete-mathematics algorithms
asked 2 hours ago
Andrew Scott
284
Say we have a function $S(x)$, which gives the sum of the digits in the number $x$. So $S(452)$ would be $4 + 5 + 2 = 11$.
Given a number $x$, find two integers $a, b$ such that $0 <= a, b <= x$ and $a + b = x$. Objective is to maximize $S(a) + S(b)$. I came across this question on a programming website and the answer is to greedily choose a number $a$ containing all $9$'s such that it is lesser than $x$, and the other number would be $x - a$.
If $x = 452$, then $S(99) + S(353) = 29$ which is the maximum possible. How do I come up with this and prove the same?
number-theory discrete-mathematics algorithms
number-theory discrete-mathematics algorithms
asked 2 hours ago
Andrew Scott
284
asked 2 hours ago
Andrew Scott
284
edited 1 hour ago
asked 2 hours ago
Andrew Scott
284
asked 2 hours ago
Andrew Scott
284
asked 2 hours ago
Andrew Scott
284
284
What is $n$ in the requirement $a+b=n$?
– 5xum
1 hour ago
2
I assume $n=x$, no? As a small point, you say that you are allowing $b=n$ but that would make $a=0$ which you are not allowing. Do you mean to allow the pair $n+0=n$ or not?
– lulu
1 hour ago
@5xum, n goes upto $10^12$.
– Andrew Scott
1 hour ago
2
I think the point isn't so much that the greedy algorithm finds some sort of unique max. Indeed, in most cases it just finds one of many. To prove it, I'd start by noting that given any optimal solution $a≤b$ we can subtract enough from each decimal place of $a$ to make the corresponding place of $b$ equal to $9$ without changing the sum you want. For example, for $n=154$ we could have the solution $77,77$ or we could "move $2$ over from each slot" to get the equivalent solution $55,99$ which is what the greedy algorithm would find.
– lulu
1 hour ago
@lulu, Yes. I am sorry. Edited the question.
– Andrew Scott
1 hour ago
 |Â
show 2 more comments
What is $n$ in the requirement $a+b=n$?
– 5xum
1 hour ago
2
I assume $n=x$, no? As a small point, you say that you are allowing $b=n$ but that would make $a=0$ which you are not allowing. Do you mean to allow the pair $n+0=n$ or not?
– lulu
1 hour ago
@5xum, n goes upto $10^12$.
– Andrew Scott
1 hour ago
2
I think the point isn't so much that the greedy algorithm finds some sort of unique max. Indeed, in most cases it just finds one of many. To prove it, I'd start by noting that given any optimal solution $a≤b$ we can subtract enough from each decimal place of $a$ to make the corresponding place of $b$ equal to $9$ without changing the sum you want. For example, for $n=154$ we could have the solution $77,77$ or we could "move $2$ over from each slot" to get the equivalent solution $55,99$ which is what the greedy algorithm would find.
– lulu
1 hour ago
@lulu, Yes. I am sorry. Edited the question.
– Andrew Scott
1 hour ago
What is $n$ in the requirement $a+b=n$?
– 5xum
1 hour ago
What is $n$ in the requirement $a+b=n$?
– 5xum
1 hour ago
2
2
I assume $n=x$, no? As a small point, you say that you are allowing $b=n$ but that would make $a=0$ which you are not allowing. Do you mean to allow the pair $n+0=n$ or not?
– lulu
1 hour ago
I assume $n=x$, no? As a small point, you say that you are allowing $b=n$ but that would make $a=0$ which you are not allowing. Do you mean to allow the pair $n+0=n$ or not?
– lulu
1 hour ago
@5xum, n goes upto $10^12$.
– Andrew Scott
1 hour ago
@5xum, n goes upto $10^12$.
– Andrew Scott
1 hour ago
2
2
I think the point isn't so much that the greedy algorithm finds some sort of unique max. Indeed, in most cases it just finds one of many. To prove it, I'd start by noting that given any optimal solution $a≤b$ we can subtract enough from each decimal place of $a$ to make the corresponding place of $b$ equal to $9$ without changing the sum you want. For example, for $n=154$ we could have the solution $77,77$ or we could "move $2$ over from each slot" to get the equivalent solution $55,99$ which is what the greedy algorithm would find.
– lulu
1 hour ago
I think the point isn't so much that the greedy algorithm finds some sort of unique max. Indeed, in most cases it just finds one of many. To prove it, I'd start by noting that given any optimal solution $a≤b$ we can subtract enough from each decimal place of $a$ to make the corresponding place of $b$ equal to $9$ without changing the sum you want. For example, for $n=154$ we could have the solution $77,77$ or we could "move $2$ over from each slot" to get the equivalent solution $55,99$ which is what the greedy algorithm would find.
– lulu
1 hour ago
@lulu, Yes. I am sorry. Edited the question.
– Andrew Scott
1 hour ago
@lulu, Yes. I am sorry. Edited the question.
– Andrew Scott
1 hour ago
 |Â
show 2 more comments
2 Answers
2
active
oldest
votes
up vote
5
down vote
accepted
Show the following two statements (I guess they would be lemmas):
When adding $a+b$ the way you learn in school, if you get no carries, then $S(a+b)=S(a)+S(b)$
For each carry you get when adding $a+b$, the sum $S(a)+S(b)$ increases by $9$.
Together they mean that you want to have as many carries as you can. The greedy algorithm you describe gives you a carry into each column (except the 1's column, which is impossible anyways) and therefore gives you the max.
answered 1 hour ago
Arthur
103k798179
WOW. Thanks! :)
– Andrew Scott
1 hour ago
add a comment |Â
up vote
0
down vote
Elaborating on the process in lulu's comment:
Since there are only finitely many choices for $a,b$, an optimum must exist.
Consider all pairs $(a,b)$ with $a+b=n$ and $S(a)+S(b)=max$ and $ale b$.
$a=overlinea_1a_2ldots a_d$ and $b=overlineb_1b_2ldots b_d$ (with $b_1>0$, but possibly $a_1=0$). Among all such $(a,b)$, pick one that maximizes $S(a)$.
Suppose $a_k<9$ for some $k>1$.
If $b_k=0$, then there must be a (maximal) $j<k$ with $b_j>0$, for otherwise we'd have $b<a$. If we replace $a_k$ with $a_k+1$, $b_j$ with $b_j-1$ and $b_i$ with $9$ for $j<ile k$, with the numbers $a',b'$ obtained this way, we have $a'+b'=a+b=n$, but $S(a')+S(b')=S(a)+S(b)+9(k-j)$, constradicting maximality of $S(a)+S(b)$.
If $b_k>0$ we could increase $a_k$ and decrease $b_k$ by one, thereby achieving $a'+b'=a+b=n$, $S(a')+S(b')=S(a)+S(b)$, but $S(a')=S(a)+1$, contradicting the maximality of $S(a)$.
We conclude that there is a
maximizing $a$ with $ale b$ and $a_2=ldots=a_d=9$.
What can we gain if we drop the condition $ale b$?
If $a_1+b_1ge 9$, we can let $a_1'=9$ and $b_1'=a_1+b_1-9$, thereby making $a'$ consist only of $9$'s and apparently the largest number $le n$ of this form
If $a_1+b_1<9$, we can let $a_1'=0$ and $b_1'=a_1+b_1$, thereby making $a'$ consist only of $9$'s and apparently the largest number $le n$ of this form
In summary, the $a$ (and associated $b$) found by the greedy method is among the maximizers.
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
5
down vote
accepted
Show the following two statements (I guess they would be lemmas):
When adding $a+b$ the way you learn in school, if you get no carries, then $S(a+b)=S(a)+S(b)$
For each carry you get when adding $a+b$, the sum $S(a)+S(b)$ increases by $9$.
Together they mean that you want to have as many carries as you can. The greedy algorithm you describe gives you a carry into each column (except the 1's column, which is impossible anyways) and therefore gives you the max.
answered 1 hour ago
Arthur
103k798179
WOW. Thanks! :)
– Andrew Scott
1 hour ago
add a comment |Â
up vote
5
down vote
accepted
Show the following two statements (I guess they would be lemmas):
When adding $a+b$ the way you learn in school, if you get no carries, then $S(a+b)=S(a)+S(b)$
For each carry you get when adding $a+b$, the sum $S(a)+S(b)$ increases by $9$.
Together they mean that you want to have as many carries as you can. The greedy algorithm you describe gives you a carry into each column (except the 1's column, which is impossible anyways) and therefore gives you the max.
answered 1 hour ago
Arthur
103k798179
WOW. Thanks! :)
– Andrew Scott
1 hour ago
add a comment |Â
up vote
5
down vote
accepted
up vote
5
down vote
accepted
Show the following two statements (I guess they would be lemmas):
When adding $a+b$ the way you learn in school, if you get no carries, then $S(a+b)=S(a)+S(b)$
For each carry you get when adding $a+b$, the sum $S(a)+S(b)$ increases by $9$.
Together they mean that you want to have as many carries as you can. The greedy algorithm you describe gives you a carry into each column (except the 1's column, which is impossible anyways) and therefore gives you the max.
answered 1 hour ago
Arthur
103k798179
Show the following two statements (I guess they would be lemmas):
When adding $a+b$ the way you learn in school, if you get no carries, then $S(a+b)=S(a)+S(b)$
For each carry you get when adding $a+b$, the sum $S(a)+S(b)$ increases by $9$.
Together they mean that you want to have as many carries as you can. The greedy algorithm you describe gives you a carry into each column (except the 1's column, which is impossible anyways) and therefore gives you the max.
answered 1 hour ago
Arthur
103k798179
edited 1 hour ago
answered 1 hour ago
Arthur
103k798179
answered 1 hour ago
Arthur
103k798179
answered 1 hour ago
Arthur
103k798179
103k798179
WOW. Thanks! :)
– Andrew Scott
1 hour ago
add a comment |Â
WOW. Thanks! :)
– Andrew Scott
1 hour ago
WOW. Thanks! :)
– Andrew Scott
1 hour ago
WOW. Thanks! :)
– Andrew Scott
1 hour ago
add a comment |Â
up vote
0
down vote
Elaborating on the process in lulu's comment:
Since there are only finitely many choices for $a,b$, an optimum must exist.
Consider all pairs $(a,b)$ with $a+b=n$ and $S(a)+S(b)=max$ and $ale b$.
$a=overlinea_1a_2ldots a_d$ and $b=overlineb_1b_2ldots b_d$ (with $b_1>0$, but possibly $a_1=0$). Among all such $(a,b)$, pick one that maximizes $S(a)$.
Suppose $a_k<9$ for some $k>1$.
If $b_k=0$, then there must be a (maximal) $j<k$ with $b_j>0$, for otherwise we'd have $b<a$. If we replace $a_k$ with $a_k+1$, $b_j$ with $b_j-1$ and $b_i$ with $9$ for $j<ile k$, with the numbers $a',b'$ obtained this way, we have $a'+b'=a+b=n$, but $S(a')+S(b')=S(a)+S(b)+9(k-j)$, constradicting maximality of $S(a)+S(b)$.
If $b_k>0$ we could increase $a_k$ and decrease $b_k$ by one, thereby achieving $a'+b'=a+b=n$, $S(a')+S(b')=S(a)+S(b)$, but $S(a')=S(a)+1$, contradicting the maximality of $S(a)$.
We conclude that there is a
maximizing $a$ with $ale b$ and $a_2=ldots=a_d=9$.
What can we gain if we drop the condition $ale b$?
If $a_1+b_1ge 9$, we can let $a_1'=9$ and $b_1'=a_1+b_1-9$, thereby making $a'$ consist only of $9$'s and apparently the largest number $le n$ of this form
If $a_1+b_1<9$, we can let $a_1'=0$ and $b_1'=a_1+b_1$, thereby making $a'$ consist only of $9$'s and apparently the largest number $le n$ of this form
In summary, the $a$ (and associated $b$) found by the greedy method is among the maximizers.
add a comment |Â
up vote
0
down vote
Elaborating on the process in lulu's comment:
Since there are only finitely many choices for $a,b$, an optimum must exist.
Consider all pairs $(a,b)$ with $a+b=n$ and $S(a)+S(b)=max$ and $ale b$.
$a=overlinea_1a_2ldots a_d$ and $b=overlineb_1b_2ldots b_d$ (with $b_1>0$, but possibly $a_1=0$). Among all such $(a,b)$, pick one that maximizes $S(a)$.
Suppose $a_k<9$ for some $k>1$.
If $b_k=0$, then there must be a (maximal) $j<k$ with $b_j>0$, for otherwise we'd have $b<a$. If we replace $a_k$ with $a_k+1$, $b_j$ with $b_j-1$ and $b_i$ with $9$ for $j<ile k$, with the numbers $a',b'$ obtained this way, we have $a'+b'=a+b=n$, but $S(a')+S(b')=S(a)+S(b)+9(k-j)$, constradicting maximality of $S(a)+S(b)$.
If $b_k>0$ we could increase $a_k$ and decrease $b_k$ by one, thereby achieving $a'+b'=a+b=n$, $S(a')+S(b')=S(a)+S(b)$, but $S(a')=S(a)+1$, contradicting the maximality of $S(a)$.
We conclude that there is a
maximizing $a$ with $ale b$ and $a_2=ldots=a_d=9$.
What can we gain if we drop the condition $ale b$?
If $a_1+b_1ge 9$, we can let $a_1'=9$ and $b_1'=a_1+b_1-9$, thereby making $a'$ consist only of $9$'s and apparently the largest number $le n$ of this form
If $a_1+b_1<9$, we can let $a_1'=0$ and $b_1'=a_1+b_1$, thereby making $a'$ consist only of $9$'s and apparently the largest number $le n$ of this form
In summary, the $a$ (and associated $b$) found by the greedy method is among the maximizers.
add a comment |Â
up vote
0
down vote
up vote
0
down vote
Elaborating on the process in lulu's comment:
Since there are only finitely many choices for $a,b$, an optimum must exist.
Consider all pairs $(a,b)$ with $a+b=n$ and $S(a)+S(b)=max$ and $ale b$.
$a=overlinea_1a_2ldots a_d$ and $b=overlineb_1b_2ldots b_d$ (with $b_1>0$, but possibly $a_1=0$). Among all such $(a,b)$, pick one that maximizes $S(a)$.
Suppose $a_k<9$ for some $k>1$.
If $b_k=0$, then there must be a (maximal) $j<k$ with $b_j>0$, for otherwise we'd have $b<a$. If we replace $a_k$ with $a_k+1$, $b_j$ with $b_j-1$ and $b_i$ with $9$ for $j<ile k$, with the numbers $a',b'$ obtained this way, we have $a'+b'=a+b=n$, but $S(a')+S(b')=S(a)+S(b)+9(k-j)$, constradicting maximality of $S(a)+S(b)$.
If $b_k>0$ we could increase $a_k$ and decrease $b_k$ by one, thereby achieving $a'+b'=a+b=n$, $S(a')+S(b')=S(a)+S(b)$, but $S(a')=S(a)+1$, contradicting the maximality of $S(a)$.
We conclude that there is a
maximizing $a$ with $ale b$ and $a_2=ldots=a_d=9$.
What can we gain if we drop the condition $ale b$?
If $a_1+b_1ge 9$, we can let $a_1'=9$ and $b_1'=a_1+b_1-9$, thereby making $a'$ consist only of $9$'s and apparently the largest number $le n$ of this form
If $a_1+b_1<9$, we can let $a_1'=0$ and $b_1'=a_1+b_1$, thereby making $a'$ consist only of $9$'s and apparently the largest number $le n$ of this form
In summary, the $a$ (and associated $b$) found by the greedy method is among the maximizers.
Elaborating on the process in lulu's comment:
Since there are only finitely many choices for $a,b$, an optimum must exist.
Consider all pairs $(a,b)$ with $a+b=n$ and $S(a)+S(b)=max$ and $ale b$.
$a=overlinea_1a_2ldots a_d$ and $b=overlineb_1b_2ldots b_d$ (with $b_1>0$, but possibly $a_1=0$). Among all such $(a,b)$, pick one that maximizes $S(a)$.
Suppose $a_k<9$ for some $k>1$.
If $b_k=0$, then there must be a (maximal) $j<k$ with $b_j>0$, for otherwise we'd have $b<a$. If we replace $a_k$ with $a_k+1$, $b_j$ with $b_j-1$ and $b_i$ with $9$ for $j<ile k$, with the numbers $a',b'$ obtained this way, we have $a'+b'=a+b=n$, but $S(a')+S(b')=S(a)+S(b)+9(k-j)$, constradicting maximality of $S(a)+S(b)$.
If $b_k>0$ we could increase $a_k$ and decrease $b_k$ by one, thereby achieving $a'+b'=a+b=n$, $S(a')+S(b')=S(a)+S(b)$, but $S(a')=S(a)+1$, contradicting the maximality of $S(a)$.
We conclude that there is a
maximizing $a$ with $ale b$ and $a_2=ldots=a_d=9$.
What can we gain if we drop the condition $ale b$?
If $a_1+b_1ge 9$, we can let $a_1'=9$ and $b_1'=a_1+b_1-9$, thereby making $a'$ consist only of $9$'s and apparently the largest number $le n$ of this form
If $a_1+b_1<9$, we can let $a_1'=0$ and $b_1'=a_1+b_1$, thereby making $a'$ consist only of $9$'s and apparently the largest number $le n$ of this form
In summary, the $a$ (and associated $b$) found by the greedy method is among the maximizers.
answered 20 mins ago
community wiki
Hagen von Eitzen
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2943253%2fhow-to-come-up-with-a-greedy-solution-and-prove-it%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
What is $n$ in the requirement $a+b=n$?
– 5xum
1 hour ago
2
I assume $n=x$, no? As a small point, you say that you are allowing $b=n$ but that would make $a=0$ which you are not allowing. Do you mean to allow the pair $n+0=n$ or not?
– lulu
1 hour ago
@5xum, n goes upto $10^12$.
– Andrew Scott
1 hour ago
2
I think the point isn't so much that the greedy algorithm finds some sort of unique max. Indeed, in most cases it just finds one of many. To prove it, I'd start by noting that given any optimal solution $a≤b$ we can subtract enough from each decimal place of $a$ to make the corresponding place of $b$ equal to $9$ without changing the sum you want. For example, for $n=154$ we could have the solution $77,77$ or we could "move $2$ over from each slot" to get the equivalent solution $55,99$ which is what the greedy algorithm would find.
– lulu
1 hour ago
@lulu, Yes. I am sorry. Edited the question.
– Andrew Scott
1 hour ago