Problem 10.4. (15 points) Once, 45 friends living in different parts of the world decided to exchange news with each other. To do this, they plan to arrange $k$ video meetings, at each of which every person will share their news, as well as all the news from other people they have learned previously.

For the video meetings, 10 days were proposed, but it turned out that each friend can only be present on 8 of them. What is the smallest natural number $k$ that guarantees we can select $k$ days for the video meetings from the proposed 10 so that everyone learns the news from everyone else?

(Between the proposed days, no new news arises among the people, and they do not communicate with each other in any other way. On each of the proposed days, one video meeting is held, which is attended by everyone who can be present on that day.)
Answer: 5 days.

Solution. Let's provide an example of a situation where 4 days would not be enough. Suppose each of the 45 people has their own unique pair of days when they cannot participate in the meeting. Since the number of ways to choose a pair of days from the 10 offered is $\mathrm{C}_{10}^{2}=45$, for any pair of days, there will be a person who cannot be present on exactly those two days. Suppose we managed to choose some 4 days such that everyone learns all the news. Then there exists a person $A$ who cannot be present on the first two of these four days, and a person $B$ who cannot be present on the last two of these four days. Notice that then $B$ will not be able to learn the news from $A$. Contradiction.

Now let's understand that 5 days will always be enough. Choose 5 days arbitrarily. We will prove that any two people will be present together at some meeting. Indeed, among these 5 days, there are no more than 2 days when the first person cannot be present, and no more than 2 days when the second person cannot be present. Therefore, there will be a day when both can be present. Thus, each pair of people will be able to exchange news, i.e., everyone will learn the news from everyone else.

## Criteria

## Points for evaluation and example are summed up:

+9 p. Evaluation - it is proven that 4 days may not be enough.

In the absence of this proof, the following progress is evaluated:

+1 p. Mentioned that different pairs of missed days can correspond to all people.

+6 p. Example - it is proven that 5 days are guaranteed to be enough.

The following progress is not evaluated:

0 p. Only the correct answer is provided.