Found problems: 7
2023 Ukraine National Mathematical Olympiad, 9.8
What is the largest possible number of edges in a graph on $2n$ nodes, if there exists exactly one way to split its nodes into $n$ pairs so that the nodes from each pair are connected by an edge?
[i]Proposed by Anton Trygub[/i]
2016 CIIM, Problem 2
A boa of size $k$ is a graph with $k+1$ vertices $\{0,1,\dots,k-1,k\}$ and edges only between the vertices $i$ and $i+1$ for $0\leq i < k.$ The boa is place in a graph $G$ through a injection of graphs. (This is an injective function form the vertices of the boa to the vertices of the graph in such a way that if there is an edge between the vertices $x$ and $y$ in the boa then there must be an edge between $f(x)$ and $f(y)$ in $G$).
The Boa can move in the graph $G$ using to type of movement each time. If the boa is initially on the vertices $f(0),f(1),\dots,f(k)$ then it moves in one of the following ways:
(i) It choose $v$ a neighbor of $f(k)$ such that $v\not\in\{f(0),f(1),\dots,f(k-1)\}$ and the boa now moves to $f(0),f(1),\dots,f(k)$ with $f'(k)=v$ and $f'(i) = f(i+1)$ for $0 \leq i < k,$ or
(ii) It choose $v$ a neighbor of $f(0)$ such that $v\not\in\{f(1),f(2),\dots,f(k)\}$ and the boa now moves to $f(0),f(1),\dots,f(k)$ with $f'(0)=v$ and $f'(i) = f'(i-1)$ for $0 < i \leq k.$
Prove that if $G$ is a connected graph with diameter $d$, then it is possible to put a size $\lceil d/2 \rceil$ boa in $G$ such that the boa can reach any vertex of $G$.
2023 Ukraine National Mathematical Olympiad, 11.8
There are $2024$ cities in a country, every two of which are bidirectionally connected by exactly one of three modes of transportation - rail, air, or road. A tourist has arrived in this country and has the entire transportation scheme. He chooses a travel ticket for one of the modes of transportation and the city from which he starts his trip. He wants to visit as many cities as possible, but using only the ticket for the specified type of transportation. What is the largest $k$ for which the tourist will always be able to visit at least $k$ cities? During the route, he can return to the cities he has already visited.
[i]Proposed by Bogdan Rublov[/i]
2023 Ukraine National Mathematical Olympiad, 10.8
Consider a complete graph on $4046$ nodes, whose edges are colored in some colors. Let's call this graph $k$-good if we can split all its nodes into $2023$ pairs so that there are exactly $k$ distinct colors among the colors of $2023$ edges that connect the nodes from the same pairs. Is it possible that the graph is $999$-good and $1001$-good but not $1000$-good?
[i]Proposed by Anton Trygub[/i]
2023 Ukraine National Mathematical Olympiad, 8.7
The country has $n \ge 3$ airports, some pairs of which are connected by bidirectional flights. Every day, the government closes the airport with the strictly highest number of flights going out of it. What is the maximum number of days this can continue?
[i]Proposed by Fedir Yudin[/i]
2022 Turkey EGMO TST, 4
On a table there are $100$ red and $k$ white buckets for which all of them are initially empty. In each move, a red and a white bucket is selected and an equal amount of water is added to both of them. After some number of moves, there is no empty bucket and for every pair of buckets that are selected together at least once during the moves, the amount of water in these buckets is the same. Find all the possible values of $k$.
2023 Belarusian National Olympiad, 10.8
On the Alphamegacentavra planet there are $2023$ cities, some of which are connected by non-directed flights. It turned out that among any $4$ cities one can find two with no flight between them.
Find the maximum number of triples of cities such that between any two of them there is a flight.