Found problems: 6
2016 Tournament Of Towns, 4
There are $64$ towns in a country and some pairs of towns are connected by roads but we do not know these pairs. We may choose any pair of towns and find out whether they are connected or not. Our aim is to determine whether it is possible to travel from any town to any other by a sequence of roads. Prove that there is no algorithm which enables us to do so in less than $2016$ questions.
(Proposed by Konstantin Knop)
2015 Switzerland Team Selection Test, 11
In Thailand there are $n$ cities. Each pair of cities is connected by a one-way street which can be borrowed, depending on its type, only by bike or by car. Show that there is a city from which you can reach any other city, either by bike or by car.
[i]Remark : It is not necessary to use the same means of transport for each city[/i]
2000 239 Open Mathematical Olympiad, 4
A graph is called 2-connected if after removing any vertex the remaining graph is still connected. Prove that for any 2-connected graph with degrees more than two, one can remove a vertex so that the remaining graph is still 2-connected.
2006 Miklós Schweitzer, 4
let P be a finite set with at least 2 elements. P is a partially ordered and connected set. $p:P^3 \to P$ is a 3-variable, monotone function which satisfies p(x,x,y)=y. Prove that there exists a non-empty subset $I \subset P$ such that $\forall x \in P$ $\forall y \in I$, we have $p(x, y, y) \in I$.
[P is connected means that if each element is replaced by vertices and there is an edge between 2 vertices iff the 2 elements can be compared, then the graph is connected.
p is monotone means that if $x_1\leq y_1 , x_2\leq y_2 , x_3\leq y_3$ , then $p(x_1,x_2,x_3)\leq p(y_1,y_2,y_3)$.]
2013 Turkey MO (2nd round), 3
Let $G$ be a simple, undirected, connected graph with $100$ vertices and $2013$ edges. It is given that there exist two vertices $A$ and $B$ such that it is not possible to reach $A$ from $B$ using one or two edges. We color all edges using $n$ colors, such that for all pairs of vertices, there exists a way connecting them with a single color. Find the maximum value of $n$.
2025 Bulgarian Spring Mathematical Competition, 9.3
In a country, there are towns, some of which are connected by roads. There is a route (not necessarily direct) between every two towns. The Minister of Education has ensured that every town without a school is connected via a direct road to a town that has a school. The Minister of State Optimization wants to ensure that there is a unique path between any two towns (without repeating traveled segments), which may require removing some roads.
Is it always possible to achieve this without constructing additional schools while preserving what the Minister of Education has accomplished?