Berr S.L.

100 people came to a party. Then those who had no acquaintances among the attendees left. Then those who had exactly one acquaintance among the remaining people also left. Then, similarly, those who had exactly 2, 3, 4, ..., 99 acquaintances among the remaining people at the time of their departure, also left.

What is the maximum number of people that could remain at the end?
It is not difficult to check that if all the guests, except for two people $A$ and $B$, were acquainted with each other, then at the end, everyone except $A$ and $B$ should remain, that is, 98 people.

Let's prove that 99 people could not remain. It is clear that person $A$, who initially had the fewest acquaintances ($k$), will leave at some point. If no one else leaves, then all the others (except $A$) had more than $k$ acquaintances before $A$ left and fewer than $k+1$ after $A$ left. But then $A$ must be acquainted with everyone else, that is, $k=99$, which contradicts the strict minimality of $k$.

## Answer

98 people.

Author: Podlipsky O.K.

Let's call a coloring of an $8 \times 8$ board in three colors good if in any corner of five cells, cells of all three colors are present. (A corner of five cells is a figure obtained by cutting out a $2 \times 2$ square from a $3 \times 3$ square.) Prove that the number of good colorings is at least $6^{8}$.

## Solution

Each corner contains a horizontal rectangle $1 \times 3$. Any row can be colored in three colors such that each rectangle $1 \times 3$ contains cells of three different colors in exactly 6 ways (resulting in a coloring pattern $A B C A B C A B$, and the colors $A, B, C$ can be chosen in 6 ways).

This means that a coloring in which each row is colored in the specified manner will be good. Since each row can be colored independently of the others, the number of such good colorings will be exactly $6^{8}$.

But there are still good colorings that we have not counted, for example, such that each row is monochromatic, and the colors of the rows alternate in the above manner (in this case, any vertical rectangle $1 \times 3$ will contain cells of three different colors). Therefore, the total number of good colorings is greater than $6^{8}$.