Given there are 2018 1s, as shown below: 2 0 1 8 1 s 1 1 1 1 ...... 1 1 that you are allowed to add pluses between the 1s. What is the maximum number of pluses can be added so that the expression above equals to 8102?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
This is a matter of solving the linear programming problem to maximize a + b + c + d − 1 for nonnegative integers subject to the constraints 1 1 1 1 a + 1 1 1 b + 1 1 c + d = 8 1 0 2 4 a + 3 b + 2 c + d = 2 0 1 8 the maximum value of 1 9 9 1 is achieved with a = 5 , b = 5 , c = 1 , d = 1 9 8 1 .
how do I know that the maximum value
Log in to reply
Try using the Simplex Method for solving such problems. There are plenty of online implementations to be found.
how to calculate a, b, and c ?
5 ∗ 1 1 1 1 + 4 ∗ 1 1 1 + 3 ∗ 1 1 + 1 9 8 0 = 8 0 1 2 ,
I got, a = 5 , b = 5 , c = 1 , d = 1 9 8 1 .
Why maximize a + b + c + d? That's not the right target function. The solution you have gives a + b + c + d - 1 = 1991. If I change b to 4 and c to 13 I get a + b + c + d - 1 = 2000. But I have many fewer '+' symbols.
What you want to do is miinimize 3 a + 2 b + c.
Log in to reply
This is wrong. We are creating a + b + c + d numbers, namely a copies of 1 1 1 1 , b copies of 1 1 1 , c copies of 1 1 and d copies of 1 .
Log in to reply
I've realized you're not wrong and I'm not wrong. We're just counting the number of "+" symbols diferently. My objection is incorrect because I didn't account for the change to d. But with the constraints we have, maximizing a + b + c + d is equivalent to minimizing 3a + 2b + c.
Log in to reply
@Richard Desper – Yes, Number of pluses = a + b + c + d − 1 = 2 0 1 7 − 3 a − 2 b − c
2018* copies of 1. ;)
Formulation: Find values of ( a , b , c , d ) such that a ∗ 1 1 1 1 + b ∗ 1 1 1 + c ∗ 1 1 1 + d = 8 1 0 2 , 4 ∗ a + 3 ∗ b + 2 ∗ c + d = 2 0 1 8 , and ( 3 ∗ a + 2 ∗ b + c ) is minimized.
Let us approach the problem from this perspective:
If we start with
d
=
2
0
1
8
, we have
2
0
1
7
"
+
" symbols but the sum is only
2
1
0
8
.
If we change a "
1
+
1
" to an
1
1
, we have one fewer "
+
" symbol, but the sum increases by
9
.
If we change "
1
+
1
+
1
" to
1
1
1
, we have two fewer "
+
" symbols, and the sum increases by
9
9
If we change "
1
+
1
+
1
+
1
" to
1
1
1
1
, we have three fewer "
+
" symbols, and the sum increases by
9
9
9
.
So how many " + " symbols do we remove going from d = 2 0 1 8 to the correct solution? Well, for each " 1 1 1 1 " we remove 3 " + " symbols, and for each " 1 1 1 " we remove 2 " + " symbols, while for each " 1 1 " we remove 1 " + " symbol. Thus the target function is 3 a + 2 b + c .
Our heuristic is to maximize a , then maximize b , then maximize c . Each " 1 + 1 + 1 + 1 → 1 1 1 1 " transition increases the sum by an average of 3 3 3 per " + " removed, while each " 1 + 1 + 1 → 1 1 1 " transition increases the sum by 4 9 . 5 per " + " removed, and each " 1 + 1 → 1 1 " transition only increases the sum by 9 per " + " removed.
Now note that
a
<
6
, because
6
6
6
6
+
1
9
9
4
=
8
6
6
0
, which is too much.
If we let
a
=
5
,
then
b
<
6
by a similar calculation.
Finally, observe that if a = 5 and b = 5 , then if we let c = 1 and d = 1 9 8 1 , we have a solution. These values of a , b , and c require removing only 2 6 " + " signs. And no other sum that removes only 2 6 " + " signs will achieve the same sum.
Problem Loading...
Note Loading...
Set Loading...
As a starting approach one can try to maximise the number of 1 's in our expression: 1 1 1 1 × a + 1 1 1 × b + 1 1 × c + 1 × d = 8 1 0 2 .
It is most efficient to use the most 1 1 1 1 's as possible. Hence we want to maximise a s.t. 8 1 0 2 − 1 1 1 1 × a ≥ 2 0 1 8 − 4 a . This gives a = 5 .
8 1 0 2 − 5 5 5 5 = 2 5 4 7 .
We can continue by maximising b s.t. 2 5 4 7 − 1 1 1 × b ≥ 2 0 1 8 − 2 0 − 3 b . This gives b = 5 .
8 1 0 2 − 5 5 5 5 − 5 5 5 = 1 9 9 2 .
We now look for c s.t. 1 9 9 2 − 1 1 × c = 2 0 1 8 − 2 0 − 1 5 − 2 c , and c = 1 satisfies this.
Currently we have 1 1 1 1 × 5 + 1 1 1 × 5 + 1 1 × 1 + 1 × 1 9 8 1 = 8 1 0 2 . With 1 9 9 1 ( = a + b + c + d − 1 ) pluses.
If a = 4 and d > 1 9 8 1 , we have < 2 0 1 8 − 1 9 8 1 − 1 6 = 2 1 1's left. So b < 7 and we can't reach 8 1 0 2 . Similarly if a = 5 , b = 4 , d > 1 9 8 1 , we have < 2 0 1 8 − 1 9 8 1 − 1 2 − 2 0 = 5 , so c < 2 and we can't reach 8 1 0 2 .
One should note that there is a similar solutions for years 2 0 1 3 to 2 0 1 9 . Assuming we are summing the 1 's to equal the year reversed. All have 1 9 9 1 pluses.
E.g. 1 1 1 1 × 6 + 1 1 1 × 4 + 1 1 × 1 + 1 × 1 9 8 1 = 9 1 0 2 as we swapped 1 1 1 for 1 1 1 1 which gains 1 0 0 0 and uses one more 1 . Likewise if we swap 1 1 1 1 's for 1 1 1 we can do earlier years:
1 1 1 1 × 0 + 1 1 1 × 1 0 + 1 1 × 1 + 1 × 1 9 8 1 = 3 1 0 2 .
2 1 0 2 is possible. We can't have any 1 1 1 1 or 1 1 1 and 2 1 0 2 = 1 1 c + ( 2 0 1 2 − 2 c ) , so 2 0 1 2 + 9 c = 2 1 0 2 .
c = 1 0 and 2 1 0 2 = 1 1 × 1 0 + 1 × 1 9 9 2 with 2 0 0 1 pluses.