Pages

Saturday, September 25, 2010

Completable Paintings

An $n \times n$ checker board is painted all white except $m$ cells that are painted black. At each step, one is allowed to choose a rectangle that has three black corners, and paint the fourth corner black. A configuration is called completable if one can paint the entire board black using a sequence of steps described above.

First Question:
Find the smallest $m$ such that any configuration with $m$ black cells are always completable.

Second Question:
Find the smallest $m$ such that there is a completable configuration with $m$ black cells.

Thursday, September 16, 2010

Ternary Polynomial

A polynomial with integer coefficients is called "ternary" if its coefficients are all 1, -1, or zero.

First Question:
Find two polynomials $P(x)$ and $Q(x)$ with integer coefficients where at least one coefficient is larger than 2010, such that $P(x)Q(x)$ is ternary.

Second Question:
Does there exist a ternary multiple of $F(x) = x^2 - 3x + 1$ ?

Solution

First Question

Note that the polynomial $(x-1)(x^2-1)(x^4-1)(x^8-1) ... (x^{2^n}-1)$ is ternary. Indeed, because the coefficient of $x^k$ can only be formed in exactly one way. For digits in the binary representation of $k$ that is one, we take the $x^{2^i}$ term, and for the other digits, we take the $-1$ term.

Now, that polynomial can be factored. For example:
$$(x-1)(x^2-1)(x^4-1)(x^8-1)$$
$$=(x-1)^{4} (x+1) (x^3+x^2+x+1) (x^7+...+1)$$
$$=(x-1)^{4) (x+1) (x+1)(x^2+1) (x+1)(x^2+1)(x^4+1)$$
$$=(x-1)^4 (x+1)^3 (x^2+1)^2 (x^4+1)$$

So similarly,
$$(x-1)(x^2-1)(x^4-1)(x^8-1) ... (x^{2^n}-1)$$
$$ = (x-1)^{n+1} (x+1)^n (x^2+1)^{n-1} ... (x^{2^{n-1}}+1) $$

If we let $P(x) = (x-1)^{n+1}$ and $Q(x)$ to be the rest, we claim that we can make the largest coefficient in $P$ and $Q$ to be arbitrarily large by setting $n$ large enough. For $P$, it is clear due to binomial expansion. For $Q$, the factor $(x+1)^n$ will have a large enough coefficient, while the rest of the factors all consist of positive signs (no negative signs).

So by setting $n$ large enough, we could find $P$ and $Q$ that satisfy the desired conditions.

Second Question

We start by proving a lemma: if $s > 2$ then $s^n > s^{n-1} + ...+ s + 1$. This lemma can be proved by induction:
$s^{n+1} > 2s^n = s^n + s^n > s^n + ... + s + 1$

Now, we note that the larger root of $F$ is greater than 2, so let $r$ be this larger root. ( $r = (3 + \sqrt{13})/2 > 2$ ).

Suppose $P$ is a ternary polynomial such that $P(x) = F(x) G(x)$ for some integer polynomial $G$, then $P(r) = 0$.

But that is impossible if $r > 2$, due to the lemma above, since the largest term in $P$ cannot be offset by the rest of the terms. A contradiction.

Wednesday, September 1, 2010

Integral Inequality

Prove that:

$$\left( \int_\pi^\infty\frac{\cos x}{x}\ dx\right)^{2} < \frac{1}{{\pi}^{2}} $$

Solution

Integrate by parts:

$$\int \frac{\cos x}{x} dx = \frac{\sin x}{x} + \int \frac{\sin x}{x^2} dx$$

So
$$\int_\pi^\infty\frac{\cos x}{x}\ dx = \int_\pi^\infty \frac{\sin x}{x^2} dx$$

And
$$| \int_\pi^\infty\frac{\cos x}{x}\ dx| = |\int_\pi^\infty \frac{\sin x}{x^2} dx|$$
$$\leq \int_\pi^\infty \frac{| \sin x |}{x^2} dx$$
$$\leq \int_\pi^\infty \frac{1}{x^2} dx $$
$$= \frac{1}{\pi}$$