IR-TST 2022 Problem 7

Suppose that $n$ is a positive integer number. Consider a regular polygon with $2n$ sides such that one of its largest diagonals is parallel to the $x$ -axis. Find the smallest integer $d$ such that there is a polynomial $P$ of degree $d$ whose graph intersects all sides of the polygon on points other than vertices.

Proposed by Mohammad Ahmadi