MathDB

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

Problem Statement