Pages

Bookmark and Share

Friday, December 15, 2017

Monic polynomial divisible by 2018

Let $P(x)$ a monic polynomial (polynomial having leading coefficient one) with integer coefficients such that $P(k)$ is divisible by 2018 for all integer $k$. Find the smallest possible degree of $P$

Solution

Note that $P(x) = x(x+1)(x+1) \dots (x+1008)$ is always divisible by 1009, because one of the factors is always divisible by 1009. It's also even. Therefore $P(x)$ is a polynomial that satisfies the problem requirement, having degree 1009. We shall show that this degree is minimal.

We call a polynomial (not necessarily monic) "good" if it has property that $P(k)$ is divisible by 2018 for all integer $k$.

Suppose $P_n(x)$ is a good monic polynomial having degree $n$, then we apply the following procedure: let $P_{n-1}(x) = P_n(x+1) - P_n(x)$. Then $P_{n-1}$ is a polynomial of degree $n-1$ (because the $x^n$ terms cancel out). Because $P_n$ is good, then $P_{n-1}$ is also good. Furthermore, the leading coefficient of $P_{n-1}$ is $n$, because the only source of $x^{n-1}$ terms is from the expansion of $(x+1)^n$. The other $x^{n-1}$ terms cancel out as well.

We continue this process to obtain $P_{n-2}, P_{n-3},$ and so on. At each step, define $P_m(x) = P_{m+1}(x+1) - P_{m+1}(x)$. We claim the following facts:

1. $P_m$ is good

2. The leading coefficient of $P_m$ is $n(n-1)(n-2) \dots (m+1) = \frac{n!}{m!}$

The two facts can be shown simultaneously using induction. It's obviously true for $m=n$, and as we demonstrated, it's also true for $m=n-1$. If it's true for $m+1$ then it's easy to see that it's true for $m$ as well, using the same argument we showed above.

Thus, at some point, we will arrive at $P_0$ having leading coefficient $n!$. That is, $P_0(x) = n!$ for all $x$, and this must be divisible by 2018 because $P_0$ is good. Therefore $n!$ is divisible by 2018.

What we showed was the necessary condition for a monic polynomial to be good. That is, if it has degree $n$ then $n!$ is divisible by 2018. The smallest possible such $n$ is 1009 because 1009 is prime. But we also showed a sufficient condition, that there exists a polynomial with degree 1009 that's both monic and good. Thus the answer is 1009.

Wednesday, December 13, 2017

Non-attacking rooks

Given an $n \times n$ chess board and $2n+1$ rooks placed on it, prove that we will always be able to choose 3 rooks who can't attack each other.

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

For $n$ natural number, and $a = \frac{2\pi}{2n+1}$ find the value of $$\cos a . \cos 2a . \cos 3a . \dots . \cos na$$

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

In an island with 257 cities, there are 2018 railroad segments such that each segment connects exactly 2 cities, and each pair of cities are connected by at most 1 segment. A group of 10 cities is called "clustered" if each pair of those 10 is connected by a segment.

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

Find the number of subsets of $n$ such that if $i$ does not belong in the subset then either $i+1$ or $i-1$ belongs to the subset. (Hint: use double recursion, use fibonacci series)

Tuesday, October 10, 2017

symmetric 2 variable function

Suppose $S = \{1,2,\dots,n\}$ and $f: S \times S \to R$ satisfies the following: $$f(i,j) + f(j,i) = 0 \forall i,j \in S$$ Now for any two number $i,j$, we say that $i$ is superior to $j$ if there exists a $k$ (not necessarily distinct from $i,j$) such that $f(i,k) + f(k,j) \geq 0$. Show that there exists a number $x \in S$ such that $x$ is superior to all elements of $S$.

Sunday, October 8, 2017

Combinatorial Proof

Give a combinatorial proof of this identity: $$n(n+1)2^{n-2} = \sum_{k=1}^n k^2 {n \choose k}$$ 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}$

Wednesday, September 20, 2017

