Olympiad problems

1987 Bundeswettbewerb Mathematik, 2

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.

2021 India National Olympiad, 4

Tags: combinatorics , guessing game , graph theory , cycles , paths , Trees , INMO

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]

2019 Romanian Masters In Mathematics, 3

Tags: RMM , RMM 2019 , combinatorics , graph theory , cycles , Fedya , probability

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]

1974 Bundeswettbewerb Mathematik, 4

Tags: polygon , combinatorics , cycles

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.

Kvant 2019, M2557

Tags: RMM , RMM 2019 , combinatorics , graph theory , cycles , Fedya , probability

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]

2019 Romanian Master of Mathematics, 3

Tags: RMM , RMM 2019 , combinatorics , graph theory , cycles , Fedya , probability

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]

2019 239 Open Mathematical Olympiad, 8

Tags: graph theory , combinatorics , Chromatic number , cycles

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.