Olympiad problems

Found problems: 2

2019 Korea National Olympiad, 8

There are two countries $A$ and $B$, where each countries have $n(\ge 2)$ airports. There are some two-way flights among airports of $A$ and $B$, so that each airport has exactly $3$ flights. There might be multiple flights among two airports; and there are no flights among airports of the same country. A travel agency wants to plan an [i]exotic traveling course[/i] which travels through all $2n$ airports exactly once, and returns to the initial airport. If $N$ denotes the number of all exotic traveling courses, then prove that $\frac{N}{4n}$ is an even integer. (Here, note that two exotic traveling courses are different if their starting place are different.)

matching combinatorics graph theory hamiltonian cycle bijection mathematical induction parity

2023 OMpD, 3

Let $m$ and $n$ be positive integers integers such that $2m + 1 < n$, and let $S$ be the set of the $2^n$ subsets of $\{1,2,\ldots,n\}$. Prove that we can place the elements of $S$ on a circle, so that for any two adjacent elements $A$ and $B$, the set $A \Delta B$ has exactly $2m + 1$ elements. [b]Note[/b]: $A \Delta B = (A \cup B) - (A \cap B)$ is the set of elements that are exclusively in $A$ or exclusively in $B$.

induction power set set combinatorics graph theory hamiltonian cycle geometry mathematical induction number theory