Coloring polygon vertices

The vertices of a regular $n$-gon ($n \geq 3$) are to be colored with one of the $k$ colors such that no two adjacent vertices may have the same color. Let $f(n)$ be the number of legal coloring. Find a closed formula for $f(n)$.

Solution:

Suppose we sever one of the edges temporarily, so that we're left with a "string" of length $n$ where the first and last vertices are not connected. In order to color this string, we may color the first vertex $k$ ways, but each of the subsequent vertices may only be colored $k-1$ ways, avoiding the color of the previous vertex. Suppose $g(n)$ is the number of ways to color a string of length $n$, then $g(n) = k(k-1)^{n-1}$

Now, take one of these colored strings of length $n$ and join the first and last vertices. The resulting polygon may or may not be a valid coloring. It is not a valid coloring if and only if the first and last vertices have the same color. The number of such invalid coloring is the same as $f(n-1)$. There is a bijection between the invalid coloring where the first and last vertices have the same color and a valid coloring of an $(n-1)$-gon.

So: $$f(n) = g(n) - f(n-1)$$ Now, $f(3) = k(k-1)(k-2)$. So: $$f(4) = k(k-1)^3 - f(3) = k(k-1)(k^2 -3k+3) =(k-1)((k-1)^3+1)$$ $$f(5) = k(k-1)^4 - f(4) = k(k-1)(k^3-4k^2+6k-4) = (k-1)((k-1)^4-1)$$ $$f(6) = k(k-1)^5 - f(5) = (k-1)((k-1)^5+1)$$ So we can see a pattern, which we can prove via induction easily.

$$f(n) = (k-1)((k-1)^{n-1}+(-1)^n)$$

ODE discrete version

If $f$ is a function that is defined over natural numbers ($f:N \to R$), let $f^*$ denote the function $f^*(n) = f(n) - f(n-1)$. Find all functions such that $$n(f^*)^*(n) + (n-1)f^*(n) = f(n)$$ for all $n > 2$

Solution We can check that $f(n) = A(n-1) + B/2^n$ for any constant $A,B$ satisfies the given equation. Now we show that there's nothing else.

Define $g = f^*+f$. The equation is identical to: $$n(f^*+f)^*(n) =(f^*+f)(n)$$ $$ n(g(n) - g(n-1)) = ng^*(n) = g(n)$$ $$\frac{g(n)}{n} = \frac{g(n-1)}{n-1}$$ for all $n>2$, therefore $g(n)/n$ must be a constant. Remember that $g(1)$ is not defined because $f$ is only defined for $n \geq 1$ thus $g$ is only defined for $n \geq 2$. Furthermore, the value $g(2)$ depends on $f(1)$ and $f(2)$.

Case 1: $g(2) = 0$ In this case then $g(n) = 0 \forall n$. $$(f^*+f)(n) = 0$$ $$f(n) = f(n-1)/2$$ so we easily get $f(n) = k/2^n$ for some constant $k$.

Case 1: $g(2) \neq 0$ Note that if $f$ is a solution to the problem then $kf$ is also a solution to the problem, for all $k$ real numbers. If we replace $f$ by $kf$, then $g$ is also replaced by $kg$. So WLOG, we may assume that $g(2) = 2$

Because $g(n) / n$ is a constant then $$g(n) / n = g(2) / 2 = 1$$ so $g(n) = n \forall n >2$ $$f(n) = \frac{f(n-1) + n}{2}$$ for all $n > 2$.

Because $g(2) = 2 = 2f(2) - f(1)$ then $f(2) = 1+ f(1)/2$ Now notice this pattern: $$f(3) = \frac{f(2) + 3}{2} = 2 + f(1)/4$$ $$f(4) = \frac{f(3) + 4}{2} = 3 + f(1)/8$$ Easy to prove by induction that $f(n) = n-1 + f(1)2^{1-n}$.

From the two cases above, it's clear that any solution of the equation must be in the form of $f(n) = A(n-1) + B/2^n$ for any constant $A,B$