Find the minimum number of instructions

Question

Here, I need some help with solving question number 2. The statement of the question is huge and so I refrained from typing it. This is last year's ZIO paper.

So, I thought that rather than vanishing bacterias and then again increasing it, we could keep $K$ bacterias as it is and decrease the number of instructions $A, B, C$ by 1 each. Then we can try to form the rest of the bacterias $i.e (N-K)$ using the 'modified' instructions.

I tried but cannot reach $N$ and I also need to develop a generalized algorithm so that all the test cases are solved easily. Thanks in advance.

This is not an ongoing test.

Answer 1

All right, for part a, you start with 23 amoebas and need to finish with 114 for an increase of 91. A increases the number of amoebas by 6, B by 11, and C by 15. So you have the equation $6a+11b+15c=91$. Considering this equation mod 3 yields $$2b\equiv1\pmod3,b\equiv2\pmod3$$. If $b=3k+2$, our equation becomes

$$6a+33k+22+15c=91$$ $$6a+33k+15c=69$$ $$2a+11k+5c=23$$

$k\ge2$ yields no solutions, giving 2 possibilities. $2a+5c=23$ gives a solution of $a=4,c=3$ for a total of 9 instructions. If $k=1$, we have $b=5$ and $2a+5c=12$, yielding $a=1,c=2$. This has $8$ instructions, the best we can do.

Part b might be easier. Our equation is $6a+14b+15c=67$. We quickly get $c\equiv1\pmod2$ and $b\equiv2\pmod3$. Substituting as before,

$$6a+42k_1+28+30k_2+15=67$$ $$6a+42k_1+30k_2=24$$

Our k's are obviously both $0$, yielding $a=4,b=2,c=1$ for a total of $7$ instructions.

This method does not work as well on part c as all 3 coefficients are coprime. Our equation is $8a+11b+25c=128$. The best option may be to check all values of $c$, then checking mod 8. If $c=0$, we have $b\equiv0\pmod8$. Letting $b$ be as high as possible, we get $b=8,a=5$ for 13 instructions. If $c=1,8a+11b=103,3b\equiv7\pmod8$. Multiplying by 3 gives $b\equiv 5\pmod8$. This gives $(a,b,c)=(6,5,1)$ for 12 instructions. If $c=2,8a+11b=78,3b\equiv6\pmod8,b\equiv2\pmod8$ for $(7,2,2)$:$11$ instructions. If $c=3,8a+11b=53,3b\equiv5\pmod8,b\equiv7\pmod8$: no solution. Finally, if $c=4,8a+11b=28$ which again has no solutions. The optimal solution is $a=7,b=c=2$.

Answer 2

If $n(A), n(B), n(C)$ are the number of times instructions $A, B, C$ are used respectivly, the answers are

(a) $n(A) = 1, n(B) = 5, n(C) = 2$

(b) $n(A) = 4, n(B) = 2, n(C) = 1$

(c) $n(A) = 7, n(B) = 2, n(C) = 2$

The final answer for each one is the sum of the instructions and the posted solution is in agreement with the above.

Edit

Sketch of algorithm using (a) as example:

Total amoebas to add is $91$. Amoebas added by each instruction is $A=6, B=11, C=15$. Maximum number of times the largest (i.e. $C$) can be used is $6$.

Trying $C$ a total of $6$ times gives $6 \times 15 = 90$ amoebas, resulting in remainder $91 - 90 = 1$ amoebas. Can $1$ amoeba be made by a combination of $A$ and $B$? No.

Then try $C$ a total of $5$ times, giving remainder $16$. Can $16$ be made by a combination of $A$ and $B$? No.

Then try $4$ giving remainder $31$. Can $31$ be made by a combination of $A$ and $B$? No.

Then try $3$ giving remainder $46$. Can $46$ be made by a combination of $A$ and $B$? Yes! $n(A) = 4, n(B)=2, n(C) = 3$. This gives a total of $9$ instructions, but we don't know if this is the minimum number of instructions, so we continue.

Then try $2$ giving remainder $61$. Can $61$ be made by a combination of $A$ and $B$? Yes! $n(A) = 1, n(B)=5, n(C) = 2$. This gives a total of $8$ instructions, but we don't know if this is the minimum number of instructions, so we continue.

And so on. The way to determine if a remainder can be made by a combination of $A$ and $B$, is to use the same procedure as I just outlined but with the largest now being $B$ instead of $C$.