$P,Q$ are polynomials with real coefficients and for every real $x$ satisfy $P(P(P(x)))=Q(Q(Q(x)))$. Prove that $P=Q$ 
$P,Q$ are polynomials with real coefficients and for every real $x$ satisfy $P(P(P(x)))=Q(Q(Q(x)))$. Prove that $P=Q$.

I see only that these polynomials are same degree
 A: Since one easily messes things up when starting from highest coefficients downward (as I did in my first revision of this answer), we shall consider the function $f(z)=\frac1{P(z^{-1})}$, which allows us nicer acccess to the high coefficients of $P$.
As a matter of notation, write $$f^{\circ k}:=\underbrace{f\circ\ldots\circ f}_{k}$$ 
for function iteration.
Lemma. Let $n,m,k\in\mathbb N$, $m> k\ge 2$. Let $f$ be holomorphic around $0$ with $f(0)\ne0$. Then there exist $M$ with $k^n<M<k^n(m-k+1)$ and $\alpha\in\mathbb C$ with $\alpha\ne 0$ such that for any  $h$ holomorphic around $0$, we have $$(z^kf+z^mh)^{\circ n}=(z^kf)^{\circ n}+\alpha  h(0)z^M+O(z^{M+1}).$$
Proof.
First observe (e.g., by induction on $n$) that $(z^kf)^{\circ n}$ has a root of order exactly $k^n$ at $z=0$, and $((z^kf)^{\circ n})^r$ has a root of order exactly $ k^nr$ at $z=0$, say $$\tag1((z^kf)^{\circ n})^r=c_{n,r}z^{k^nr}+O(z^{k^nr})$$ with $c_{n,r}\ne0$ depending only on $f,k,n,r$ (but we consider $f,k$ fixed).
Now we show the claim of the lemma by induction on $n$. The claim is clear for $n=1$ with $\alpha=1$ and $M=m$ (which is $<k^1(m-k+1)$!).
Assume that the claim holds for $n$.
For any $r\ge 1$, we have
$$\tag1\begin{align}\left( (z^kf+z^mh)^{\circ n}\right)^r&=\left((z^kf)^{\circ n}+\alpha h(0)z^M+O(z^{M+1})\right)^r\\
&=((z^kf)^{\circ n})^r+r\cdot ((z^kf)^{\circ n})^{r-1}\alpha h(0)z^M+O(z^{k^n(r-1)+M+1}).\end{align}$$
Let $f(z)=a_0+a_1z+a_2z^2+\ldots$. 
Then summing $(1)$ using these coefficients we get
$$\begin{align}((z^kf+z^mh)^{\circ n}) &=(z^kf+z^mh)\circ ((z^kf+z^mh)^{\circ n}) \\&=\sum_r a_r(z^kf^{\circ n})^{r+k}+\sum_r a_r(r+k)((z^kf)^{\circ n})^{r+k-1}\alpha h(0)z^M\\
&\quad+h(0)((z^kf)^{\circ n})^m+h(0)m((z^kf)^{\circ n})^{m-1}\alpha h(0)z^M\\&\quad+O(z^{k^n(\min\{m,k\}-1)+M+1})\end{align}$$
Now the first sum is just $(z^kf)^{\circ(n+1)}$. 
The second sum is $$a_0kc_{n,k-1}\alpha h(0)z^{k^n(k-1)+M}+O(z^{k^n(k-1)+M+1}).$$
The third summand is $$h(0)z^{k^nm}+O(z^{k^nm+1})=O(z^{k^n(k-1)+M+1}) $$
because $M<k^n(m-k+1) $.
The fourth summand is 
$$h(0)^2m\alpha z^{k^n(m-1)+M}+O(z^{k^n(m-1)+M+1}) =O(z^{k^n(k-1)+M+1})$$  because $m>k$.
Thus with $M':=k^n(k-1)+M$ (which is $>k^n(k-1)+k^n=k^{n+1}$ and $<k^n(k-1)+k^n(m-k+1)=k^nm\le k^{n+1}(m-k+1)$) we have 
$$(z^kf+z^mh)^{\circ (n+1)}=(z^kf)^{\circ(n+1)}+\alpha'h(0)z^{M'}+O(z^{M'+1}) $$
where 
 $\alpha'=a_0kc_{n,k-1}\alpha\ne 0$.
This shows that the claim also holds for $n+1$. $_\square$
Corollary. Let $n,k\in\mathbb N$, $k\ge2$. Let $f,g$ be holomorphic around $0$ with a root of order exactly $k$ at $z=0$. Then $f^{\circ n}=g^{\circ n}$ implies $f=g$.
Proof. Note that we can write $f(z)=z^kf_0(z)$ and $g(z)=z^kf_0(z)+z^mh(z)$ with $m>k\ge 2$. $_\square$
Proposition. Let $P,Q$ be polynomials such that $P(P(P(x)))=Q(Q(Q(x)))$ for all $x\in\mathbb R$. Then $P=Q$.
Proof.
By the condition, the polynomials $P^{\circ 3}$ and $Q^{\circ 3}$ are the same. If $P(x)=a_nx^n+\ldots$, then $P^{\circ 3}(x) = a_n^{n^2+n+1}x^{n^3}+\ldots$.
We conclude that we can read $\deg P$  from $P^{\circ 3}$, namely $\deg P=\sqrt[3]{\deg P^{\circ 3}}$, and we also obtain $a_n$ because $n^2+n+1$ is odd and odd powers are bijective maps $\mathbb R\to\mathbb R$.
Hence $P,Q$ have the same degree and the same leading coefficient.
In the case $n=0$, we are already done.
In the case $n=1$, say $P(x)=ax+b$, $Q(x)=ax+c$, we have $P(P(P(x)))=a^3x+(a^2+a+1)b$ and $Q(Q(Q(x)))=a^3x+(a^2+a+1)c$. Since for $a\in\mathbb R$ we have $a^2+a+1=(a+\frac12)^2+\frac34>0$, we conclude $b=c$, i.e., $P=Q$ also in this case.
In the case $n\ge 2$, we can consider $f(z)=\frac1{P(z^{-1})}$ and $g(z)=\frac1{Q(z^{-1})}$, which match the conditions of the corollary as both are $\frac1{a_n}z^n+O(z^{n+1})$. $_\square$ 
A: It is easy to see that $P$ and $Q$ have the same leading term.  Without loss of generality, assume that both are monic.  Note that $P$ and $Q$ also have the same constant term. (Note: as zhw has pointed out, this part is not so obvious.  I'll try to update with an argument shortly.)
Suppose that $P\neq Q$.  Since $P-Q$ is not a constant, it is unbounded.  Without loss of generality, there is some $t$ such that $P$ and $Q$ are strictly increasing on $[t,\infty)$, and, for all $a\geq t$, we have $P(a)>Q(a)\geq a$.
Then we have $P(P(P(t))) > P(P(Q(t)) > P(Q(Q(t))) > Q(Q(Q(t)))$, a contradiction.
A: Slade, I had the same approach but I'm not sure how you got the constant terms equal so quickly. But if the degree is $1$ that part is easy and you're done. Otherwise, if $p\ne q,$ then $|p_2(x)-q_2(x)|$ blasts off to $\infty$ as $x\to \infty.$ Because the leading coefficients of $p$ and $q$ agree, this would imply $|p_3(x)-q_3(x)|\to \infty,$ contradiction.
