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)$.


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$

Thursday, August 11, 2016

Polynomial and divisibility

Find an integer polynomial $P(x)$ with the lowest degree that satisfies the following:

$P(x)$ is divisible by $x^2+x+1$

$P(x)+3$ is divisible by $x^{2017} -1$


Let $Q(x) = x^2+x+1$ and $R(x) = x^{2016} + \dots + 1$. It's easy to show that $Q$ and $R$ are relatively prime.

The LCM for both divisors is thus $(x-1)Q(x)R(x)$ which has degree 2019.

Now if $P$ and $P'$ both satisfy the problem statement, then $P-P'$ must be divisible by $(x-1)Q(x)R(x)$.

On the other hand, if $P$ satisfies the problem statement, then $P + A(x).(x-1)Q(x)R(x)$ also satisfies the problem statement for any integer polynomial $A(x)$.

Therefore, we can find at most one $P(x)$ with degree less than 2019, because if there were two such polynomials, their difference must be divisible by $(x-1)Q(x)R(x)$ but that difference has degree less than 2019, so the difference must be zero. That one polynomial is our answer.

To find it: let $t$ be the root of $Q(x)$. We want to find $P(x)$ such that:

$$P(x)+3 = S(x).(x-1).R(x)$$ for some $S(x)$, with $S(x) = ax+b$. We know that it's possible for $S$ to be a linear function because we've established that there exists a $P$ with degree less than 2019, and $R$ has degree 2016.

$$P(t) + 3 = (at+b).(t-1).R(t)$$

$P(t) = 0$ because $P(x)$ is divisible by $Q(x)$ and $Q(t) = 0$.

$R(t) = t^{2016} + \dots + t + 1 = 1$ because every 3 consecutive terms in $t^{2016} + \dots + t$ sum to zero (because $Q(t) = 0$).

So: $$ 3 = (at+b)(t-1)$$ $$at^2 + (b-a)t - b-3 = 0$$ $$a(-t-1) + (b-a)t - b-3 = 0$$ $$ (b-2a)t=a+b+3$$

Solving for the system:$b-2a = 0, a+b+3 = 0$ gives us: $a = -1, b= -2$ so $S(x) = -(x+2)$

Plugging in to the equations, we find:

$$P(x) = -(x+2)(x^{2017}-1) - 3 = -x^{2018} - 2x^{2017} + x -1 = -x^2(x^{2016}-1) -2x(x^{2016}-1) -( x^2+x+1) $$

Each term in the right-most expression is divisible by $Q(x)$ because $(x^{2016}-1)$ is divisible by $x^3-1$ so $P(x)$ is also divisible by $Q(x)$

Wednesday, March 30, 2016

Spanning set

Let $S = \{0,1,2,\dots,10\}$.

A set of numbers $A \subset S$ is called "spanning" if the set $\{ x, x+1, x+2, x+3 \mod 11 | x \in A \} = S$.

And a set of numbers $B \subset S$ is called "potentially spanning" if there is an integer $k$ such that the set $\{kb \mod 11 | b \in B \}$ is spanning.

Prove that every subset of $S$ with four elements are potentially spanning, and prove that there exists a subset of $S$ with three elements that is not potentially spanning.

Solution First, we show that there is a subset of three elements that is not potentially spanning.

