Any solution ??

The polynomial $P(x) = -\frac{1}{\pi} (x - 1)^2 (x - 2)^2 \cdots (x - n)^2$ works for part (a). @below oh yeah, thanks I forgot that :b

@above, your example does work, but only if you put a minus sign in front.

Call a number $x$ handsome if it satisfies the equation $\lfloor P(x)\rfloor=P(\lfloor x\rfloor)$ (say that $x\in \mathcal{H}$). If such a point is also an integer point, call it amazing (and say it belongs to $\mathcal{A}$); if it is not amazing, call it beautiful (say It belongs to $\mathcal{B}$). Lemma 1: if $x$ is beautiful, then $\lfloor x\rfloor$ is amazing. Proof: $P(\lfloor x\rfloor)=\lfloor P(x)\rfloor$ which implies $P(\lfloor x\rfloor)\in \mathbb{Z}$. Therefore $\lfloor P(\lfloor x\rfloor)\rfloor=P(\lfloor x\rfloor)=P(\lfloor \lfloor x\rfloor \rfloor)$, implying $\lfloor x\rfloor$ is amazing. Lemma 2: if $x_0=m+t$ ($t\in (0,1)$) is beautiful, then $P(x_0)$ is an integer and $P(x)\leq P(x_0)$ $\forall x$ such that $\lfloor x\rfloor =\lfloor x_0\rfloor$. Proof: Assume $P(m)=n$, which implies $\lfloor P(x_0)\rfloor=n$. Assume by way of contradiction that $P(x_0)=n+u$ with $u\in (0,1)$. Since polynomials are continuous, by definition of limit we can find a neighborhood $\mathcal{I}(x_0)\subset (m,m+1)$ such that $P(\mathcal{I}(x_0))=\mathcal{J}(n+u)\subset (n,n+1)$ ($\mathcal{J}$ is a neighborhood of $P(x_0)$), which is a contradiction since all points of $\mathcal{I}$ are beautiful and $\mathcal{I}$ is uncountable, implying we would have $|\mathcal{H}|\geq |\mathcal{I}|>n$. Furthermore what we also get is that $P'(x_0)=0$, since otherwise there would be a $y_0$ in some neighbourood such that $P(y_0)>n$ which would once again be a contradiction. Now note that $|\mathcal{A}|+|\mathcal{B}|=n=\frac{2n+1}{3}+\frac{n-1}{3}$. Therefore we have two possibilities, of which at least one must be true. I)$M=|\mathcal{A}|\geq \frac{n-1}{3}$. Let $a_1<a_2<\cdots <a_M$ be the points in $\mathcal{A}$, which are all integer points. We must have $P(x)=R(x)+Q(x)(x-a_1)\cdots(x-a_M)$, where $R(x)$ is the polynomial obtained by Lagrange interpolation, with degree less than $M$. Since $a_i,P(a_i)\in \mathbb{Z}$. Assume that $Q(x)\equiv 0$. It follows by the formula of Lagrange interpolation that $R(x)\in \mathbb{Q}[x]$, and say $R(x)=\frac{S(x)}{m}$, with $S\in\mathbb{Z}[x]$ and $m\in\mathbb{Z}^+$. Since $0\equiv S(a_M)\equiv S(a_M+m)\pmod{m}$, $P(a_M+m)=\frac{S(a_M+m)}{m}\in\mathbb{Z}$ ,which implies $a_M+m$ is also an integer point and thus an amazing point, which is a contradiction. So $Q\neq 0$, which implies $deg P\geq M\geq \frac{2n+1}{3}$. II)$N=|\mathcal{B}|\geq \frac{n-1}{3}$. Consider some beautiful numbers $t_1,...,t_k$ such that $m<t_1<\cdots <t_k<m+1$, with $m\in\mathbb{Z}$. We already know by Lemma 2 that $P(m)=P(t_1)=\cdots P(t_k):=n$, and that $P'(t_1)=\cdots =P'(t_k)=0$. Therefore, by Lagrange's theorem, we have $n$ other points $u_i\in (t_{i-1},t_i)$ (where $t_0:=m$), such that $P'(u_i)=0$. Therefore we have a total of $2k$ points with zero derivative. Adding this numbers for all intervals $(m,m+1)$, we get that the number of points where $P'(x)$ is zero is $\geq 2b$, which implies (since $P'$ clearly can't be the zero polynomial) $deg P'\geq 2N$. Therefore $deg P\geq 2N+1\geq 2\frac{n-1}{3}+1=\frac{2n+1}{3}$, as we wanted.

