Problem

Source: Iran 3rd round 2013 - Combinatorics exam problem 3

Tags: combinatorics unsolved, combinatorics



$n$ cars are racing. At first they have a particular order. At each moment a car may overtake another car. No two overtaking actions occur at the same time, and except moments a car is passing another, the cars always have an order. A set of overtaking actions is called "small" if any car overtakes at most once. A set of overtaking actions is called "complete" if any car overtakes exactly once. If $F$ is the set of all possible orders of the cars after a small set of overtaking actions and $G$ is the set of all possible orders of the cars after a complete set of overtaking actions, prove that \[\mid F\mid=2\mid G\mid\] (20 points) Proposed by Morteza Saghafian