4. Vasya, a bibliophile, has 1300 books arranged on $k$ bookshelves in his cabinets. One day, Vasya moved the cabinets to a new place, taking all the books out beforehand. In the process, he completely forgot how the books were arranged before and placed them in the cabinets in a different order. For what maximum $k$ will there definitely be 5 books that were on the same shelf both before and after the rearrangement?
Answer: 18.

Solution. If Vasya has 18 shelves, then on some shelf there are at least 73 books (otherwise, there would be no more than 72 books on each shelf, and the total would not exceed $18 \cdot 72=12964$, making it impossible to rearrange the books on this shelf so that there are no more than four books on each shelf. Thus, $k=18$ works.

Now, we will show that with 19 shelves, the books can be rearranged so that no five books remain on the same shelf. Let the $n$-th row be the books standing on the $n$-th position from the left, cyclically ordered by shelves:

$$
1,2, \ldots, 19,1,2, \ldots, 19, \ldots
$$

Let the cyclic shift of a row by $m$ shelves be the permutation of books where the new shelf number for each book is obtained from the old one by shifting $m$ positions to the right in the sequence (*). Fill the rows from 1 to 68, as well as the first 8 shelves of the 69th row, with books. Thus, there will be $19 \cdot 68 + 8 = 1300$ books on the shelves. After rearranging the shelves, we will place the books as follows. Books from rows 1, 2, 3, and 4 will be placed in their original positions; in rows 5, 6, 7, and 8, the books will be cyclically shifted by one shelf, in rows 9, 10, 11, and 12 by two shelves, and so on. As a result, we will have a situation where no five books that were on the same shelf before and after the rearrangement.