cadaeibf wrote: Call a number $x$ handsome if it satisfies the equation $\lfloor P(x)\rfloor=P(\lfloor x\rfloor)$ (say that $x\in \mathcal{H}$). If such a point is also an integer point, call it amazing (and say it belongs to $\mathcal{A}$); if it is not amazing, call it beautiful (say It belongs to $\mathcal{B}$). Lemma 1: if $x$ is beautiful, then $\lfloor x\rfloor$ is amazing. Proof: $P(\lfloor x\rfloor)=\lfloor P(x)\rfloor$ which implies $P(\lfloor x\rfloor)\in \mathbb{Z}$. Therefore $\lfloor P(\lfloor x\rfloor)\rfloor=P(\lfloor x\rfloor)=P(\lfloor \lfloor x\rfloor \rfloor)$, implying $\lfloor x\rfloor$ is amazing. Lemma 2: if $x_0=m+t$ ($t\in (0,1)$) is beautiful, then $P(x_0)$ is an integer and $P(x)\leq P(x_0)$ $\forall x$ such that $\lfloor x\rfloor =\lfloor x_0\rfloor$. Proof: Assume $P(m)=n$, which implies $\lfloor P(x_0)\rfloor=n$. Assume by way of contradiction that $P(x_0)=n+u$ with $u\in (0,1)$. Since polynomials are continuous, by definition of limit we can find a neighborhood $\mathcal{I}(x_0)\subset (m,m+1)$ such that $P(\mathcal{I}(x_0))=\mathcal{J}(n+u)\subset (n,n+1)$ ($\mathcal{J}$ is a neighborhood of $P(x_0)$), which is a contradiction since all points of $\mathcal{I}$ are beautiful and $\mathcal{I}$ is uncountable, implying we would have $|\mathcal{H}|\geq |\mathcal{I}|>n$. Furthermore what we also get is that $P'(x_0)=0$, since otherwise there would be a $y_0$ in some neighbourood such that $P(y_0)>n$ which would once again be a contradiction. Now note that $|\mathcal{A}|+|\mathcal{B}|=n=\frac{2n+1}{3}+\frac{n-1}{3}$. Therefore we have two possibilities, of which at least one must be true. I)$M=|\mathcal{A}|\geq \frac{n-1}{3}$. Let $a_1<a_2<\cdots <a_M$ be the points in $\mathcal{A}$, which are all integer points. We must have $P(x)=R(x)+Q(x)(x-a_1)\cdots(x-a_M)$, where $R(x)$ is the polynomial obtained by Lagrange interpolation, with degree less than $M$. Since $a_i,P(a_i)\in \mathbb{Z}$. Assume that $Q(x)\equiv 0$. It follows by the formula of Lagrange interpolation that $R(x)\in \mathbb{Q}[x]$, and say $R(x)=\frac{S(x)}{m}$, with $S\in\mathbb{Z}[x]$ and $m\in\mathbb{Z}^+$. Since $0\equiv S(a_M)\equiv S(a_M+m)\pmod{m}$, $P(a_M+m)=\frac{S(a_M+m)}{m}\in\mathbb{Z}$ ,which implies $a_M+m$ is also an integer point and thus an amazing point, which is a contradiction. So $Q\neq 0$, which implies $deg P\geq M\geq \frac{2n+1}{3}$. II)$N=|\mathcal{B}|\geq \frac{n-1}{3}$. Consider some beautiful numbers $t_1,...,t_k$ such that $m<t_1<\cdots <t_k<m+1$, with $m\in\mathbb{Z}$. We already know by Lemma 2 that $P(m)=P(t_1)=\cdots P(t_k):=n$, and that $P'(t_1)=\cdots =P'(t_k)=0$. Therefore, by Lagrange's theorem, we have $n$ other points $u_i\in (t_{i-1},t_i)$ (where $t_0:=m$), such that $P'(u_i)=0$. Therefore we have a total of $2k$ points with zero derivative. Adding this numbers for all intervals $(m,m+1)$, we get that the number of points where $P'(x)$ is zero is $\geq 2b$, which implies (since $P'$ clearly can't be the zero polynomial) $deg P'\geq 2N$. Therefore $deg P\geq 2N+1\geq 2\frac{n-1}{3}+1=\frac{2n+1}{3}$, as we wanted. Can you please explain the motivation behind this?

That solution is wrong. For starters AM + m doesn’t have to be an integer point since Q(x) might be irrational.

R8kt wrote: That solution is wrong. For starters AM + m doesn’t have to be an integer point since Q(x) might be irrational. Note that $Q$ is rational by Lagrange Interpolation (this is also mentioned in the solution!). Indeed, the solution in #5 is perfectly fine.

Fibonacci_11235 wrote: Can you please explain the motivation behind this? Let me try (giving another way to formulate the same solution). First of all, let us study pretty polynomials in general, without any precise goal in mind. The first observation we make is that often, when we have one such solution $x$, we already get infinitely many, which would kill us. Indeed, consider a solution $x_0$ and consider $x=x_0+\varepsilon$ for small $\varepsilon>0$. Since $P(\lfloor x_0+\varepsilon\rfloor)=P(\lfloor x_0\rfloor)$, the only way in which this will not be another solution will be if $\lfloor P(x_0)\rfloor \ne \lfloor P(x_0+\varepsilon)\rfloor$. But by continuity, this only happens when $P(x_0)$ is an integer and $P$ is locally decreasing to the right of $x_0$. Hence we have shown: If $x_0$ is a solution, then $P(x_0)$ must be an integer and $P$ is locally decreasing to the right of $x_0$, since else we have infinitely many solutions. Repeating the same argument with $x_0-\varepsilon$, we see that either $x_0$ itself is an integer or $P$ is locally increasing to the left of $x_0$ (or else we have infinitely many solutions). Finally, we observe that for a solution $x_0$, also $\lfloor x_0\rfloor$ is a solution, by direct computation. The situation therefore can be fully described as follows: We have a bunch of integers $m$ such that $P(m)$ is an integer and such that on $(m,m+1)$ we have $P(x) \le P(m)$ with finitely many, say $a_m$ many, equality cases. From here we finally start counting: Let $d$ be the degree. If $m \ge d+1$, then $P$ is rational by Lagrange Interpolation and hence assumes infinitely many integer values at integer points, contradiction! Hence $m \le d$. On the other hand, on each interval $(m,m+1)$ we must have $a_m$ local maxima and together with the point $m$ itself, the derivative $P'$ must have at least $2a_m$ roots on this interval, hence $2a_m \le d-1$. But the total number of solutions is $n=m+a_m \le d+\frac{d-1}{2}=\frac{3d-1}{2}$ and we conclude that $d \ge \frac{2n+1}{3}$ by rearranging.

Thanks man