## Task 29/76

For the transport of 416 people, buses with 7, 21, and 31 seats are available. The transport is to be carried out with the fewest number of trips, with no seat left empty. How many trips should each bus make?
We denote with $x, y$ and $z$ the number of trips the bus with 7, 21, and 31 seats must perform, respectively. Then the following relationships apply:

$$
7 x+21 y+31 z=416 \quad ; \quad x+y+z \Rightarrow \min \quad ; \quad x ; y ; z \in N
$$

If we divide the equation by 7, we get

$$
x+3 y+4 z+\frac{3}{7} z=59+\frac{3}{7}
$$

From this, it immediately follows: To ensure no seat is left empty, $z \equiv 1(\bmod 7)$ must hold, i.e., $z=7 k+1$ with $k \in N$. Substituting this into the equation, we obtain after equivalent transformation $x+3 y+31 k=55$.

Obviously, $k=0$ would not lead to the minimum for the sum $x+y+z$. Therefore, $k=1, z=8$. This results in $x+3 y=24$, from which it is immediately clear that for $x=0, y=8$ the minimum for the sum is achieved.

Thus, 8 trips each are required with the buses for 21 and 31 people, and the bus for 7 people is not used.