3

Part of 2021 All-Russian Olympiad

Problems(3)

The classics are back

Source: All-Russian 2021/10.3

In the country there're

N

cities and some pairs of cities are connected by two-way airlines (each pair with no more than one). Every airline belongs to one of

k

companies. It turns out that it's possible to get to any city from any other, but it fails when we delete all airlines belonging to any one of the companies. What is the maximum possible number of airlines in the country ?

combinatoricsgraph theory

Points and segments in a different way

Source: All-Russian 2021/9.3

n+1

segments are marked such that one of the points of the line is contained in all of them. Prove that one can find

2

distinct segments

I, J

which intersect at a segment of length at least

\frac{n-1}{n}d

d

is the length of the segment

I

combinatoricsRussiaAll Russian Olympiad

maximum set of particularly picked words in three letter alphabet

Source: All-Russian 2021/11.3

Some language has only three letters -

A, B

C

. A sequence of letters is called a word iff it contains exactly 100 letters such that exactly 40 of them are consonants and other 60 letters are all

A

. What is the maximum numbers of words one can pick such that any two picked words have at least one position where they both have consonants, but different consonants?