Olympiad problems

2022 Brazil Team Selection Test, 4

Let $d_1, d_2, \ldots, d_n$ be given integers. Show that there exists a graph whose sequence of degrees is $d_1, d_2, \ldots, d_n$ and which contains an perfect matching if, and only if, there exists a graph whose sequence of degrees is $d_2, d_2, \ldots, d_n$ and a graph whose sequence of degrees is $d_1-1, d_2-1, \ldots, d_n-1$.

2022 3rd Memorial "Aleksandar Blazhevski-Cane", P6

Tags: symmetry , central symmetry , perfect matching , circles , combinatorics

For any integer $n\geq1$, we consider a set $P_{2n}$ of $2n$ points placed equidistantly on a circle. A [i]perfect matching[/i] on this point set is comprised of $n$ (straight-line) segments whose endpoints constitute $P_{2n}$. Let $\mathcal{M}_{n}$ denote the set of all non-crossing perfect matchings on $P_{2n}$. A perfect matching $M\in \mathcal{M}_{n}$ is said to be [i]centrally symmetric[/i], if it is invariant under point reflection at the circle center. Determine, as a function of $n$, the number of centrally symmetric perfect matchings within $\mathcal{M}_{n}$. [i]Proposed by Mirko Petrusevski[/i]

2011 Brazil Team Selection Test, 3

Tags: perfect matching , hall s marriage theorem , matching , graph theory , combinatorics

On some planet, there are $2^N$ countries $(N \geq 4).$ Each country has a flag $N$ units wide and one unit high composed of $N$ fields of size $1 \times 1,$ each field being either yellow or blue. No two countries have the same flag. We say that a set of $N$ flags is diverse if these flags can be arranged into an $N \times N$ square so that all $N$ fields on its main diagonal will have the same color. Determine the smallest positive integer $M$ such that among any $M$ distinct flags, there exist $N$ flags forming a diverse set. [i]Proposed by Tonći Kokan, Croatia[/i]

2011 Peru IMO TST, 5

Tags: graph theory , hall s marriage theorem , perfect matching , matching , combinatorics

On some planet, there are $2^N$ countries $(N \geq 4).$ Each country has a flag $N$ units wide and one unit high composed of $N$ fields of size $1 \times 1,$ each field being either yellow or blue. No two countries have the same flag. We say that a set of $N$ flags is diverse if these flags can be arranged into an $N \times N$ square so that all $N$ fields on its main diagonal will have the same color. Determine the smallest positive integer $M$ such that among any $M$ distinct flags, there exist $N$ flags forming a diverse set. [i]Proposed by Tonći Kokan, Croatia[/i]

2010 IMO Shortlist, 2

Tags: combinatorics , hall s marriage theorem , perfect matching , graph theory , matching

On some planet, there are $2^N$ countries $(N \geq 4).$ Each country has a flag $N$ units wide and one unit high composed of $N$ fields of size $1 \times 1,$ each field being either yellow or blue. No two countries have the same flag. We say that a set of $N$ flags is diverse if these flags can be arranged into an $N \times N$ square so that all $N$ fields on its main diagonal will have the same color. Determine the smallest positive integer $M$ such that among any $M$ distinct flags, there exist $N$ flags forming a diverse set. [i]Proposed by Tonći Kokan, Croatia[/i]