Solução 1:
Note que $$\angle CDZ=\angle CDE=\angle BDE+\angle BED=90^{\circ}+\angle B$$ e sabemos que $$\angle ZBC=\angle OBC=90^{\circ}-\angle B$$, logo $$\angle ZDC+\angle ZOC=90^{\circ}+\angle B+90^{\circ}-\angle B=180^{\circ}$$. Logo o quadrilátero é cíclico!
Solução 2:
Façamos um grafo G com vértices $$\{ 1,2,3,\dots, p\}$$. Ligamos uma aresta entre os vértices $$i$$ e $$j$$ com a cor
$$k\equiv -\frac{a_j-a_i}{j-i} \pmod p$$
Com $$0\le k< p$$, assim, usamos no máximo p cores nas arestas e temos $$\binom p2$$ arestas. assim, alguma cor foi usada menos que $$\frac 1p \binom p2=\frac{p-1}2$$ Assim, existe um subgrafo de $$G$$ com \frac{p-1}2 arestas e $$p$$, vamos provar que esse grafo tem pelo menos $$\frac{p+1}2$$ componentes conexas:
Como uma componente conexa é pelo menos uma árvore $$\implies$$ número de arestas de cada componente conexa $$\ge$$ número de vértices de cada componente $$-1$$, assim, $$\mbox{#arestas}\ge \mbox{#vertices} -\mbox{#componentes conexas}\implies \frac{p-1}2\ge p-\mbox{#componentes conexas}\implies \mbox{#componentes conexas}\ge \frac{p+1}2\ge \frac p2$$, assim, existe uma cor com pelo menos $$\frac p2$$ restos distintos, como queríamos.
Solução 3:
Veja que, para todo $$r\in \mathbb{R}$$ tal que $$P(r)\in \mathbb{Z}\implies P(2r)\in \mathbb{Z}$$. Assim, seja $$Q(x)=P(2x)-2^dP(x)$$, onde $$d=deg P$$. Veja que o grau de $$Q$$ é no máximo $$d-1$$ e que o conjunto
$$A=\{ x\mid P(x)\in \mathbb{Z}\} \subseteq B=\{ x\mid Q(x)\in \mathbb{Z}\} $$
sabemos que $$P,Q$$ são eventualmente monótonos, se que não é constante ($$\exists M\in\mathbb{N}\mbox{tal que} \forall m>M P(m)>P(m-\epsilon), Q(m)>Q(m-\epsilon)\forall\epsilon>0$$). Logo,
$$|Q(M+r)-Q(M)\ge |B\cap [Q(M),Q(M+r)]|\ge A\cap [P(M),P(M+r)]|=P(M+r)-P(M),r\in \mathbb{N}$$
Veja que isso é um polinômio de grau $$d$$ em função de $$r$$, que sempre é menor que um polinômio de grau menor que $$d\rightarrow Abs! $$
Assim, $$Q$$ é constante $$\implies 2^dP[x^i]=Q[x^i]\forall i\neq 0\implies 2^da_i=2^ia_i\implies a_i=0\implies P(x)=ax^d+c$$. é fácil provar que isso só vai funcionar quando $$a=1$$