4. In the theater, there are $k$ rows of seats. 770 spectators came to the theater and sat down (possibly not occupying all the seats). After the intermission, all the spectators forgot which seats they had and sat down differently. For what largest $k$ will there definitely be 4 spectators who sat in the same row both before and after the intermission?
Answer: 16

Solution. If the audience is seated on 16 rows, then on some row there are no fewer than 49 spectators (otherwise, there would be no more than 48 spectators on each row, and the total would not exceed $16 \cdot 48=7683$, making it impossible to seat the spectators of this row after the intermission such that there are no more than three in each row. Thus, $k=16$ works.

Now, we will show that with 17 rows, the audience can be seated in such a way that the required four spectators do not exist. Let the $n$-th column be the seats in the hall with number $n$, cyclically ordered by rows:

$$
1,2, \ldots, 17,1,2, \ldots, 17, \ldots
$$

A cyclic shift of a column by $m$ rows is a permutation of the column where the new row number of each spectator is obtained from the old one by shifting $m$ positions to the right in the sequence (*). Fill the columns numbered from 1 to 45 with spectators, as well as the first 5 seats of the 46th column. Thus, there will be $17 \cdot 45 + 5 = 770$ people in the hall. After the intermission, we will seat the spectators as follows. The spectators in columns $1,2,3$ sit in their original seats; in columns $4,5,6$, the spectators are cyclically shifted by one row, in columns $7,8,9$ by two rows, and so on. As a result, we will have a situation where there are no four spectators who sat in the same row both before and after the intermission.