3. (3 points) In a certain country, there are 50 cities. The Ministry of Aviation requires that every two cities be connected by a two-way flight operated by exactly one airline, and that it should be possible to travel from any city to any other using the flights of each airline (possibly with layovers). What is the maximum number of airlines for which this is possible?

## Answer: 25
Solution: Evaluation: in order to connect all cities, the airline must have at least 49 flights. In total, there are $50 \cdot 49 / 2$ pairs of cities, so there are no more than 25 airlines.

Example: let the cities be denoted as $a_{1}, a_{2}, \ldots a_{25}, b_{1}, b_{2}, \ldots, b_{25}$ in some way. Then the airline with number $k$ will connect

1) cities $a_{k}$ and $b_{k}$
2) $a_{k}$ and each city $a_{i}$, where $i < k$
3) $a_{k}$ and each city $b_{i}$, where $i > k$
4) $b_{k}$ and each city $a_{i}$, where $i > k$
5) $b_{k}$ and each city $b_{i}$, where $i < k$.

Thus, cities $a_{i}$ and $a_{j}$ are connected by a flight of the airline with number $\max \left(a_{i}, a_{j}\right)$, cities $b_{i}$ and $b_{j}$ - by the airline with number $\max \left(b_{i}, b_{j}\right)$, and cities $a_{i}$ and $b_{j}$ - by the airline with number $\min \left(b_{i}, b_{j}\right)$.

4. (3 points) Prove that for $n=3002$, the sum of binomial coefficients with a step of 6, i.e., $C_{n}^{1}+C_{n}^{7}+\ldots+C_{n}^{n-1}$, gives a remainder of 1 when divided by 3.

$C_{n}^{k}$ - the number of ways to choose $k$ items from $n$, which is $\frac{n!}{k!(n-k)!}$ if $0 \leqslant k \leqslant n$ and 0 in other cases.

Solution:

It is easy to verify that $C_{n}^{k}=C_{n-3}^{k-3}+3 C_{n-3}^{k-2}+3 C_{n-3}^{k-1}+C_{n-3}^{k}$, therefore, $C_{n}^{k}$ gives the same remainder when divided by 3 as $C_{n-3}^{k-3}+C_{n-3}^{k}$.

Thus, $C_{n}^{1}+C_{n}^{7}+\ldots+C_{n}^{n-1}$ gives the same remainder when divided by 3 as $C_{n-3}^{1}+C_{n-3}^{4}+\ldots+$ $C_{n-3}^{n-7}+C_{n-3}^{n-4}$ (here the two extreme terms, equal to 0, are omitted).

Denote this sum by $S_{n-3}$.

Similarly, we transition to $2 C_{n-6}^{1}+2 C_{n-3}^{4}+\ldots+2 C_{n-3}^{n-7}+2 C_{n-3}^{n-4}=2 S_{n-6}$.

Applying this procedure 998 more times, we get that the formula from the condition gives the same remainder when divided by 3 as $2^{999} S_{2}=4^{499} \cdot 2 C_{2}^{1}=4^{500}$, which gives a remainder of 1 when divided by 3.