1. In each cell of a $75 \times 75$ table, a natural number is written. In each row, there are at least 15 different numbers, and in any three consecutive rows, there are no more than 25 different numbers. What is the maximum number of different numbers that can be in the table?
# Answer: 385

Solution. In one line, there are no less than 15 different numbers, so in the next two lines together, there appear no more than 10 new numbers. Therefore, the first three lines contain no more than 25 different numbers, and each of the following two lines adds no more than 10 new numbers, making the total number of numbers no more than $25 + 36 \cdot 10 = 385$.

Let's provide an example with 385 numbers. We will number the lines from 1 to 75. In the first line, we will place numbers from 1 to 15, and in the line with number $k$, we will place numbers from 1 to 10 and numbers from $5k + 6$ to $5k + 10$. Then, in each line, there will be 5 unique numbers and numbers from 1 to 10, i.e., exactly 15 different numbers, and in every three lines, there will be exactly 25 different numbers.

Remark. We can also prove that the number of different numbers in the table does not exceed 385 by induction. Specifically, we can prove that in any $2n + 1$ consecutive lines, there are no more than $5(2n + 3)$ different numbers. The base case $n=1$ is true by the problem statement. We will establish the transition from $n$ to $n+1$. Consider $2n + 3$ consecutive lines. Suppose the third line from the bottom contains $k \geq 15$ different numbers. Then, in the two lowest lines, there are no more than $25 - k$ different numbers. And in the remaining $2n + 1$ lines, by the inductive hypothesis, there are no more than $5(2n + 3)$ numbers. Therefore, the total number of different numbers will be more than $5(2n + 3) + 25 - k = 5(2n + 8) - k \leq 5(2n + 5)$.