On a $30 \times 30$ board, the rows and columns are numbered from 1 to 30. In each row, João paints red the cells where the column number is a multiple of the row number. How many cells will be painted red?

#
Solution

The number of houses painted in line $i$ is equal to the number of multiples of $i$ less than or equal to 30. If we divide 30 by $i$ and get quotient $q$ and remainder $r$, with $0 \leq r<i$, then the number of houses painted is $q$, because

$$
i \cdot 1<i \cdot 2<\ldots<i \cdot q \leq 30<i \cdot q+i
$$

The table below indicates, for each $i$, how many numbers will be painted in line $i$.

| $i$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: |
| $q$ | 30 | 15 | 10 | 7 | 6 | 5 | 4 | 3 | 3 | 3 |
| $i$ | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
| $q$ | 2 | 2 | 2 | 2 | 2 | 1 | 1 | 1 | 1 | 1 |
| $i$ | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 |
| $q$ | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |

Therefore, the number of little squares painted is

$$
30+15+10+7+6+5+4+3+3+3+2+2+2+2+2+1+1+\ldots+1=111
$$