Note that for a set to be spanning, it has to be $\{c,c+4, c+8\}$ for some $c$ (here we assume everything is modulo 11, so we don't write it for notational simplicity). This is because the maximum distance between two adjacent element is 4, so the distances between 3 elements must be 4+4+3 (or its rotation).

Now we claim that a set $\{x,y,z\}$ is potentially spanning if and only if there exists $r \neq 0$ and $s$ such that $\{x,y,z\} = \{r+s, 2r+s, 3r+s \mod 11\}$. First, clearly if a set is spanning, then all of its "rotations" are also spanning sets. Likewise, if a set is potentially spanning, then all of its rotations are also potentially spanning. So wlog we may assume that $s=0$. Then the set $\{r,2r,3r\}$ is potentially spanning because we can always take $k = 4r^{-1} \mod 11$ so that $\{kr,2kr,3kr\} = \{4,8,12=1\}$ a spanning set. The inverse modulo is guaranteed to exist because 11 is prime and $r \neq 0$.

Now the other direction. Suppose $\{x,y,z\}$ is potentially spanning, such that $\{kx,ky,kz\}$ is spanning. As we've established above, it must have form $\{c,c+4, c+8\}$ for some $c$. Thus we can take $r = 4k^{-1} \mod 11$ and $s = (c-4)k^{-1} \mod 11$ so that $\{k(r+s),2kr,3kr\} = \{4+ks,8+ks,12+ks\} = \{c,c+4,c+8\}$.

So we have shown that the potentially spanning sets are generated by (and only by) the number of $(r,s)$ pairs we can choose. There are 10 choices for $r$ and 11 for $s$, so there are at most 110 potentially spanning sets. We say at most because some choices of $r$ and $s$ may "collide" (result in the same spanning triplet). However, there are ${11 \choose 3} = 165$ possible triplets, so there are some triplets that are not generated by the $(r,s)$ construction above and thus not potentially spanning.

Now we show that a subset $B = \{b_1,b_2,b_3,b_4\}$ is always potentially spanning. Note that if any three of $b_i$s form a potentially spanning triplet then $B$ is potentially spanning. In particular, if $B$ contains an arithmetic sequence modulo 11 then $B$ is potentially spanning. So we assume that $B$ is free from arithmetic progression.

Now let $d_i = b_{i+1} - b_i$ (of course we mean $b_5 = b_1$. Then among all four $d_i$s, let $d$ be the maximal distance. If the maximal distance is 4, then we are done because $B$ itself is spanning. So we assume that the maximal distance is at least 5. Wlog, we may assume that this maximal distance is $d_4$ and that $b_1 = 0$. So this means $0=b_1 < b_2 < b_3 < b_4 = 11-d$ and $b_i$ must not contain arithmetic sequence. It's easy to see that the only possible combinations are:

Case 1: $d=5$, so $0=b_1 < b_2 < b_3 < b_4 = 6$. The only combinations are $\{0,1,4,6\}, \{0,1,5,6\},\{0,2,5,6\}$. All the other combinations contain an arithmetic sequence. But in the first two cases, we can take $k=8$ to get: $\{0,4,8,10\}, \{0,4,7,8\}$ which contains arithmetic sequence thus potentially spanning, and for the third case we can take $k=3$ to get $\{0,4,6,7\}$ which is spanning.

Case 2: $d=6$, so $0=b_1 < b_2 < b_3 < b_4 = 5$. The only combinations are $\{0,1,4,5\}$ and $\{0,2,3,5\}$. We can take $k=4$ to get $\{0,4,5,9\}$ and $k=2$ to get $\{0,4,6,10\}, both spanning sets.

Case 3: $d=7$, so $0=b_1 < b_2 < b_3 < b_4 = 5$. The only combination is $\{0,1,3,4\}$. We can take $k=5$ to get $\{0,4,5,9\}$, a spanning set.

And there is no way to have $d > 7$ and still fitting $b_2$ and $b_3$ without getting an arithmetic progression. So our proof is complete.

Sunday, March 27, 2016

Various double counting problems

These problems can all be solved by the double counting principle, that is, to count the same object two different ways and assert that those must match.

Suppose $n > 4$. Let $A_1, A_2, \dots ,A_k$ each be a set of $n$ integers, where $k \leq 4^{n-1} / 3^n$. Show that we can color each integer with one of the four colors so that each set contains integers of 4 different colors.

In a party attended by $n$ people, there were a number of handshakes. A group of 10 persons is called "tight" if each person shook hands with the other 9. It is known that we cannot add another handshake (two people who didn't shake hands now shaking hands) without increasing the number of tight groups. Prove that the number of handshakes is at least $8n-36$

In a class with many students, we choose 2016 committees among them. Each committee has 11 students, and each student may belong to multiple committees. Prove that there is a way to choose some of the students so that each committee has at least one chosen and one unchosen student.

Tuesday, February 9, 2016

Paintings and colors

In a museum there are $n$ paintings, each of which was painted with at least 3 colors. The total number of colors from all paintings is $m << n$. The average number of colors per painting is $s$.

If we choose $k$ paintings at random, what's the expected number of colors that we get? What's the maximum and minimum value of this expectation, for a fixed color-painting configuration, but for varying choices of paintings?

If we choose $l$ colors at random, what's the expected number of paintings that can be replicated with those colors? (It means each painting is painted only with those colors). Again, what's the maximum and minimum value of this expectation?

Remark: by choosing $m,n,s,k,l$ judiciously we can write problems such as: show that we can choose $k$ paintings such that the number of colors among those paintings is at most / at least $x$.


There are $N = {n \choose k}$ ways to choose paintings. For each choice of paintings, we tally up the total number of colors produced, and then we sum it over all possible choice of paintings. Let $S$ be this sum of total number of colors. The expected number of colors is then $S / N$.

Suppose the color $c$ is used by $p_c$ paintings. We wish to count the contribution of $c$ towards $S$. The color contributes one point to $S$ for each choice of paintings that includes at least one of the $p_c$, and zero otherwise. That means now the question is, how many ways can we choose $k$ out of $n$ paintings such that at least one of them comes from the $p_c$ paintings? There are $N$ ways total to choose, and there are ${n-p_c \choose k}$ ways to choose such that none of the $p_c$ paintings are chosen, so the total number is: $${n \choose k} - {n-p_c \choose k}$$ So: $$S = \sum_c {n \choose k} - {n-p_c \choose k}$$ where the sum runs over all $m$ colors. This expression is exact. What follows from this point on is an attempted to upper/lower bound $S$, and it may not be exact, although we will give examples to show that the bound is tight.

Now consider the function $f(t) = {n \choose k} - {n-t \choose k}$, defined over $t \in [1,m]$ (the color must be used in at least 1 painting, and at most $m$ paintings obviously). We are given that $m << n$ so it's safe to assume that ${n-m \choose k} > 0$. The convexity and concavity analysis depends on if $k$ is even or odd. For now, assume $k$ is odd. The analysis if $k$ is even is very similar.

The function $(n-t)(n-t-1)\dots (n-t-k+1)$ is convex in the interval $(0,n-k-1)$, and since $m << n$, it is convex in the interval $[1,m]$. That means $f(t)$ is concave. On the other hand, we know that the average number of colors per painting is $s$, so there are $sn$ distinct painting-color pairs, so $\sum_c p_c = sn$.

By Jensen, the maximum of $\sum_c f(p_c)$ is achieved if all the $p_c$ is the same, that is $sn/m$. In that case, $$\frac{S}{N} \leq \frac{\sum_c {n \choose k} - {n-p_c \choose k}}{n \choose k} = \frac{ m({n \choose k} - {n-\frac{sn}{m} \choose k}) }{n \choose k}$$ For example, for $n=50,k=3,m=25,s=10$, we have $S/N = 19.8$. So we can write a problem such as: show that we can choose 3 paintings such that between them we get at most 19 colors.

In order to find the lower bound, by majorization theorem, the minimum of $\sum_c f(p_c)$ is achieved by $[p_c] = [m,m,m,\dots,m,r,1,\dots,1]$ because that's the configuration that majorizes everything else. The number of $m$s, and $1$s and the value of $r$ (if needed) will have to depend on the particular problem setup, to make sure the following two conditions are met:

1. $\sum_c p_c = sn$ 2. The number of elements in $[p_c]$ is $m$.

For example, in the $n=50,k=3,m=25,s=10$ case above, we would have $[p_c] = [25,25,\dots,25,20,1,1,\dots,1]$ where there are 19 25s and 6 1s. Then: $$S \geq 25 \times {50 \choose 3} - 19 \times {50-25 \choose 3} - 1 \times {50-20 \choose 3} - 6 \times {50-1 \choose 3}$$ $$\frac{S}{N} \geq 16.9$$ So we can say: show that we can choose 3 paintings such that between them we get at least 17 colors.

Dancing partners

In a party with $n$ boys and $n$ girls, each boy dances with some girls and vice versa. (No pair of boy and girl dance more than once). There are $n^2-n+1$ dances that occurred throughout the night. Show that we can pair each boy with each girl so that everyone is paired with someone he/she danced with.


The key fact is because the number of dances is more than $n^2-n$. If it were exactly $n^2-n$, we could have a situation where $n-1$ boys danced with all the girls, and one boy never danced, and this effectively blocks that boy from being paired correctly.

Suppose that there is no way to pair them correctly. That is, for every given pairing, there's always a pair that did not dance. For each pairing, we define the score of said pairing to be the number of pairs that actually danced. This means a legal pairing is the one with score $n$.

Now let $S$ be the sum of all the scores of all possible pairings. Our contrapositive hypothesis is that all pairings have a score of at most $n-1$, so $S \leq (n-1)n!$ (because there are $n!$ possible pairings).

On the other hand, for each dance that happened throughout the night, we want to count how many points it contributes to $S$. Suppose the dance happens between boy $B$ and girl $G$. Then it contributes one point of score whenever the pairing pairs $B$ and $G$. In other words, there are $(n-1)!$ such pairings (because one pair is fixed and we have complete freedom to pair the other $n-1$ boys and $n-1$ girls. So the total number of score is: $$S = (n^2-n+1)(n-1)! > (n^2-n)(n-1)! = (n-1)n!$$ A contradiction.