Let's say a language $L \subseteq \{0,1\}^*$ is in $\textbf{P}_{angel}$ if there exists a polynomial $p : \mathbb{N} \mapsto \mathbb{N}$, a sequence of strings $\{\alpha_n\}_{n \in \mathbb{N}}$ with $\alpha_n \in \{0,1\}^{p(n)}$, and a deterministic polynomial time Turing Machine $M$ such that for every $x \in \{0,1\}^n$ $$x \in L \Leftrightarrow M(x, \alpha_n) = 1$$ Let us call $\alpha_n$ to be the [i]angel string [/i]for all $x$ of the length $n$. Note that the [i]angel string[/i] is $\textbf{not}$ similar to a [i]witness[/i] or [i]certificate [/i]as used in the definition of $\textbf{NP}$ For example, all unary languages, even $UHALT$ which is undecidable, are in $\textbf{P}_{angel}$ because the \textit{angel string} can simply be a single bit that tells us if the given unary string is in $UHALT$ or not. \\\\ A set $S \subseteq \Sigma^*$ is said to be [b]sparse[/b] if there exists a polynomial $p : \mathbb{N} \mapsto \mathbb{N}$ such that for each $n \in \mathbb{N}$, the number of strings of length $n$ in $S$ is bounded by $p(n)$. In other words, $|S^{=n}| \leq p(n)$, where $S^{=n} \subseteq S$ contains all the strings in $S$ that are of length $n$. [list=1] [*] Given $k \in \mathbb{N}$ sparse sets $S_1, S_2 \ldots S_k$, show that there exists a sparse set $S$ and a deterministic polynomial time TM $M$ with oracle access to $S$ such that given an input $\langle x,i \rangle$ the TM $M$ will accept it if and only if $x \in S_i$. \\Define the set $S$ (note that it need not be computable), and give the description of $M$ with oracle $S$. \\Note that a TM $M$ with oracle access to $S$ can query whether $s \in S$ and get the correct answer in return in constant time. [/*] [*] Let us define a variant of $\textbf{P}_{angel}$ called $\textbf{P}_{bad-angel}$ with a constraint that there should exists a polynomial time algorithm that can [b]compute[/b] the angel string for any length $n \in \mathbb{N}$. In other words, there is a poly-time algorithm $A$ such that $\alpha_n = A(n)$. \\Is $\textbf{P} =\textbf{P}_{bad-angel}$? Is $\textbf{NP}=\textbf{P}_{bad-angel}$? Justify. [/*] [*] Let the language $L \in$ $\textbf{P}_{angel}$. Show that there exists a sparse set $S_L$ and a deterministic polynomial time TM $M$ with oracle access to $S_L$ that can decide the language $L$. [/*]

Let $P_k(x) = (x-k)(x-(k+1))$. Kara picks four distinct polynomials from the set $\{P_1(x), P_2(x), P_3(x), \ldots ,$ $P_{12}(x)\}$ and discovers that when she computes the six sums of pairs of chosen polynomials, exactly two of the sums have two (not necessarily distinct) integer roots! How many possible combinations of four polynomials could Kara have picked? [i]Proposed by Andrew Wu[/i]

Find all real polynomials $ p(x)$ of degree $ n \ge 2$ for which there exist real numbers $ r_1 < r_2 < ... < r_n$ such that (i) $ p(r_i) \equal{} 0, 1 \le i \le n$, and (ii) $ p' \left( \frac {r_i \plus{} r_{i \plus{} 1}}{2} \right) \equal{} 0, 1 \le i \le n \minus{} 1$. [b]Follow-up:[/b] In terms of $ n$, what is the maximum value of $ k$ for which $ k$ consecutive real roots of a polynomial $ p(x)$ of degree $ n$ can have this property? (By "consecutive" I mean we order the real roots of $ p(x)$ and ignore the complex roots.) In particular, is $ k \equal{} n \minus{} 1$ possible for $ n \ge 3$?

