## Friday, December 15, 2017

### Monic polynomial divisible by 2018

## Wednesday, December 13, 2017

### Non-attacking rooks

**Solution**

Partition the board into $n$ groups in a "broken diagonal" pattern. That is, cell $(i,j)$ belongs to group $i+nj \mod n$. Two cells in the same group can't attack each other (easily shown either by diagonal argument or modular analysis).

Because there are $2n+1$ rooks, then there are 3 rooks that sit on the same group.

### Product of cosines

**Solution**

We first prove the following claim: for any $n$ positive odd number, $$\sin (nx) = \sin x P_n (\cos x)$$ $$\cos (nx) = \cos x Q_n (\cos x)$$ where $P_n(t)$ and $Q_n(t)$ are polynomials in the form of $2^{n-1} t^{n-1} + ...$ (In other words, they have degree $n-1$ and the leading coefficient $2^{n-1}$

Proof by induction, evident for $n=1$ and $n=3$. Inductive step: $$\sin (n+2)x = \sin nx \cos 2x + \cos nx \sin 2x = \sin x P_n (\cos x) (2 \cos^2 x - 1) + \cos x Q_n (\cos x) .2\sin x \cos x$$ $$ = \sin x ( P_n (\cos x) (2 \cos^2 x - 1) + 2\cos^2 x Q_n (\cos x) ) = \sin x P_{n+2} (\cos x)$$ where $P_{n+2}$ has degree $n+2$ and the leading coefficient $2. 2^{n-1} + 2.2^{n-1} = 2^{n+1}$

Likewise: $$\cos (n+2) x = \cos nx \cos 2x - \sin nx \sin 2x = \cos x Q_n(\cos x)(2 \cos^2 x - 1) - \sin x P_n (\cos x) . 2 \sin x \cos x$$ $$ = \cos x ( Q_n(\cos x)(2 \cos^2 x - 1) - 2 P_n (\cos x) (1 - \cos^2 x)) = \cos x Q_{n+2} (\cos x)$$ like before, the polynomial $Q_{n+2}$ has degree $n+2$ and leading coefficient $2^{n+1}$

So now, observe that $x = 0,a,2a, \dots, 2na$ are all solutions of the equation $$\cos (2n+1)x = 1 = \cos x Q_{2n+1}(\cos x)$$ Therefore $t = \cos 0, \cos a, \dots, \cos 2na$ are all roots of the polynomial $$ S(t) = tQ_{2n+1}(t) - 1$$ Because $S(t)$ has degree $2n+1$, then $\cos 0, \dots \cos 2na$ are ALL of the roots, and the product of all those roots is $\frac{1}{2^{2n}}$ (because $S(t)$ has leading coefficient $2^{2n}$

Now, $\cos a = \cos 2n a, \cos 2a = \cos (n-1) a$ and so on. So: $$\cos 0 . \cos a .\dots. \cos 2na = 1 . (\cos a. \dots . \cos na)^2 = \frac{1}{2^{2n}}$$ So: $$\cos a . \dots . \cos na = \frac{1}{2^n}$$

## Wednesday, October 11, 2017

### A tale of two cities

Prove that there exist 2 unconnected cities that we can connect without increasing the number of clustered groups.

**Solution**

Proof by contradiction. Suppose we cannot connect two cities without increasing the number of clustered groups.

Let $n=257$ be the number of cities. Take all possible groups of 10 cities, ${n \choose 10 }$ of them, and count how many segments there are among them. Of course, if the group is clustered, it should have ${10 \choose 2} = 45$ segments. Let $S$ be the sum of unconnected pairs, over all possible groups of 10 cities.

Now let us count $S$ in a different way. Take 2 connected cities $A$ and $B$. The segment $AB$ contributes to $S$ only when the chosen group of 10 cities include $AB$, so this segment is counted ${n-2 \choose 8}$ times. Because there are 2018 segments, then $S$ must be:

$$S = {n-2 \choose 8}.(2018)$$

Note that $2018 < 2020 = 8n-36$, so $S < {n-2 \choose 8}.(8n-26)$. That means, on average, there are $S / {n \choose 10 }$ segments.

### Non-adjacent subsets

## Tuesday, October 10, 2017

### symmetric 2 variable function

## Sunday, October 8, 2017

### Combinatorial Proof

**Solution**

Let's say in a class there are $n$ students and you are asked to select one or more students, with the caveat that Joe must be selected. For each student that is selected, the whole class gets 1 dollar. So what is the expected value of the class' income?

Or if you want a non-probabilistic way to think about it, then over all the possible ways to select students, what is the sum of class income in all of those scenarios?

First way to count: Say there are $k \geq 1$ students who are selected (including Joe). There are $n-1 \choose k-1$ ways to choose the students (because Joe must be selected). So this particular way of selecting the students has $k {n-1 \choose k-1} = \frac{k^2}{n} {n \choose k}$ income. So the sum of all income over all scenarios is $\sum_{k=1}^n \frac{k^2}{n} {n \choose k}$

Second way to count: Consider a student, not Joe. How many dollars does he contribute to the total class income? He contributes 1 dollar everytime he is selected, which is $2^{n-2}$ times (because both he and Joe must be selected for him to contribute, so the other $n-2$ students can be chosen freely, selected or not selected). There are $(n-1)2^{n-2}$ contributions from these, because there are $n-1$ students that are not Joe.

But how many dollars did Joe contribute? He ALWAYS contributes 1 dollar for every selection, and there are $2^{n-1}$ selections total. So there are $2^{n-1}$ contributions from Joe.

So the total contribution is $(n-1)2^{n-2} + 2^{n-1} = (n+1)2^{n-2}$