8. Let $x, y$ be nonnegative integers such that $x+2 y$ is a multiple of $5, x+y$ is a multiple of 3 and $2 x+y \geq 99$. Find the minimum possible value of $7 x+5 y$.
設 $x 、 y$ 少非負整數, 使得 $x+2 y$ 爲 5 的倍數、 $x+y$ 絧 3 的倍數, 且 $2 x+y \geq 99$ 。求 $7 x+5 y$ 的最小可能値。
8. 366
8. Let $x+2 y=5 a$ and $x+y=3 b$. Solving for $x, y$ in terms of $a$ and $b$, we have $x=6 b-5 a$ and $y=5 a-3 b$. Also, $2 x+y=9 b-5 a$ and $7 x+5 y=27 b-10 a$. Hence the problem becomes minimising $27 b-10 a$ over non-negative integers $a, b$ satisfying $6 b \geq 5 a \geq 3 b$ and $9 b-5 a \geq 99$.
Clearly standard linear programming techniques will solve the problem. We present a purely algebraic solution below. We first establish lower bounds on $a$ and $b$ : $9 b \geq 5 a+99 \geq 3 b+99$ gives $b \geq 17$, while $5 a \geq 3 b \geq 3(17)$ gives $a \geq 11$. Next $9 b \geq 5 a+99 \geq 5(11)+99$ gives $b \geq 18$. We consider two cases.
- If $b=18$, then we have $5 a \leq 9 b-99=9(18)-99=63$, which gives $a \leq 12$ and hence $27 b-10 a \geq 27(18)-10(12)=366$. We check that $(a, b)=(12,18)$ satisfies all conditions with $27 b-10 a=366$.
- If $b>18$, then $27 b-10 a=9 b+2(9 b-5 a) \geq 9(19)+2(99)=369$.
Combining the two cases, we see that the answer is 366 .