Find angle C

From AMC12 1999:

In triangle $ABC$,
$3 \sin A + 4 \cos B = 6$
$4 \sin B + 3 \cos A = 1$

Find $\angle C$

a,b,c,d odd powers

If $a,b,c,d$ are integers such that $a+b+c+d = 0$ then show that for any odd number $n$,

$$X_n = a^n + b^n + c^n + d^n$$

is divisible by $Y = \sqrt{-(a+b)(a+c)(a+d)(b+c)(b+d)(c+d)}$

And that if $n$ is prime, then $X_n$ is divisible by $n$ as well

First Solution

First, it is straightforward to show that $Y$ is indeed an integer.
$a+b = -(c+d)$
$a+c = -(b+d)$
$a+d = -(b+c)$
Multiplying all three, we have that $Y = |(a+b)(b+c)(c+a)|$
If $Y=0$, then $X_n = 0$ as well. So now we're going to assume that $Y > 0$. For proving divisibility purposes, we can also assume that $Y = (a+b)(b+c)(c+a)$.

Let $f(t) = (t-a)(t-b)(t-c) = t^3 - Pt^2 + Qt - R$ be a polynomial with roots $a,b,c$

We have that $Y=(a+b)(b+c)(c+a) = (P-a)(P-b)(P-c) = f(P) = PQ-R$.

Let's also define $S_n = a^n + b^n + c^n$. All we have to show is that $S_n - P^n$ is divisible by $Y$ for $n$ odd.

Now we assert the following, and prove by induction:
If $n$ is odd, then $S_n - P^n$ is divisible by $Y$
If $n=2m$ is even, then $S_n - P^n - 2(-Q)^m$ is divisible by $Y$.

We readily obtain that $S_1 = P$ and $S_2 = P^2 - 2Q$, so the assertions above are true for $n=1,2$.

Now for higher values of $n$, we have the following:
$a^{n-3}f(a) = a^n - Pa^{n-1} + Qa^{n-2} - Ra^{n-3} = 0$
similarly we can do the same for $b,c$ and add them, so that we have:
$S_n = PS_{n-1} - QS_{n-2} + RS_{n-3}$

If $n=2m$ is even, then $n-1$ is odd, $n-2 = 2(m-1)$ is even, and $n-3$ is odd. So from induction hypothesis, we can write:
$S_{n-1} = P^{n-1} + YZ_1$
$S_{n-2} = P^{n-2} + 2(-Q)^{m-1} + YZ_2$
$S_{n-3} = P^{n-3} + YZ_3$

where $Z_1, Z_2, Z_3$ are integers
So:
$$S_n = P^n + PYZ_1 - P^{n-2}Q + 2(-Q)^m -QYZ_2 + RP^{n-3} + RYZ_3$$
$$= P^n + 2(-Q)^m + P^{n-3}(PQ-R) + Y(PZ_1 - QZ_2 + RZ_3)$$
$$= P^n + 2(-Q)^m + Y(P^{n-3} + PZ_1 - QZ_2 + RZ_3)$$

which proves our induction assertion that $S_n - P^n - 2(-Q)^m$ is divisible by $Y$. For $n$ odd, we can do the same.

So $S_n - P^n = X_n$ is divisible by $Y$ for $n$ odd.

Second Solution

We have $d = -(a+b+c)$, then
$$X_n = a^n + b^n + c^n - (a+b+c)^n$$ if $n$ is odd.

For fixed values of $b,c$, let $f(a) = a^n + b^n + c^n - (a+b+c)^n$ by a polynomial of degree $n-1$ in $a$.
Note that $f(-b) = 0$ and $f(-c) = 0$. That means $X_n = f(a)$ is divisible by $(a+b)(a+c)$.

Write $f(a) = (a+b)(a+c)P(a)$ for $P$ some integer polynomial.
Now note that $f(a) = a^n - (a+b+c)^n + (b^n + c^n)$
$a^n - (a+b+c)^n$ is divisible by $(b+c)$ in a polynomic manner (not just integer divisibility), and so is $b^n + c^n$ (since $n$ is odd).

So $f(a)$ is divisible by $(b+c)$ in a polynomic manner, which means $P(a)$ is divisible by $(b+c)$.

Triangular (and tetrahedral) lattice

An equilateral triangle $ABC$ with side $n$ a positive integer is divided into triangular lattice consisting of unit triangles.

Each point on the lattice is colored red, white, or blue such that:
1. No point on $AB$ is colored red
2. No point on $BC$ is colored blue
3. No point on $AC$ is colored white

Prove that there exists a unit triangle whose vertices are colored with 3 different colors.

Challenge problem: Same problem but for tetrahedron and four colors.

Solution

We first state the one-dimensional version of this problem:

Given a sequence of points on a line colored red or blue, and the first point must be colored red, and the last point must be colored blue, then we have an ODD number of segments that has two differently-colored end points.

This one-dimensional version is trivial to prove.

Now we turn to the 2-dimensional version as stated in the problem.
For each side that has both red and blue endpoints, we "mark" that side.
Then for each unit triangle, we give it a score based on how many marked sides it has. Now, if we consider the "outside" area as another "surrogate unit triangle", then we can also give it a score based on how many marked sides are facing the outside.

First, note that the total score of all areas must be even, since any marked side contribute one score to two areas.

Now, applying the 1-dimensional version of the problem, we know that side AC has an odd number of marked sides. Side AB and BC does not have any marked sides. So the outside area has an odd score. Thus, there is an odd number of unit triangles that has an odd score. In order for a unit triangle to have an odd score, it must have three differently-colored vertices.

Number of black cells

Each cell on an $n \times n$ checkerboard is to be painted black or white.

How many ways are there to paint the board such that each column and each row contains an even number of black cells?

How many ways are there to paint it such that each column and row contains an odd number of black cells?

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.

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.

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}$$