Maximize the following sum

Question

Let $a, b, c, d, e$ be nonnegative integers such that $625a + 250b + 100c + 40d + 16e = 15^3$ . What is the maximum possible value of $a + b + c + d + e$?

Quick arithmetic gives: $15^3 = 3375$.

$625a + 250b + 100c + 40d + 16e = 3375$ is the given.

The idea is to maximize $e$ because the coefficient $16$ will make $e$ very large. $\lfloor 3375/16 \rfloor = 210$. But that is impossible.

Please do not give a full answer, only hints! Thanks!

Answer 1

Brute Force:

This can be posed as a linear program. Renaming the unknowns to $x_i$, it is: $$ \begin{array}{ll} \max & c^\top x \\ \mbox{w.r.t.} & a^\top x = b \\ & 0 \le x \\ & x_i \in \mathbb{Z} \end{array} $$ where $$ c = (1,1,1,1,1)^\top \\ x = (x_1, x_2, x_3, x_4, x_5)^\top \\ a = (625, 250, 100, 40, 16)^\top \\ b = 15^3 $$ So it can be solved by the well-known algorithms and software.

Using R and the lpSolveAPI package:

R is a popular maths package. If not done yet, the lpSolveAPI package must be installed:

> install.packages("lpSolveAPI")

Then the library must be loaded:

> library(lpSolveAPI)

We then create the model for 5 unknowns, add the objective function and constraints:

> lprec <- make.lp(0,5)
> set.objfn(lprec,c(1,1,1,1,1))
> add.constraint(lprec, c(625,250,100,40,16), "=", 15**3)

Standard sense is to minimize, but we want to maximize:

> lp.control(lprec, sense= "maximize")

Now let us have a look:

> lprec

    Model name: 
                C1    C2    C3    C4    C5         
    Maximize     1     1     1     1     1         
    R1         625   250   100    40    16  =  3375
    Kind       Std   Std   Std   Std   Std         
    Type      Real  Real  Real  Real  Real         
    Upper      Inf   Inf   Inf   Inf   Inf         
    Lower        0     0     0     0     0   

Ah, the restrictions of the unknowns to integer are missing:

> set.type(lprec,1, "integer")
> set.type(lprec,2, "integer")
> set.type(lprec,3, "integer")
> set.type(lprec,4, "integer")
> set.type(lprec,5, "integer")
> lprec

Model name: 
           C1   C2   C3   C4   C5         
Maximize    1    1    1    1    1         
R1        625  250  100   40   16  =  3375
Kind      Std  Std  Std  Std  Std         
Type      Int  Int  Int  Int  Int         
Upper     Inf  Inf  Inf  Inf  Inf         
Lower       0    0    0    0    0     

Not the bounds are set for non-negative solutions. Now solve and check the results:

> solve(lprec)
[1] 0
> get.objective(lprec)

Spoiler: maximum (put mouse over field to get the hidden information)

[1] 153

> get.variables(lprec)

Spoiler: solution vector

[1] 1 1 1 0 150

What is left is how to solve this clever without machine.

What does a lp solver do?

(Large image version)

The image shows the problem reduced to two unknowns. The constraint $a^\top x = b$ is a hyperplane (dimension $n-1$), here the dark blue line.

Together with the constraints $0 \ge x$ the feasible solutions (those that honor the constraints) are within the green triangle. As we are looking for integer solutions they are the integer grid points within the triangle.

The objective function can attain various values $s$ $$ c^\top x = s $$ This is another hyperplane, dependent on $s$. Shown are the lines for $s = 5$, $10$, $15$ and $20$.

We find the maximum by pulling that hyperplane as high (regarding $s$ value) as possible, while still touching one of the feasible solutions from the grid within the triangle.

In the continous case we would just need to inspect the points of the triangle, with the maximum attained at the top point.

In the discrete case, e.g. if the coordinate grid cross points within the triangle were the feasible solutions, we had four feasible solutions and a maximum at $(0, 10)$ with value $10$.

I do not know how the solvers are implemented for discrete unknowns. I would naively inspect all grid points within the triangle, closest to the boundary. But there might be smarter approaches.

Answer 2

Instead of maximizing e, try minimizing a.

The first guess would be a = 0. This gives:

$$250b + 100c + 40d + 16e = 3375$$

This is clearly impossible, because the left hand side is even while the right hand side is odd. So Try $a = 1$ instead:

$$250b + 100c + 40d + 16e = 2750$$

Now we see that all terms are divisible by $2$. Let's divide by $2$:

$$125b + 50c + 20d + 8e = 1375$$

Now, we try to minimize $b$. By the same logic as before, $b = 0$ won't work. So try $b = 1$:

$$50c + 20d + 8e = 1250$$

And again dividing by $2$ gives:

$$25c + 10d + 4e = 625$$

Since you said you didn't want a full answer, I'll leave it there for you to finish.

Answer 3

Hint: You can use divisibility considerations to simplify the problem a lot, so that in the end the system is easily solved. The final solution is brute force, though you may not find it as brutal.

For more detailed steps check below:

---

'To start, let us simplify the constraint. From $625a + 250b + 100c + 40d + 16e = 15^3$, it is evident that $a$ must be odd and $5 \mid e$. So let $a = 2p+1, e = 5q$ for non-negative integers $p, q$. Now the constraint is $25b+10c+4d+125p+8q = 275$.

It is evident that $5 \mid (d+2q)$, so let $d = 5r-2q$, where $r \ge \frac25q$ is an integer. With this we have $5b+2c+25p+4r=55$

Similarly, $c=5s-2r$ where $s \ge \frac25r$ is integer, to get the constraint finally as $b=11-5p-2s$. Now $b \ge 0 \implies 11 \ge 5p+2s$, which reasonably contains the problem.

Now the objective function is to maximise $12+3(q+r+s-p)$. It is clear we need to select $p=0$ and maximum possible $s, r, q$ in that order, to get $s = 5, r=12, q=30$.

Now plug in these to get $a, b, c, d, e$ and the maximum desired.