MEMO 2021 T2

Given a positive integer $n$ , we say that a polynomial $P$ with real coefficients is $n$ -pretty if the equation $P(\lfloor x \rfloor)=\lfloor P(x) \rfloor$ has exactly $n$ real solutions. Show that for each positive integer $n$ [list=a] [] there exists an n-pretty polynomial; [] any $n$ -pretty polynomial has a degree of at least $\tfrac{2n+1}{3}$ . [/list] (Remark. For a real number $x$ , we denote by $\lfloor x \rfloor$ the largest integer smaller than or equal to $x$ .)