Found problems: 9
$n(\geq 4)$ islands are connected by bridges to satisfy the following conditions:
[list]
[*]Each bridge connects only two islands and does not go through other islands.
[*]There is at most one bridge connecting any two different islands.
[*]There does not exist a list $A_1, A_2, \ldots, A_{2k}(k \geq 2)$ of distinct islands that satisfy the following:
[center]For every $i=1, 2, \ldots, 2k$, the two islands $A_i$ and $A_{i+1}$ are connected by a bridge. (Let $A_{2k+1}=A_1$)[/center]
[/list]
Prove that the number of the bridges is at most $\frac{3(n-1)}{2}$.
All diagonals of a convex polygon are drawn. Prove that its sides and diagonals can be assigned arrows in such a way that no round trip along sides and diagonals is possible.
Given a natural number $k> 1$. Prove that if through any edge of the graph $G$ passes less than $[e(k-1)! - 1]$ simple cycles, then the vertices of this graph can be colored with $k$ colors in the correct way.
Given any positive real number $\varepsilon$, prove that, for all but finitely many positive integers $v$, any graph on $v$ vertices with at least $(1+\varepsilon)v$ edges has two distinct simple cycles of equal lengths.
(Recall that the notion of a simple cycle does not allow repetition of vertices in a cycle.)
[i]Fedor Petrov, Russia[/i]
An arrow is assigned to each edge of a polyhedron such that for each vertex, there is an arrow pointing towards that vertex and an arrow pointing away from that vertex. Prove that there exist at least two faces such that the arrows on their boundaries form a cycle.
Given any positive real number $\varepsilon$, prove that, for all but finitely many positive integers $v$, any graph on $v$ vertices with at least $(1+\varepsilon)v$ edges has two distinct simple cycles of equal lengths.
(Recall that the notion of a simple cycle does not allow repetition of vertices in a cycle.)
[i]Fedor Petrov, Russia[/i]
A Magician and a Detective play a game. The Magician lays down cards numbered from $1$ to $52$ face-down on a table. On each move, the Detective can point to two cards and inquire if the numbers on them are consecutive. The Magician replies truthfully. After a finite number of moves, the Detective points to two cards. She wins if the numbers on these two cards are consecutive, and loses otherwise.
Prove that the Detective can guarantee a win if and only if she is allowed to ask at least $50$ questions.
[i]Proposed by Anant Mudgal[/i]
Given any positive real number $\varepsilon$, prove that, for all but finitely many positive integers $v$, any graph on $v$ vertices with at least $(1+\varepsilon)v$ edges has two distinct simple cycles of equal lengths.
(Recall that the notion of a simple cycle does not allow repetition of vertices in a cycle.)
[i]Fedor Petrov, Russia[/i]
In the country of Sikinia there are finitely many cities. From each city, exactly three roads go out and each road goes to another Sikinian city. A tourist starts a trip from city $A$ and drives according to the following rule: he turns left at the first city, then right at the next city, and so on, alternately. Show that he will eventually return to $A.$