In a chocolate store, there are boxes with 8, 9, and 10 chocolates. Note that some quantities of chocolates cannot be bought exactly, such as, for example, 12 chocolates.

a) Find another quantity of chocolates that cannot be bought.

b) Verify that every number greater than 56 can be written in the form $8x + 9y$ with $x$ and $y$ being non-negative integers.

c) What is the largest quantity of chocolate units that we cannot buy exactly in this store?
Solution

a) It is not possible to buy 15 chocolates, because $15>10$ and the sum of the quantities of any two boxes is greater than 15

b) Initially note that the numbers from 57 to 64 can be written in the form $8 x+9 y$:

| $x$ | $y$ | $8 x+9 y$ |
| :---: | :---: | :---: |
| 9 | 1 | 57 |
| 5 | 2 | 58 |
| 4 | 3 | 59 |
| 3 | 4 | 60 |
| 2 | 5 | 61 |
| 1 | 8 | 62 |
| 0 | 7 | 63 |
| 8 | 0 | 64 |

By adding 8 units to each of these representations, we can write all the integers in the interval [65,72] in the form $8 x+9 y$. For example, since $60=8 \cdot 3+9 \cdot 4$, it follows that $68=8 \cdot 4+9 \cdot 4$. By successively adding 8, we can conclude that all integers in the intervals

$$
[73,80],[81,88],[89,96], \ldots
$$

can be written in the form $8 x+9 y$, with $x$ and $y$ non-negative integers. Thus, all integers greater than 56 can be written in the form $8 x+9 y$ with $x$ and $y$ non-negative integers.
c) The quantities of chocolates that can be bought are the numbers of the form $8 x+9 y+10 z$, with $x, y$ and $z$ non-negative integers representing the quantities of each type of box. A number that can be written in the form $8 x+9 y$ in particular can also be written in the form $8 x+9 y+10 z$. Therefore, in light of the previous item, it is sufficient to analyze the numbers less than 56 to determine which is the largest of them that cannot be an admissible quantity of chocolates bought in the store. The table below indicates how to write all the numbers from 32 to 40 in the form $8 x+9 z+10 z$:

| $x$ | $y$ | $z$ | $8 x+9 y+10 z$ |
| :---: | :---: | :---: | :---: |
| 4 | 0 | 0 | 32 |
| 3 | 1 | 0 | 33 |
| 3 | 0 | 1 | 34 |
| 2 | 1 | 1 | 35 |
| 2 | 0 | 2 | 36 |
| 1 | 1 | 2 | 37 |
| 1 | 0 | 3 | 38 |
| 0 | 1 | 3 | 39 |
| 5 | 0 | 0 | 40 |

By adding 8 units to each of these representations, we can write all the numbers from 40 to 48. Repeating this process, we can write all the integers from 48 to 56 in the form $8 x+9 y+10 z$, with $x, y$ and $z$ non-negative integers. To conclude that 31 is the largest quantity of chocolate that cannot be bought in the store, we need to verify that there do not exist non-negative integers $x, y$ and $z$ such that

$$
8 x+9 y+10 z=31
$$

If such integers existed, since 31 is odd and 8 and 10 are even, we must have $y \neq 0$. Thus $y=3$ or $y=1$. In the first case, we would have $8 x+10 z=4$, which clearly has no solution in non-negative integers. In the second case, we would have $8 x+10 z=22$, or $4 x+5 z=11$. For $z=0, z=1$ and $z=2$, we should have $4 x=11, 4 x=6$ and $4 x=1$. Since none of these equations have solutions in integers, we can conclude that the equation (2) has no solution in non-negative integers.