$a,b,c$ are digits. İf $a+2b+3c=40$ then what is the largest value for $a+b+c$?

Question

I am finding it hard to understand the method and the logic behind this.

I read that we have to give the one with the smallest coefficient the biggest value ,why is this . ?

Answer 1

I read that we have to give the one with the smallest coefficient the biggest value; why is this?

Let's say you are going to market to buy fish. Some fish cost \$1, some cost \$2, others cost \$3. You have \$40 and want to buy the most fish. How many of each should you buy? Clearly you should buy 40 of the one-dollar fish. You could swap two of the one-dollar fish for one two-dollar fish; that would result in the same amount paid, but would result in one less fish.

Answer 2

Assume you have found an optimal triple $(a,b,c)$ with $a,b,c\in\{0,\ldots,9\}$. Note that $a+2b+3c=40$ implies $3c=40-a-2b\ge 40-9-18=13$ and so $c>4$. Also, $2b=40-a-3c\ge 40-9-27=4$ and so $b\ge 2$.

If $a<8$ in our optimal solution, then (as $b\ge 2$ and so $b-1$ is still a digit), then $(a+2,b-1,c)$ is a valid triple and has larger target sum, contradicting optimality. We conclude that $a\ge 8$ in any optimal triple.

Similarly, if $b<7$, then $(a,b+3,c-2)$ is an improvement. We conclude that $b\ge 7$.

In particular, $a$ and $b$ are not far apart: $|a-b|\le 2$. then from $a-b=40-3b-3c=1+3\cdot(13-b-c)$, we conclude that $a-b=1$ and also that $13-b-c=0$. This makes $a+b+c=13+a$, so we certainly want to make $a$ as large as possible, namely $a=9$, leading to the maximal target sum $a+b+c=13+a=22$, where by the way $b=a-1=8$ and $c=13-b=5$.