Question 7. (10 points) Cutting down costs Given a list of positive integers ai,

Question

Question 7. (10 points) Cutting down costs Given a list of positive integers ai, a2, .. , an, we can perform the following operation on the list any number of times . If a > aj, then a, +a - aj What is the minimum value of ? 1 ai that we can achieve in this manner? E g, for the list 4,2,4 We can do the following operations ?? = ??-?? to get 2,2,2 As we can't reduce the sum any further the minimum is 6 Note 7.1. For this question we are not required to give an algorithm. Instead we need to just find the minimum possible value of this sum We still need to prove our claim about the value that we suggest Hint 7.1. Try to find similarities to Euclids algorithm for finding the GCD.

Explanation / Answer

Here let us consider two numbers, a1 and a2 .

Then we perform the following operation as mentioned above:

if a1 > a2 : a1 = a1 - a2

else if a2>a1 : a2 = a2 - a1

we keep doing this. Finally the resulting value will be equal i.e. we will reach a point where a1 = a2. We cannot proceed forward from that. From Euclid's algorithm we can say that this final integer is the GCD of initial a1 and a2 i.e. in the final stage,  a1 = a2 = GCD of the initial values of a1 and a2.

Now for a series of numbers a1, a2, ...., ai, ai+1, ......, an. First we start with a1 and a2 and reduce them to the GCD of intial a1 and a2. Let this number be agcd12. Then we consider agcd12 and a3. We repeat the procedure and these two values reduces to GCD of initial values of agcd12 and a3. Let this value be agcd123. Then we consider agcd123 and a4 and in a similar way get agcd1234. Continuing in this way, finally we get all the values in the series equal to agcd123..n.

Thus finally all the values in the series is equal to agcd123..n and hence the sum of the series is = n * agcd123..n = n* GCD of all the numbers in the series.

For eg. for the series 4,2,4, the GCD of 4,2,4 is 2. Hence minimum sum of the series = 3* GCD of 4,2,4 = 3*2 = 6.

Therefore, the minimum value of the sum of the seroes = number of elements in the series * GCD of numbers in the series.

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.