Determine all real numbers $a, b, c, d$ such that the polynomial $f(x) = ax^3 +bx^2 + cx + d$ satisfies simultaneously the folloving conditions $\begin {cases} |f(x)| \le 1 \,for \, |x| \le 1 \\ f(2) = 26 \end {cases}$

Find all real numbers $ a,b,c,d$ such that \[ \left\{\begin{array}{cc}a \plus{} b \plus{} c \plus{} d \equal{} 20, \\ ab \plus{} ac \plus{} ad \plus{} bc \plus{} bd \plus{} cd \equal{} 150. \end{array} \right.\]

Let $P_0(x) = x^3 + 313x^2 - 77x - 8$. For integers $n \ge 1$, define $P_n(x) = P_{n - 1}(x - n)$. What is the coefficient of $x$ in $P_{20}(x)$?

$P$ is an monic integer coefficient polynomial which has no integer roots. deg$P=n$ and define $A$ $:=${$v_2(P(m))|m\in Z, v_2(P(m)) \ge 1$}. If $|A|=n$, show that all of the elements of $A$ is smaller than $\frac{3}{2}n^2$.

$f(x)$ is square trinomial. Is it always possible to find polynomial $g(x)$ with fourth degree, such that $f(g(x))=0$ has not roots?

Is there a triangle with angles in ratio of $ 1: 2: 4$ and the length of its sides are integers with at least one of them is a prime number? [i]Nanang Susyanto, Jogjakarta[/i]

The polynomial $R(x)$ is the remainder upon dividing $x^{2007}$ by $x^2-5x+6$. $R(0)$ can be expressed as $ab(a^c-b^c)$. Find $a+c-b$.

Consider a quadratic polynomial $ax^2+bx+c$ with real coefficients satisfying $a\ge 2$, $b\ge 2$, $c\ge 2$. Adam and Boris play the following game. They alternately take turns with Adam first. On Adam’s turn, he can choose one of the polynomial’s coefficients and replace it with the sum of the other two coefficients. On Boris’s turn, he can choose one of the polynomial’s coefficients and replace it with the product of the other two coefficients. The winner is the player who first produces a polynomial with two distinct real roots. Depending on the values of $a$, $b$ and $c$, determine who has a winning strategy.

Let $p(z)=a_0+a_1z+a_2z^2+\cdots+a_nz^n$ be a complex polynomial. Suppose that $1=c_0\ge c_1\ge \cdots \ge c_n\ge 0$ is a sequence of real numbers which form a convex sequence. (That is $2c_k\le c_{k-1}+c_{k+1}$ for every $k=1,2,\cdots ,n-1$ ) and consider the polynomial \[ q(z)=c_0a_0+c_1a_1z+c_2a_2z^2+\cdots +c_na_nz^n \] Prove that : \[ \max_{|z|\le 1}q(z)\le \max_{|z|\le 1}p(z) \]

For a polynomial $ P$ of degree 2000 with distinct real coefficients let $ M(P)$ be the set of all polynomials that can be produced from $ P$ by permutation of its coefficients. A polynomial $ P$ will be called [b]$ n$-independent[/b] if $ P(n) \equal{} 0$ and we can get from any $ Q \in M(P)$ a polynomial $ Q_1$ such that $ Q_1(n) \equal{} 0$ by interchanging at most one pair of coefficients of $ Q.$ Find all integers $ n$ for which $ n$-independent polynomials exist.

Two graphs $G_1$ and $G_2$ of quadratic polynomials intersect at points $A$ and $B$. Let $O$ be the vertex of $G_1$. Lines $OA$ and $OB$ intersect $G_2$ again at points $C$ and $D$. Prove that $CD$ is parallel to the $x$-axis.

Find all integers $ n\ge 2$ having the following property: for any $ k$ integers $ a_{1},a_{2},\cdots,a_{k}$ which aren't congruent to each other (modulo $ n$), there exists an integer polynomial $ f(x)$ such that congruence equation $ f(x)\equiv 0 (mod n)$ exactly has $ k$ roots $ x\equiv a_{1},a_{2},\cdots,a_{k} (mod n).$