5. At the ceremony marking the City Day, a tribune was set up where the seats were properly arranged in rows and columns (the number of seats in all rows is the same, the number of seats in all columns is the same). Each spectator has either a cap or a hat on their head. The mayor noticed that in each row there are exactly 8 spectators with caps, and in each column there are exactly 9 spectators with hats. There are a total of 12 empty seats on the tribune.

a) What is the minimum number of seats that can be on the tribune?

b) Show an example of a seating arrangement that meets the conditions of the problem.
## Solution.

a) Let $a$ be the number of rows, and $b$ be the number of columns of the stand.

The total number of seats on the stand is $a b$, the total number of spectators with caps is $8 a$, and the total number of spectators with hats is $9 b$. We have

$$
a b=8 a+9 b+12
$$

Now,

$$
\begin{gathered}
a b-8 a=9 b+12 \\
a(b-8)=9 b+12 \\
a=\frac{9 b+12}{b-8}=\frac{9(b-8)+84}{b+8}=9+\frac{84}{b-8}
\end{gathered}
$$

The divisors of the number 84 are: $1,2,3,4,6,7,12,14,21,28,42,84$, and these are the possibilities for the number $b-8$.

For each divisor, we calculate the corresponding values for $b$, $a$, and $a b$.

| $b-8$ | $b$ | $\frac{84}{b-8}$ | $a$ | $a b$ |
| :---: | :---: | :---: | :---: | :---: |
| 1 | 9 | 84 | 93 | 837 |
| 2 | 10 | 42 | 51 | 510 |
| 3 | 11 | 28 | 37 | 407 |
| 4 | 12 | 21 | 30 | 360 |
| 6 | 14 | 14 | 23 | 322 |
| 7 | 20 | 12 | 16 | 315 |
| 12 | 22 | 6 | 13 | 320 |
| 14 | 36 | 2 | 12 | 377 |
| 21 | 50 | 1 | 10 | 950 |
| 28 | 92 |  |  |  |
| 42 | 29 |  |  |  |
| 84 |  |  |  |  |

The stand has at least 315 seats.

Note. The obtained equation can also be solved in this way:

$$
\begin{gathered}
a b-8 a-9 b=12 \\
a(b-8)-9(b-8)=84 \\
(a-9)(b-8)=84
\end{gathered}
$$

Write the number 84 as the product of two natural numbers:

$$
84=1 \cdot 84=2 \cdot 42=3 \cdot 28=4 \cdot 21=6 \cdot 14=7 \cdot 12
$$

| $b-8$ | $a-9$ | $b$ | $a$ | $a b$ |
| :---: | :---: | :---: | :---: | :---: |
| 1 | 84 | 9 | 93 | 837 |
| 2 | 42 | 10 | 51 | 510 |
| 3 | 28 | 11 | 37 | 407 |
| 4 | 21 | 12 | 30 | 360 |
| 6 | 14 | 14 | 23 | 322 |
| 7 | 12 | 15 | 21 | 315 |
| 12 | 7 | 20 | 16 | 320 |
| 14 | 6 | 22 | 15 | 330 |
| 21 | 4 | 29 | 13 | 377 |
| 28 | 3 | 36 | 12 | 432 |
| 42 | 2 | 50 | 11 | 550 |
| 84 | 1 | 92 | 10 | 920 |

The stand can have at least 315 seats.

b) Example seating arrangement for 315 seats on the stand:

In each row, there are 8 caps, in each column 9 hats, and 12 seats remain empty.

| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- |
| 1 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 2 | 2 | 2 | 2 | 2 | 2 |
| 2 | 1 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 3 | 3 | 3 | 3 | 3 |
| 3 | 2 | 1 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 4 | 4 | 4 | 4 |
| 4 | 3 | 2 | 1 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 5 | 5 | 5 |
| 5 | 4 | 3 | 2 | 1 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 6 | 6 |
| 6 | 5 | 4 | 3 | 2 | 1 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 7 |
| 7 | 6 | 5 | 4 | 3 | 2 | 1 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| 9 | 8 | 7 | 6 | 5 | 4 | 3 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| 1 | 9 | 8 | 7 | 6 | 5 | 4 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| 1 | 2 | 9 | 8 | 7 | 6 | 5 | 2 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| 1 | 2 | 3 | 9 | 8 | 7 | 6 | 3 | 3 | 3 | 4 | 5 | 6 | 7 | 8 |
| 1 | 2 | 3 | 4 | 9 | 8 | 7 | 4 | 4 | 4 | 4 | 5 | 6 | 7 | 8 |
| 1 | 2 | 3 | 4 | 5 | 9 | 8 | 5 | 5 | 5 | 5 | 5 | 6 | 7 | 8 |
| 1 | 2 | 3 | 4 | 5 | 6 | 9 | 6 | 6 | 6 | 6 | 6 | 6 | 7 | 8 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 7 | 7 | 7 | 7 | 7 | 7 | 7 | 8 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 8 | 8 | 8 | 8 | 8 | 8 | 8 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 9 | 9 | 9 | 9 | 9 | 9 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 9 | 8 |  |  |  |  |  |  |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 8 |  |  |  |  |  |  |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 9 | 8 |  |  |  |  |  |  |


[^0]:    111612, 116112, 161112, 611112, 111216, 112116, 121116, 211116, 11112312, 11113212, 11121312, 11123112, 11131212, 11132112, 11211312, 11213112, 11231112, 11311212, 11312112, 11321112, 12111312, 12113112, 12131112, 12311112, 13111212, 13112112, 13121112, 13211112, 21111312, 21113112, 21131112, 21311112, 23111112, 31111212, 31112112, 31121112, 31211112, 32111112, 21111132, 12111132, 11211132, 11121132, 11112132 and 11111232.