A vending machine cannot return coins as change, but only five-cent and eight-cent stamps.
For a particular k, though, we can prove by induction that the machine can make every number of cents that is k or greater.
What is the smallest value of k for which we can do this?
My answer is 9 but I was told this is not correct. My understanding is that the machine can only make change for numbers greater than 7.
I am looking for a confirmation.
On
The machine certainly can't make change of 9 cents from 5c and 8c stamps.
Induction...
Let $k = 5a + 8b$ for any integers $a,b$ including negatives
then $k+1 = 5a + 8b + (16 - 15) = 5(a-3) + 8(b+2) = 5a' + 8b'$
clearly $0 = 5 \cdot 0 + 8 \cdot 0$ and $1 = 5 \cdot -3 + 8 \cdot 2$, so the proof is complete.
Minimal $k$ (and a realistic vending machine) requires both $a$ and $b$ to be non-negative simultaneously. The first time this occurs is when $k=5 \cdot 4 + 8 \cdot 1 = 28$
You can quickly check that $9$ can not be correct, because there is no way it could output $11$.
It also can't output $27$. However it can return $\underbrace{28, 29, 30, 31, 32}_{\text{5 consecutive numbers}}$ and thus also $33 = 28 + 5, 34 = 29 + 5, \ldots$.
$$ \begin{array}{c|cccc} 0 & 5 & 10 & 15 & 20 & 25 & \color{red}{30} \\ \hline 8 & 13 & 18 & 23 & \color{red}{28} & 33 & 38 \\ 16 & 21 & 26 & \color{red}{31} & 36 & 41 & 46 \\ 24 & \color{red}{29} & 34 & 39 & 44 & 49 & 54 \\ \color{red}{32} & 37 & 42 & 47 & 52 & 57 & 62 \end{array} $$